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

Материал из CSC Wiki
Перейти к:навигация, поиск
(Осень)
(Практика)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 56: Строка 56:
  
 
Telegram-чат для обсуждений лекций и практик: https://t.me/joinchat/AA2G21ajZldIoWaAAUoW7w
 
Telegram-чат для обсуждений лекций и практик: https://t.me/joinchat/AA2G21ajZldIoWaAAUoW7w
 +
 +
<h3>Условия зачёта </h3>
 +
(''предварительные'')
 +
* <code>0.85 * (количество обязательных задач в домашних заданиях)</code>
 +
* <code>0.75 * (количество задач в контестах)</code>
  
 
<h3>Задачи</h3>
 
<h3>Задачи</h3>
[[Медиа:Master.2019.fall.pdf| Условия задач]]
+
[[Медиа:Master.2019.fall.pdf| Условия задач, осень]]
 +
 
 +
[[Медиа:Master.2020.spring.pdf| Условия задач, весна]]
  
 
<h3>Александр Мишунин</h3>
 
<h3>Александр Мишунин</h3>
Строка 67: Строка 74:
  
 
[https://docs.google.com/spreadsheets/d/1Y0vrwRVfzGDCt0bw_Is_VctfkjTi4umIegwuyUdAYjo/edit#gid=277089110 Таблица с результатами, осень]
 
[https://docs.google.com/spreadsheets/d/1Y0vrwRVfzGDCt0bw_Is_VctfkjTi4umIegwuyUdAYjo/edit#gid=277089110 Таблица с результатами, осень]
 +
 +
[https://docs.google.com/spreadsheets/d/14o7VNxZNyIaHTOMP4khFPTLUBXxEOvwEq1iA05XKw90/edit#gid=459193508 Таблица с результатами, весна]
  
 
<h3>Михаил Слабодкин</h3>
 
<h3>Михаил Слабодкин</h3>
Строка 72: Строка 81:
 
Контакты:  
 
Контакты:  
 
* <code>slabodkin.m[at]gmail.com</code>
 
* <code>slabodkin.m[at]gmail.com</code>
* Telegram: slabod
+
* <code>Telegram: @slabod</code>
  
 
Дедлайны по теоретическому ДЗ:  
 
Дедлайны по теоретическому ДЗ:  
* мягкий дедлайн в воскресенье в 23:59, после него преподаватель один раз проверяет работу до пары
+
* мягкий дедлайн за два дня до занятия (в субботу) в 13:00, после него преподаватель один раз проверяет работу до пары
* жёсткий дедлайн в 23:59 в день до занятия, после него работы не принимаются
+
* жёсткий дедлайн в день занятия (в понедельник) в 03:00, после него работы не принимаются
  
 
[https://docs.google.com/spreadsheets/d/1Y0vrwRVfzGDCt0bw_Is_VctfkjTi4umIegwuyUdAYjo/edit#gid=592669848 Таблица с результатами, осень]
 
[https://docs.google.com/spreadsheets/d/1Y0vrwRVfzGDCt0bw_Is_VctfkjTi4umIegwuyUdAYjo/edit#gid=592669848 Таблица с результатами, осень]
 +
 +
[https://docs.google.com/spreadsheets/d/14o7VNxZNyIaHTOMP4khFPTLUBXxEOvwEq1iA05XKw90/edit#gid=725375999 Таблица с результатами, весна]
  
 
<h3>Роман Бойкий</h3>
 
<h3>Роман Бойкий</h3>

Текущая версия на 20:58, 10 февраля 2020

Лекции

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

Контакты:

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

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

Осень

  • 5 сентября. Введение. Алгоритм. Модель вычисления RAM-машина. Память и время как ресурсы. Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. O-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента).
  • 12 сентября. Элементарные структуры данных. Массивы переменного размера: аддитивная и мультипликативная схемы аллокации. Односвязный список, двусвязный список. Абстрактные типы данных, интерфейс и реализация. Стек, очередь, дек; моделирование на основе массива. Моделирование очереди с помощью двух стеков. Анализ учётных стоймостей операций при помощи функция потенциала, истинные и учётные стоимости.
  • 19 сентября. Рекуррентные соотношения. Метод ”разделяй и властвуй“. Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск. Сортировка слиянием: с рекурсией и без. Нижняя оценка для сортировки сравнениями.
  • 26 сентября, первая лекция. Алгоритмы сортировки. Квадратичные сортировки. Сортировка с помощью кучи: очередь с приоритетами, построение кучи за линейное время, частичная сортировка.
  • 26 сентября, вторая лекция. Быстрая сортировка: понятие вероятностного алгоритма, время работы в среднем, анализ средней глубины рекурсии, элиминация хвостовой рекурсии, IntroSort. Быстрая сортировка: анализ среднего времени работы, массивы с малым количеством различных элементов, QuickSort3.
  • (На практике) Порядковые статистики, нахождение за линейное в среднем время. Медиана медиан.
  • 10 октября. Частичная сортировка. Сортировка подсчётом, стабильность. Цифровая сортировка. Bucket sort для равномерно распределённых вещественных чисел. Динамическое программирование. Общие принципы динамического программирования. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности. Кратчайшие пути в ациклических ориентированных графах. Дискретная задача о рюкзаке.
  • 17 октября. Динамическое программирование (продолжение). Дискретная задача о рюкзаке. Умножение матриц. Независимые множества максимального веса в деревьях. Редакционное расстояние: граф на подзадачах, нахождение кратчайшего пути в данном графе; нахождение оптимального выравнивания с использованием линейной памяти.
  • 24 октября. Жадные алгоритмы. Покрытие точек единичными отрезками. Непрерывный рюкзак. Задача о выборе заявок. Максимальные независимые множества в деревьях. Код Хаффмена.
  • 7 ноября. Задача о покрытии множествами. Минимальное покрывающее дерево: свойство разреза, жадная стратегия, алгоритм Прима, алгоритм Краскала.
  • 14 ноября. Система непересекающихся множеств. Представление множеств с помощью деревьев, эвристика сжатия путей, верхняя оценка на время работы m операций. Анализ учётных стоймостей операций: метод ростовщика.
  • 21 ноября Способы хранения графов: матрица смежности, списки смежности, матрица инцидентности. Поиск в глубину. Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности. Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин. Мосты и точки сочленения (на практике).
  • 28 ноября. Выделение компонент сильной связности в орграфах. Кратчайшие пути в графах. Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину.
  • 5 декабря. Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры, оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-ичной кучей).
  • 12 декабря. Нахождение кратчайших путей из одной вершины в графах, в которых есть рёбра отрицательного веса, алгоритм Беллмана-Форда, проверка наличия цикла отрицательного веса. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла.
  • 19 декабря. Альтернативные модели вычисления. Модель внешней памяти. Сортировка слиянием в модели внешней памяти. Модель cache-oblivios. Модель PRAM, вычисление максимума за константу. Модель BSP. Сортировка методом регулярного сэмплирования.

Литература

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

Практика

Telegram-чат для обсуждений лекций и практик: https://t.me/joinchat/AA2G21ajZldIoWaAAUoW7w

Условия зачёта

(предварительные)

  • 0.85 * (количество обязательных задач в домашних заданиях)
  • 0.75 * (количество задач в контестах)

Задачи

Условия задач, осень

Условия задач, весна

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

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

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

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

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

Михаил Слабодкин

Контакты:

  • slabodkin.m[at]gmail.com
  • Telegram: @slabod

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

  • мягкий дедлайн за два дня до занятия (в субботу) в 13:00, после него преподаватель один раз проверяет работу до пары
  • жёсткий дедлайн в день занятия (в понедельник) в 03:00, после него работы не принимаются

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

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

Роман Бойкий

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

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

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