skip to content
se.moevm.info
User Tools
Log In
Site Tools
Search
Tools
Show pagesource
Old revisions
Backlinks
Recent Changes
Media Manager
Sitemap
Log In
>
Recent Changes
Media Manager
Sitemap
You are here:
МОЭВМ Вики
»
Курсы
»
Построение и анализ алгоритмов
»
Программа
Sidebar
Регистрация первокурсников
Дипломникам (4 и 6 курс!)
Аспирантам
Регистрация результатов интеллектуальной деятельности (РИД)
Часто задаваемые вопросы о зачетах, экзаменах и пересдачах
1 курс
Программирование
Информатика
2 курс
Объектно-ориентированное программирование
Алгоритмы и структуры данных
Построение и анализ алгоритмов
3 курс
Базы данных
Основы промышленной разработки ПО
Тестирование
Искусственные нейронные сети
Базы знаний и экспертные системы
Научно-исследовательская практика
Производственная практика на кафедре МО ЭВМ, 3 курс
4 курс
Введение в нереляционные базы данных
Основы подготовки научных публикаций
Цифровая обработка сигналов
Машинное обучение
Проектирование человеко-машинного интерфейса
Статистические методы обработки экспериментальных данных
Разработка приложений для мобильных платформ
Аттестация за преддипломную практику (весенний семестр 4 и 6 курса)
Допуск до защиты ВКР (проверка демонстрационных материалов)
5 курс
Машинное обучение
Технологии автоматизации разработки ПО
Инструменты для анализа данных: R, Pandas
Анализ и интерпретация данных
Анализ, моделирование и оптимизация систем
Программные средства разработки систем искусственного интеллекта
Управление промышленной разработкой ПО
Нейронные сети (магистратура) для групп 2024 года
blockchain
Обучение с подкреплением
Представление знаний и системы искусственного интеллекта
(учебная практика и НИР)Аттестация магистрантов первого семестра обучения
(производственная практика НИР)Аттестация магистрантов второго семестра обучения
Классические байесовские фильтры
6 курс
Компьютерное Зрение
Пространственный искусственный интеллект
Smart Data
Knowledge Graphs
Многопоточное и распределённое программирование
Представление знаний и системы искусственного интеллекта
Robot OS
(производственная практика НИР)Аттестация магистрантов третьего семестра обучения
Аттестация за преддипломную практику (весенний семестр 4 и 6 курса)
Допуск до защиты ВКР (проверка демонстрационных материалов)
Научно-технический семинар 2024 (бывш. конференция ППС)
Регистрация научных профилей
Развертывание студенченских проектов
Moodle - хитрости, проблемы, решения (для преподавателей и авторов задач)
Domain-driven design
AutoML
Олимпиадное программирование
FAQ
Old
Summer Schools
Отправка отчетов
SPCN 2020
Магистрам
Учебные материалы по работе со Stepik
МДП
Разработка ПО с GUI
AI Systems practice
Список конференций
Сотрудникам
Функциональное программирование
Технологии хранения данных
Автоматизация учебных задач
courses:algorithms_building_and_analysis:lectures
This is an old revision of the document!
Table of Contents
Программа
Сложность алгоритмов
Поиск с возвращением
Жадные алгоритмы
Графы
Раскраска в 3 цвета
Минимальный разрез
Кратчайшие пути. A* и его расширения
Топологическая сортировка
Задача о коммивояжёре
Потоки в графах
Изоморфизм графов
Строки
Редакционное расстояние
Алгоритм Кнута-Морриса-Пратта
Алгоритм Ахо-Корасик
Динамическое программирование
Не рассматривается (пересечение с курсами и т.п.)
Графы и структуры данных
Остовные деревья
Задачи связности
Потоки в графах
Кратчайшие пути. Дейкстра
Паросочетания
Клики
Алгоритм Рабина-Карпа
Задачи выполнимости
Программа
Сложность алгоритмов
Виды сложности:
Операции
Время
Память
Понятие вычислительной сложности в зависимости от размера входа
Константная сложность на примере vector и unordered_set:
Амортизированная
В среднем
Поиск с возвращением
Идея поиска с возвращением (backtracking)
Пример на задаче о ферзях
Подходы метода ветвей и границ по отсеканию вариантов
Метод Монте-Карло
Пример на размере дерева
Пример на площади фигуры
Ограничения и условия применимости
Жадные алгоритмы
…
Графы
Раскраска в 3 цвета
Алгоритм полного перебора
Перебор с учётом выбора только из 2 цветов
Перебор подмножеств размера ⇐ n/3
Вероятностный алгоритм. Сведение к задаче выполнимости
Применение раскраски на практике
Минимальный разрез
Примеры практических задач
Алгоритм Каргера
Оптимизация Штейна алгоритма Каргера
Кратчайшие пути. A* и его расширения
Напоминание о A*
Эвристические функции
Алгоритм ALT
Алгоритм REACH
Алгоритм Arc flags
Топологическая сортировка
Ограничения на циклы
Алгоритм нумерацией шагов обхода
Алгоритм исключения вершины с минимальным количеством входящих рёбер
Задача о коммивояжёре
Сложность полного перебора
Метод ветвей и границ:
Отсечка по текущему найденному пути
Отсечка по весу МОД
Локальный поиск
2-окружение
Имитация отжига
Приближённое решение (2-приближённый алгоритм)
Потоки в графах
Алгоритм Гольдберга (проталкивания предпотока):
Идея push-relabel алгоритмов
Формализмы и инварианты
Доказательство корректности
Сравнение сложности с Фордом-Фалкерсоном
Изоморфизм графов
Задача изоморфизма:
Точный изоморфизм
Поиск подграфа в графе
Алгоритм Ульмана (переборный с матрицей)
Применение изоморфизма
Строки
Редакционное расстояние
Расстояние Левенштейна (редакционное расстояние)
Вычисление редакционного расстояния методом ДП
Восстановление РП по таблице (обратный ход в методе ДП)
Сведение задачи к путям в графе
Алгоритм Кнута-Морриса-Пратта
Основные определения
Задача точного поиска образца в строке
Наивный алгоритм и его сложность
Алгоритм КМП
Наивное построение префикс-функции и его сложность
Построение префикс-функции за линейное время
Алгоритм Ахо-Корасик
Задача точного поиска набора образцов
Trie
Задача о словаре
Алгоритм Ахо-Корасик
Динамическое программирование
Примеры вычисления чисел Фибоначчи
Масимальная возрастающая подпоследовательность:
Сведение к графу
Выделение подзадачи
Задача о рюкзаке:
Без повторений (одномерный случай)
С повторениями (двумерный случай)
Задача о порядке перемножения матриц
Не рассматривается (пересечение с курсами и т.п.)
Графы и структуры данных
Графы: определения и примеры. Упорядоченный граф
Представления графов: матрица инциденций, матрица смежности, список пар, структура смежности (списки инцидентности)
Остовные деревья
Задача о связности графа и остовный лес
Минимальное остовное дерево. Теорема “о минимальном ребре”:
Жадный алгоритм (Краскал)
Алгоритм “ближайшего соседа” (Ярник, Прим, Дейкстра)
Алгоритм Борувки (О(m*log n))
Задачи связности
Связные компоненты
Алгоритм нахождения сильно связных компонент (Косарайю)
Потоки в графах
Алгоритм Форда-Фалкерсона
Кратчайшие пути. Дейкстра
Кратчайшие пути от фиксированной вершины
Случай неотрицательных весов: алгоритм Дейкстры
Алгоритм Флойда-Уоршелла вычисления расстояний между всеми парами вершин, одновременное построение путей
Паросочетания
Понятия вершинных и рёберных покрытий
Теорема Галлаи
Алгоритм Куна поиска паросочетания в двудольном графе
Клики
Полные подграфы, клики
Применения и сложность задачи построения клик графа
Алгоритм нахождения клик на основе поиска с возвращением.
Алгоритм Рабина-Карпа
Идея использования хешей для решения задачи точного поиска образца в строке
Полиномиальные хеши для строк
Алгоритм быстрого вычисления всех хешей текста длины образца
Алгоритм Рабина-Карпа
Задачи выполнимости
Локальный поиск
Метод расщепления
Сведения
courses/algorithms_building_and_analysis/lectures.1707555634.txt.gz
· Last modified: 2024/02/10 09:00 by
kalishenko
Page Tools
Show pagesource
Old revisions
Backlinks
Export to PDF
Rename Page
ODT export
Back to top