Описание для «Алгоритмы и анализ сложности (ресурсный курс) - Весна 2024

Алгоритмы и анализ сложности (ресурсный курс) - Весна 2024 - Герасимов Александр Сергеевич

Преподаватель: Герасимов Александр Сергеевич

Skill Level: Beginner

Объявления

Примерная программа курса

Ссылка на навигационный курс для групп 5130202/20001 и 5130202/20002

Ссылка на навигационный курс для групп 5140901/31501 и 5140901/31502

1. Введение. Возвратная индукция и инварианты циклов для доказательства корректности алгоритмов. Временная и пространственная сложность алгоритма

2. Скорость роста функций. Простейшие арифметические алгоритмы

3. Метод "разделяй и властвуй". Алгоритм Карацубы для умножения натуральных чисел. Рекуррентные соотношения: основная теорема и другие методы решения

4. Метод "разделяй и властвуй": сортировка, порядковые статистики, умножение матриц

5. Графы: основные определения и способы представления

6. Поиск в глубину в графах

7. Сильно связные компоненты. Поиск в ширину в графах

8. Задача о кратчайших путях из одной вершины. Алгоритм Дейкстры

9. Алгоритм Беллмана-Форда. Кратчайшие пути в ориентированных ациклических графах. Жадные алгоритмы. Задача о выдаче сдачи

10. Минимальные покрывающие деревья: алгоритм Крускала и алгоритм Прима. Система непересекающихся множеств

12. Приём "запоминание". Задача о рюкзаке. Кратчайшие пути для всех пар вершин орграфа: алгоритм Флойда-Уоршелла

13. Введение в линейное программирование. Потоки в сетях

Некоторые задачи для практических занятий

Оцениваемая домашняя работа 1

Оцениваемая домашняя работа 2

Оцениваемая домашняя работа 3

Ссылка на Teams-команду, в которой 11.06.2024 в 16:00 пройдёт консультация

Информация о курсе

Алгоритмы и анализ сложности (ресурсный курс) - Весна 2024 - Герасимов Александр Сергеевич

Общая информация

Объявления

Примерная программа курса

Ссылка на навигационный курс для групп 5130202/20001 и 5130202/20002

Ссылка на навигационный курс для групп 5140901/31501 и 5140901/31502

Лекции

1. Введение. Возвратная индукция и инварианты циклов для доказательства корректности алгоритмов. Временная и пространственная сложность алгоритма

2. Скорость роста функций. Простейшие арифметические алгоритмы

3. Метод "разделяй и властвуй". Алгоритм Карацубы для умножения натуральных чисел. Рекуррентные соотношения: основная теорема и другие методы решения

4. Метод "разделяй и властвуй": сортировка, порядковые статистики, умножение матриц

5. Графы: основные определения и способы представления

6. Поиск в глубину в графах

7. Сильно связные компоненты. Поиск в ширину в графах

8. Задача о кратчайших путях из одной вершины. Алгоритм Дейкстры

9. Алгоритм Беллмана-Форда. Кратчайшие пути в ориентированных ациклических графах. Жадные алгоритмы. Задача о выдаче сдачи

10. Минимальные покрывающие деревья: алгоритм Крускала и алгоритм Прима. Система непересекающихся множеств

12. Приём "запоминание". Задача о рюкзаке. Кратчайшие пути для всех пар вершин орграфа: алгоритм Флойда-Уоршелла

13. Введение в линейное программирование. Потоки в сетях

Практические занятия

Некоторые задачи для практических занятий

Оцениваемая домашняя работа 1

Оцениваемая домашняя работа 2

Оцениваемая домашняя работа 3

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

Ссылка на Teams-команду, в которой 11.06.2024 в 16:00 пройдёт консультация

Алгоритмы и анализ сложности (ресурсный курс) - Весна 2024 - Герасимов Александр Сергеевич