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

Мы используем файлы cookies для улучшения работы сайта НИУ ВШЭ и большего удобства его использования. Более подробную информацию об использовании файлов cookies можно найти здесь, наши правила обработки персональных данных – здесь. Продолжая пользоваться сайтом, вы подтверждаете, что были проинформированы об использовании файлов cookies сайтом НИУ ВШЭ и согласны с нашими правилами обработки персональных данных. Вы можете отключить файлы cookies в настройках Вашего браузера.

✖

АБB
АБB
АБB

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

О кафедре

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

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

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

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

Публикации

Книга

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

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

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

Статья

Эффективный поиск минимального дерева на точках пространства в $l_1$-норме

Каймаков К. В., Малышев Д. С.

Математические заметки. 2025. Т. 117. № 5. С. 672-679.

Глава в книге

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.

Препринт

The Gamma-Theta Conjecture holds for planar graphs

Taletskii D.

math. arXiv. Cornell University, 2024

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

603093 Н.Новгород, ул. Родионова, д. 136, 406 к.

Тел: (831) 436-13-97
E-mail: kaf_pmi@hse.ru

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

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

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

Статус:: Маго-лего

Когда читается:: 3 модуль

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

Асеева Наталья Владимировна

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

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

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.

Цель освоения дисциплины

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.

Планируемые результаты обучения

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

Содержание учебной дисциплины

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

Элементы контроля

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

Промежуточная аттестация

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

Список литературы

Авторы

Савченко Андрей Владимирович

Современные методы исследования операций