Алгоритмы и структуры данных 5SE 2021-2022 — различия между версиями

Материал из CSC Wiki
Перейти к:навигация, поиск
(Рабочая программа)
Строка 12: Строка 12:
 
* '''9 сентября.''' Введение. Алгоритм. Модель вычисления RAM-машина. Память и время как ресурсы. Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. O-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента). Элементарные структуры данных. Массивы переменного размера: аддитивная и мультипликативная схемы аллокации.  
 
* '''9 сентября.''' Введение. Алгоритм. Модель вычисления RAM-машина. Память и время как ресурсы. Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. O-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента). Элементарные структуры данных. Массивы переменного размера: аддитивная и мультипликативная схемы аллокации.  
  
* '''16 сентября.'''  
+
* '''16 сентября.''' Односвязный список, двусвязный список. Абстрактные типы данных, интерфейс и реализация. Стек, очередь, дек; моделирование на основе массива. Моделирование очереди с помощью двух стеков. Анализ учётных стоймостей операций при помощи функция потенциала, истинные и учётные стоимости. Рекуррентные соотношения. Метод ”разделяй и властвуй“. Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск. Сортировка слиянием: с рекурсией и без. Нижняя оценка <math>\Omega(n\log n)</math> для сортировки сравнениями.
Односвязный список, двусвязный список. Абстрактные типы данных, интерфейс и реализация. Стек, очередь, дек; моделирование на основе массива. Моделирование очереди с помощью двух стеков. Анализ учётных стоймостей операций при помощи функция потенциала, истинные и учётные стоимости.
 
Рекуррентные соотношения. Метод ”разделяй и властвуй“. Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск. Сортировка слиянием: с рекурсией и без. Нижняя оценка <math>\Omega(n\log n)</math> для сортировки сравнениями.
 
  
 
* '''23 сентября.''' Алгоритмы сортировки. Квадратичные сортировки. Сортировка с помощью кучи: очередь с приоритетами, построение кучи за линейное время, частичная сортировка.
 
* '''23 сентября.''' Алгоритмы сортировки. Квадратичные сортировки. Сортировка с помощью кучи: очередь с приоритетами, построение кучи за линейное время, частичная сортировка.

Версия 15:33, 9 сентября 2021

Лекции

Лектор: Александр Смаль

Контакты:

  • avsmal[at]gmail.com
  • Telegram: avsmal

Рабочая программа

Осень

  • 9 сентября. Введение. Алгоритм. Модель вычисления RAM-машина. Память и время как ресурсы. Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. O-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента). Элементарные структуры данных. Массивы переменного размера: аддитивная и мультипликативная схемы аллокации.
  • 16 сентября. Односвязный список, двусвязный список. Абстрактные типы данных, интерфейс и реализация. Стек, очередь, дек; моделирование на основе массива. Моделирование очереди с помощью двух стеков. Анализ учётных стоймостей операций при помощи функция потенциала, истинные и учётные стоимости. Рекуррентные соотношения. Метод ”разделяй и властвуй“. Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск. Сортировка слиянием: с рекурсией и без. Нижняя оценка для сортировки сравнениями.
  • 23 сентября. Алгоритмы сортировки. Квадратичные сортировки. Сортировка с помощью кучи: очередь с приоритетами, построение кучи за линейное время, частичная сортировка.
  • 30 сентября. Быстрая сортировка: понятие вероятностного алгоритма, время работы в среднем, анализ средней глубины рекурсии, элиминация хвостовой рекурсии, IntroSort. Быстрая сортировка: анализ среднего времени работы, массивы с малым количеством различных элементов, QuickSort3.
  • 7 октября Частичная сортировка. Сортировка подсчётом, стабильность. Цифровая сортировка. Bucket sort для равномерно распределённых вещественных чисел. Порядковые статистики, нахождение за линейное в среднем время. Медиана медиан.
  • 14 октября. Динамическое программирование. Общие принципы динамического программирования. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности. Кратчайшие пути в ациклических ориентированных графах. Дискретная задача о рюкзаке.
  • 21 октября. Динамическое программирование (продолжение). Дискретная задача о рюкзаке. Умножение матриц. Независимые множества максимального веса в деревьях. Редакционное расстояние: граф на подзадачах, нахождение кратчайшего пути в данном графе; нахождение оптимального выравнивания с использованием линейной памяти.
  • 28 октября. Жадные алгоритмы. Покрытие точек единичными отрезками. Непрерывный рюкзак. Задача о выборе заявок. Максимальные независимые множества в деревьях. Код Хаффмена.
  • 4 ноября. Минимальное покрывающее дерево: свойство разреза, жадная стратегия, алгоритм Прима, алгоритм Краскала.
  • 11 ноября. Система непересекающихся множеств. Представление множеств с помощью деревьев, эвристика сжатия путей, верхняя оценка на время работы m операций. Анализ учётных стоймостей операций: метод ростовщика.
  • 18 ноября Альтернативные модели вычисления. Модель внешней памяти. Сортировка слиянием в модели внешней памяти. Модель cache-oblivios. Модель PRAM, вычисление максимума за константу. Модель BSP. Сортировка методом регулярного сэмплирования.
  • 25 ноября. Способы хранения графов: матрица смежности, списки смежности, матрица инцидентности. Поиск в глубину. Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности. Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин. Выделение компонент сильной связности в орграфах.
  • 2 декабря. Кратчайшие пути в графах. Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину. Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры, оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-ичной кучей).
  • 9 декабря. Нахождение кратчайших путей из одной вершины в графах, в которых есть рёбра отрицательного веса, алгоритм Беллмана-Форда, проверка наличия цикла отрицательного веса. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла.
  • 16 декабря. ЗАПАСНАЯ ЛЕКЦИЯ

Литература

Онлайн-курсы

Практика

Таблица с результатами, осень.

ПРАВИЛО

Если вы используете какие-то внешние источники, то вы должны явно сообщить об этом.

Задачи

TeX-шаблон для домашек

  • Домашняя работа 1: pdf tex

Александр Мишунин

Контакты: alexander.mishunin[at]gmail.com

Дедлайны по теоретическому ДЗ: до начала занятия для правок уже присланных ранее задач, и до начала суток, в которые будет занятие, для новых задач.

Татьяна Белова

Контакты:

  • yukikomodo@gmail.com
  • Telegram: @tbelova

Правила сдачи:

  • Работы присылайте, пожалуйста, на почту в виде pdf-файла.

Дедлайны по теоретическому ДЗ:

  • Мягкий дедлайн: пятница, 20:00.
  • Жесткий дедлайн: воскресенье, 23:59.

Задачи, присланные до мягкого дедлайна, будут проверены к воскресенью. Исправления, а также новые задачи можно присылать до жесткого дедлайна.

Евгений Кравченко и Виктор Крыштапович

Контакты:

  • Виктор: kry127+itmo-se-5-algo-2021@yandex.ru. Тема письма: HW <номер домашки>, <Фамилия>. В случае отправки по правильному почтовому адресу вернётся автоматический ответ вида "Спасибо! Домашняя работа принята в пул работ."
  • Евгений: zzzheka97+itmo-se-5-algo-2021@gmail.com. Тема письма: HW <номер домашки>, <Фамилия>.

Правила сдачи:

  • Мягкий дедлайн: пятница, 20:00. Гарантии на работы, присланные до мягкого дедлайна: будут обязательно проверены и получен фидбек до жёсткого дедлайна, исправления можно прислать к жёсткому дедлайну
  • Жёсткий дедлайн: воскресенье, 23:59. Гарантия: будут обязательно проверены
  • После жёсткого дедлайна: работы не проверяются с вероятностью почти наверное

Правила зачета: TBD