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

АБB
АБB
АБB

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

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

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

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

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

Публикации

Книга

Integral Robot Technologies and Speech Behavior

Kharlamov A. A., Pantiukhin D., Borisov V. et al.

Newcastle upon Tyne: Cambridge Scholars Publishing, 2024.

Статья

On efficient algorithms for bottleneck path problems with many sources
В печати

Каймаков К. В., Malyshev D.

Optimization Letters. 2024. P. 1-11.

Глава в книге

Neural Networks for Speech Synthesis of Voice Assistants and Singing Machines

Pantiukhin D.

In bk.: Integral Robot Technologies and Speech Behavior. Newcastle upon Tyne: Cambridge Scholars Publishing, 2024. Ch. 9. P. 281-296.

Препринт

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 implement an efficient tabu search 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
to get acquainted with several examples of neighborhoods used for different optimization problems
to get acquainted with several examples of tabu search algorithms for a simple scheduling problem, maximum clique problem and min-k-tree problem
to get acquainted with tabu search approach allowing local search to go out of local optimums
to know basic parameters and features of branch-and-bound methods including branching strategy, bounds computation, initial heuristic solution
to know basic parameters of local search algorithms including initial solution construction, restart strategy, stopping criterion, first/best improvement strategies.
to know basic parameters of tabu search including tabu strategy, tabu list length, aspiration criterion
to understand the main feature which should be found for a problem to apply a dynamic programming approach: the problem should «repeat itself»

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 after week 1
Programming assignment after week 2
Programming assingment after 4 week
Final project
Tests (after 3,5,6 weeks)

Interim Assessment

2021/2022 3rd module
55% Programming assignments + 15% tests + 30% Final task (0.15*w1 + 0.15*w2 + 0.05*w3 + 0.25*w4 + 0.05*w5 + 0.05*w6 + 0.30*f )

Bibliography

Recommended Core Bibliography

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

Mauricio G.C. Resende, & Celso C. Ribeiro. (2016). Optimization by GRASP : Greedy Randomized Adaptive Search Procedures. Springer.

Modern Methods of Decision Making