Кафедра прикладной математики и информатики (Нижний Новгород)

АБB
АБB
АБB

Обычная версия сайта

Кафедра ПМИ создана в 2006 году как выпускающая кафедра по направлению "Прикладная математика и информатика".

Целью деятельности кафедры «Прикладной математики и информатики» является подготовка высококвалифицированных специалистов (бакалавров и магистров) по направлению 010500 «Прикладная математика и информатика», обладающих знаниями и квалификацией, необходимыми для профессионального моделирования и информационного обеспечения экономических и бизнес процессов, анализа и обработки данных.

Научная деятельность

Кафедра выполняет межкафедральные (кафедры Информационных систем и технологий, Математики и др.) исследовательские проекты, национальные проекты в составе общих исследовательских групп (РФФИ, проекты Минобрнауки РФ и др.) с участием партнеров из Института прикладной математики им. М. Келдыша РАН, Математического института им. В. Стеклова РАН, Института прикладной физики РАН, МГУ им. М. Ломоносова, ННГУ им Н. Лобачевского. Осуществляется международное сотрудничество с различными научными центрами Европы и США.

Публикации

Книга

Теория вероятностей и математическая статистика. 2-е изд.

Колданов А. П., Колданов П. А.

М.: Издательский дом НИУ ВШЭ, 2024.

Статья

Efficient Online Sensitivity Analysis For The Injective Bottleneck Path Problem
В печати

Kirill V. Kaymakov, Dmitry S. Malyshev.

Optimization Letters. 2025.

Глава в книге

ALOE: Boosting Large Language Model Fine-Tuning with Aggressive Loss-Based Elimination of Samples

Demidovskij A., Трутнев А. И., Тугарев А. М. et al.

In bk.: Frontiers in Artificial Intelligence and Applications: 27th European Conference on Artificial Intelligence, 19–24 October 2024, Santiago de Compostela, Spain. Vol. 392. IOS Press Ebooks, 2024. P. 3980-3986.

Препринт

DAREL: Data Reduction with Losses for Training Acceleration of Real and Hypercomplex Neural Networks

Demidovskij A., Трутнев А. И., Тугарев А. М. et al.

NeurIPS 2023 Workshop. ZmuLcqwzkl. OpenReview, 2023

Все публикации

Кто читает:: Кафедра прикладной математики и информатики (Нижний Новгород) (Факультет информатики, математики и компьютерных наук (Нижний Новгород))

Статус:: Курс обязательный

Когда читается:: 1-й курс, 3 модуль

Преподаватель

Бацын Михаил Владимирович

Full Syllabus

Abstract

The course is devoted to heuristic and exact algorithms for combinatorial optimization problems. The prerequisites for this course are graph theory; basic data structures (vector, list, tree, heap, stack, queue etc), algorithms (DFS, BFS, binary search, sort etc) and their complexity; experience in C++ programming.

Learning Objectives

To get acquainted with efficient algorithms, which can be applied to solve a large class of problems coming from real life – combinatorial optimization problems
To get programming experience and understanding of many well-known problems and algorithms to solve them
To be able to suggest a couple of heuristic algorithms and an exact algorithm for almost every real-life problem related to discrete optimization.

Expected Learning Outcomes

to be able to implement a branch-and-bound algorithm in C++ program
to be able to implement a greedy algorithm in C++ program
to be able to implement an efficient constructive algorithm in C++ program
to be able to suggest a constructive branch-and-bound algorithm for an arbitrary combinatorial optimization problem
to be able to suggest a dynamic programming algorithm for an optimization problem which can be expressed via the same problem, but having a smaller size
to be able to suggest a greedy algorithm for an arbitrary combinatorial optimization problem
to be able to suggest an efficient constructive algorithm for an arbitrary combinatorial optimization problem
to be able to suggest an efficient local search algorithm for an arbitrary combinatorial optimization problem
to be able to suggest an efficient tabu search algorithm for an arbitrary combinatorial optimization problem
to get acquainted with branch-and-bound methods applied to find an exact globally optimal solution for a combinatorial optimization problem
to get acquainted with different combinatorial optimization problems
to get acquainted with different local search algorithms including ILS (Iterated Local Search, GRASP (Greedy Randomized Adaptive Search Procedure), VNS (Variable Neighborhood Search), LNS (Large Neighborhood Search)
to get acquainted with dynamic programming methods applied to find an exact globally optimal solution for polynomial and pseudo-polynomial problems including the shortest path, the longest common subsequence, the pattern matching, the knapsack, the partition problems
to get acquainted with examples of branch-and-bound algorithms for the travelling salesman problem and maximum clique problem
to get acquainted with several examples of greedy approaches
to get acquainted with several examples of max-regret, greedy randomized and other constructive approaches

Course Contents

Combinatorial optimization problems and greedy algorithms
Simple and efficient heuristics: max-regret, greedy randomized and others
Local search algorithms
Tabu search approach
Branch-and-bound methods
Dynamic programming methods

Assessment Elements

Programming assignment / week 1
Programming assignment / week 2
Programming assignment / week 3
Final Programming assignment

Interim Assessment

2023/2024 3rd module
0.3 * Final Programming assignment + 0.3 * Programming assignment / week 1 + 0.2 * Programming assignment / week 2 + 0.2 * Programming assignment / week 3

Bibliography

Recommended Core Bibliography

Combinatorial optimization and applications, 3rd International Conference, COCOA 2009 Huangsham, China, June 10-12, 2009 : Proceedings, eds. Ding-Zhu, Xiaodong Hu, Panos M. Pardalos, 542 p., , 2009
Mauricio G.C. Resende, & Celso C. Ribeiro. (2016). Optimization by GRASP : Greedy Randomized Adaptive Search Procedures. Springer.
Michael L. Pinedo. (2016). Scheduling : Theory, Algorithms, and Systems: Vol. Fifth edition. Springer.
Potvin, J.-Y., & Gendreau, M. (2010). Handbook of Metaheuristics (Vol. 2nd ed). New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=373689

Recommended Additional Bibliography

Data Correcting Approaches in Combinatorial Optimization, 114 p., Goldengorin, B., Pardalos, P. M., 2012

Authors

BATSYN MIKHAIL VLADIMIROVICH

Modern operations research methods