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

Мы используем файлы 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

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

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

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

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

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

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

Пономаренко Александр Александрович

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

Аннотация

Ресурсы вычислительной техники конечны. Вместе с тем, существует масса способов, как можно запрограммировать компьютер на решение одной задачи. При этом один алгоритм может требовать меньшее число вычислительных ресурсов чем другой. Данный курс должен помочь студенту освоить подходы к построению эффективных алгоритмов для решения широкого спектра практических задач.

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

знать основные структуры данных (список, дерево, хеш-таблицы, графы), базовые алгоритмы (поиск в глубину, поиск в ширину, принцип разделяй и властвуй, динамическое программирование, поиск с отсечением, генерирование комбинаторных объектов).
развить алгоритмическое мышление
овладеть навыками программирования на языке C++ в процессе реализации основных вычислительных алгоритмов и структур данных

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

Владеет методом "поиск в глубину"
Владеет методом "поиск в ширину"
Знает различные формализации понятия алгоритма.
Понимает и умеет реализовывать "двоичное дерево"
Понимает и умеет реализовывать различные методы хэширования
Понимает когда можно использовать "жадные" алгоритмы.
Решает задачи методом динамического программирования
Умеет использовать метод динамического программирования
Умеет использовать нотацию большого О
Умеет оценивать вычислительную сложность алгоритмов
Умеет реализовывать алгоритмы поиска минимального остова, определения изоморфноти графов
Умеет реализовывать алгоритмы построения выпуклой оболочки и вращения геометрических фигур
Умеет реализовывать базовые алгоритмы на графах
Умеет реализовывать различные комбинаторные объекты
Умеет реализовывать рекурсивные алгоритмы

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

Понятие и свойство алгоритма. Способы записи алгоритма. Различные формализации понятия алгоритма.
Сложность алгоритмов. Классы алгоритмов.
Поиск в ширину. Поиск в глубину. Рекурсия.
Двоичные деревья.
Хеширование
Построение различных комбинаторных объектов
Жадные алгоритмы
Динамическое программирование
Динамическое программирование – разные задачи.
Алгоритмы на графах
Алгоритмы на графах – 2
Геометрические задачи

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

Лабораторная работа "Ход-конём"
Лабораторная работа "Хамелеон"
Поиск в ширину
Лабораторная работа "Задача о сумме"
Лабораторная работа "Сортировка подсчётом"
Лабораторная работа "Хэширование цепочками"
Лабораторная работа "Хэширование с открытой адресацией (двойное хэширование!)"
Лабораторная работа "Поиск по интервалу в двоичном дереве"
Лабораторная работа "Лабиринт с бомбами"
Поиск в ширину/Динамическое программирование
Лабораторная работа "Оптимальный порядок перемножения матриц"
Динамическое программирование
Лабораторная работа "Жук-инвалид"
Лабораторная работа "Острова"
Лабораторная работа "Количество правильных скобочных последовательностей"
Лабораторная работа "Найти минимальный остов"
Лабораторная работа "Взлом сети"
Динамическое программирование
Лабораторная работа "Быстрая сортировка"
Разделяй и властвуй
Лабораторная работа "Жадны до денег"
Динамическое программирование
Лабораторная работа "Ход-конём"
Лабораторная работа "Хамелеон"
Поиск в ширину
Лабораторная работа "Задача о сумме"
Лабораторная работа "Сортировка подсчётом"
Лабораторная работа "Хэширование цепочками"
Лабораторная работа "Хэширование с открытой адресацией (двойное хэширование!)"
Лабораторная работа "Поиск по интервалу в двоичном дереве"
Лабораторная работа "Лабиринт с бомбами"
Поиск в ширину/Динамическое программирование
Лабораторная работа "Оптимальный порядок перемножения матриц"
Динамическое программирование
Лабораторная работа "Жук-инвалид"
Лабораторная работа "Острова"
Лабораторная работа "Количество правильных скобочных последовательностей"
Лабораторная работа "Найти минимальный остов"
Лабораторная работа "Взлом сети"
Динамическое программирование
Лабораторная работа "Быстрая сортировка"
Разделяй и властвуй
Лабораторная работа "Жадны до денег"
Динамическое программирование

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

2021/2022 учебный год 2 модуль
0.06 * Лабораторная работа "Взлом сети" + 0.06 * Лабораторная работа "Жадны до денег" + 0.06 * Лабораторная работа "Найти минимальный остов" + 0.06 * Лабораторная работа "Поиск по интервалу в двоичном дереве" + 0.08 * Лабораторная работа "Ход-конём" + 0.06 * Лабораторная работа "Острова" + 0.06 * Лабораторная работа "Сортировка подсчётом" + 0.06 * Лабораторная работа "Задача о сумме" + 0.06 * Лабораторная работа "Оптимальный порядок перемножения матриц" + 0.06 * Лабораторная работа "Хэширование цепочками" + 0.06 * Лабораторная работа "Быстрая сортировка" + 0.06 * Лабораторная работа "Количество правильных скобочных последовательностей" + 0.08 * Лабораторная работа "Хамелеон" + 0.06 * Лабораторная работа "Хэширование с открытой адресацией (двойное хэширование!)" + 0.06 * Лабораторная работа "Лабиринт с бомбами" + 0.06 * Лабораторная работа "Жук-инвалид"

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

Авторы

Пономаренко Александр Александрович
Калягин Валерий Александрович

Алгоритмы и структуры данных