Алгоритмы и структуры данных на ПМИ (основной поток) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Четвертый модуль)
(link death)
 
(не показано 16 промежуточных версии 3 участников)
Строка 1: Строка 1:
 
'''Лектор:''' [http://www.hse.ru/staff/obiedkov С. Объедков]
 
'''Лектор:''' [http://www.hse.ru/staff/obiedkov С. Объедков]
 +
 +
'''[Оценки https://docs.google.com/spreadsheets/d/1xtmTV9_jYmGj34_sr1EqTKqrRji3J-1dpRIoHB7H7kc/pubhtml]
  
 
'''Расписание лекций:'''<br/>
 
'''Расписание лекций:'''<br/>
 
понедельник 10:30 – 11:50, ауд. 622<br/>
 
понедельник 10:30 – 11:50, ауд. 622<br/>
 
четверг 12:10 – 13:30, ауд. 622
 
четверг 12:10 – 13:30, ауд. 622
 +
 +
'''Консультации (по предварительной договоренности):'''<br/>
 +
понедельник 18:00 – 20:00, к. 324<br/>
 +
четверг 16:30 – 18:00, к. 324
  
 
== Рекомендуемая литература ==
 
== Рекомендуемая литература ==
Строка 10: Строка 16:
 
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
 
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
 
# Также см. [https://www.dropbox.com/sh/5lxaheg89isd6h9/AACOa50ihgNiu46YqhguwmDBa/algo_16-17_1course_standart.pdf конспекты].
 
# Также см. [https://www.dropbox.com/sh/5lxaheg89isd6h9/AACOa50ihgNiu46YqhguwmDBa/algo_16-17_1course_standart.pdf конспекты].
 +
# [https://syarifsoden.blogspot.com ,основные учебники по программированию, ноутбук экран рекордер приложение ]
  
 
== Лекции ==
 
== Лекции ==
Строка 32: Строка 39:
 
* '''10 апреля.''' Самоорганизующиеся списки и конкурентный анализ онлайн-алгоритмов.
 
* '''10 апреля.''' Самоорганизующиеся списки и конкурентный анализ онлайн-алгоритмов.
 
* '''13 апреля.''' Динамическое программирование: выравнивание абзаца по ширине. Свойства задач, эффективно решаемых при помощи динамического программирования: наличие полиномиального числа подзадач, выразимость исходной задачи в терминах подзадач, сводимость больших подзадач к полиномиальному числу меньших подзадач. Вычисление редакционного расстояния и выравнивание последовательностей.
 
* '''13 апреля.''' Динамическое программирование: выравнивание абзаца по ширине. Свойства задач, эффективно решаемых при помощи динамического программирования: наличие полиномиального числа подзадач, выразимость исходной задачи в терминах подзадач, сводимость больших подзадач к полиномиальному числу меньших подзадач. Вычисление редакционного расстояния и выравнивание последовательностей.
* '''17 апреля.''' Динамическое программирования на деревьях: нахождение независимого множества максимального веса в дереве. Задача о рюкзаке: жадный приближенный алгоритм; псевдополиномиальный алгоритм, основанный на динамическом программировании; приближенная схема полиномиального времени.
+
* '''17 апреля.''' Динамическое программирование на деревьях: нахождение независимого множества максимального веса в дереве. Задача о рюкзаке: жадный приближенный алгоритм; псевдополиномиальный алгоритм, основанный на динамическом программировании; приближенная схема полиномиального времени.
 
* '''20 апреля.''' Графы. Способы представления графов: матрица смежности и списки смежности. Обход графа в глубину и ширину. Поиск компонент связности в неориентированном графе.
 
* '''20 апреля.''' Графы. Способы представления графов: матрица смежности и списки смежности. Обход графа в глубину и ширину. Поиск компонент связности в неориентированном графе.
 
* '''24 апреля.''' Топологическая сортировка за линейное время: алгоритмы, основанные на удалении вершин без входящих ребер и на поиске в глубину.
 
* '''24 апреля.''' Топологическая сортировка за линейное время: алгоритмы, основанные на удалении вершин без входящих ребер и на поиске в глубину.
Строка 41: Строка 48:
 
* '''25 мая.''' Система непересекающихся множеств.
 
* '''25 мая.''' Система непересекающихся множеств.
 
* '''27 мая.''' Максимальный поток. Алгоритм Форда – Фалкерсона.
 
* '''27 мая.''' Максимальный поток. Алгоритм Форда – Фалкерсона.
 +
* '''29 мая.''' Полиномиальный вариант алгоритма Форда – Фалкерсона (с поиском "широких" увеличивающих путей).
 +
* '''1 июня.''' Алгоритм Эдмондса – Карпа. Алгоритм Диница. Двойственность задач о максимальном потоке и минимальном разрезе. Минимальный разрез в неориентированном графе. Алгоритм Каргера.
 +
* '''5 июня.''' Конечные автоматы. Регулярные языки. Замкнутость регулярных языков по дополнению, пересечению и объединению. Минимизация конечного автомата.
 +
* '''8 июня.''' Регулярные выражения. Недетерминированные конечные автоматы. Эквивалентность детерминированных и недетерминированных конечных автоматов. Замкнутость регулярных языков относительно регулярных операций. Построение конечного автомата по регулярному выражению.
 +
* '''9 июня.''' Эквивалентность регулярных выражений и конечных автоматов. Нерегулярные языки. Лемма о накачке.
  
 
== Домашние задания ==
 
== Домашние задания ==
Строка 56: Строка 68:
 
ДЗ 1-3: [https://official.contest.yandex.ru/contest/4445 Обход в глубину] — до 23:59:59 7 мая.
 
ДЗ 1-3: [https://official.contest.yandex.ru/contest/4445 Обход в глубину] — до 23:59:59 7 мая.
  
ДЗ 2-1: [https://official.contest.yandex.ru/contest/4561 Обход в ширину и алгоритм Дейкстры] — до 23:59:59 4 июня.
+
ДЗ 2-1: [https://official.contest.yandex.ru/contest/4561 Обход в ширину и алгоритм Дейкстры] — до 23:59:59 7 июня.
 +
 
 +
ДЗ 2-2: [https://official.contest.yandex.ru/contest/4602 Алгоритм Флойда, остовные деревья, потоки] — до 23:59:59 16 июня. Для получения максимальной оценки достаточно решить любые 8 задач.
  
 
== Контрольные работы ==
 
== Контрольные работы ==
Строка 66: Строка 80:
  
 
В конце четвертого модуля пройдет письменный экзамен. На экзамене можно пользоваться бумажными материалами и нельзя — электронными.
 
В конце четвертого модуля пройдет письменный экзамен. На экзамене можно пользоваться бумажными материалами и нельзя — электронными.
 +
 +
[https://www.dropbox.com/s/0gzo35d1vv9s6ey/regular.pdf?dl=0 Задачи на конечные автоматы] для подготовки к экзамену.
 +
 +
Консультация: 23 июня, 16:40, ауд. 205.
 +
 +
[https://www.dropbox.com/s/9gd8o29w7rjgwot/algo-exam2017.pdf?dl=0 Задачи] экзамена 24 июня 2017 г.
  
 
== Оценка ==
 
== Оценка ==
Строка 79: Строка 99:
 
! Подгруппа !! Преподаватель !! Учебные ассистенты !! Расписание занятий
 
! Подгруппа !! Преподаватель !! Учебные ассистенты !! Расписание занятий
 
|-
 
|-
| 162-1 || [http://www.hse.ru/staff/obiedkov Сергей Объедков]  || [mailto:piter.zh@gmail.com Петр Жижин] || '''Пн''', '''пт''' (ауд. 513): 13:40 – 15:00
+
| 162-1 || [https://lagutube.com lagutube]  || [download lagu] || '''Пн''', '''пт''' (ауд. 513): 13:40 – 15:00
 
|-
 
|-
 
| 162-2 || [https://www.hse.ru/org/persons/174481011 Филипп Синицын] || [mailto:arture226@gmail.com Арсений Турышев] || '''Пн''' (ауд. 513), '''чт''' (ауд. 301): 9:00 – 10:20
 
| 162-2 || [https://www.hse.ru/org/persons/174481011 Филипп Синицын] || [mailto:arture226@gmail.com Арсений Турышев] || '''Пн''' (ауд. 513), '''чт''' (ауд. 301): 9:00 – 10:20
Строка 99: Строка 119:
 
| 167-2 || [https://www.hse.ru/org/persons/161006240 Михаил Чичварин] || [mailto:mkryabinin@edu.hse.ru Максим Рябинин] || '''Ср''' (ауд. 605), '''чт''' (ауд. 513): 10:30 – 11:50
 
| 167-2 || [https://www.hse.ru/org/persons/161006240 Михаил Чичварин] || [mailto:mkryabinin@edu.hse.ru Максим Рябинин] || '''Ср''' (ауд. 605), '''чт''' (ауд. 513): 10:30 – 11:50
 
|-
 
|-
| 168-1 ||  [http://www.hse.ru/org/persons/138215687 Михаил Дектярев] || [mailto:oleg.naydin@gmail.com Олег Найдин] || '''Ср''' (ауд. 416), '''чт''' (ауд. 501): 10:30 – 11:50
+
| 168-1 ||  [http://www.hse.ru/org/persons/138215687 Михаил Дектярев] || [mailto:arture226@gmail.com Арсений Турышев] || '''Ср''' (ауд. 416), '''чт''' (ауд. 501): 10:30 – 11:50
 
|-
 
|-
| 168-2 || Ольга Абакумова || [mailto:oleg.naydin@gmail.com Олег Найдин] || '''Ср''' (ауд. 327): 10:30 – 11:50; '''чт''' (ауд. 605): 9:00 – 10:20  
+
| 168-2 || Ольга Абакумова || [mailto:piter.zh@gmail.com Петр Жижин] || '''Ср''' (ауд. 327): 10:30 – 11:50; '''чт''' (ауд. 605): 9:00 – 10:20  
 
|-
 
|-
 
|}
 
|}

Текущая версия на 09:37, 31 августа 2021

Лектор: С. Объедков

[Оценки https://docs.google.com/spreadsheets/d/1xtmTV9_jYmGj34_sr1EqTKqrRji3J-1dpRIoHB7H7kc/pubhtml]

Расписание лекций:
понедельник 10:30 – 11:50, ауд. 622
четверг 12:10 – 13:30, ауд. 622

Консультации (по предварительной договоренности):
понедельник 18:00 – 20:00, к. 324
четверг 16:30 – 18:00, к. 324

Рекомендуемая литература

  1. Дасгупта, Пападимитриу, Вазирани. Алгоритмы
  2. Клейнберг, Тардос. Алгоритмы. Разработка и применение
  3. Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы: построение и анализ
  4. Также см. конспекты.
  5. ,основные учебники по программированию, ноутбук экран рекордер приложение

Лекции

Третий модуль

  • 12 января. Постановка задачи поиска медианы. Простые решения этой задачи. Оценка сложности алгоритмов по времени и памяти. О-, o-, Ω-, ω-, Θ-обозначения. Время работы в худшем, лучшем и среднем случаях. Сортировка вставками.
  • 19 января. Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема.
  • 26 января. Быстрая сортировка. Оптимальность сортировки слиянием.
  • 2 февраля. Разделяй и властвуй: быстрое возведение в степень по модулю, выбор порядковой статистики за время O(n) — рандомизированный и детерминированный алгоритмы.
  • 9 февраля. Структуры данных. Массив с операциями инициализации, чтения и записи, выполняемыми за время O(1). Структура данных для быстрого поиска и вставки на основе нескольких отсортированных массивов. Амортизационный анализ: групповой анализ и банковский метод (на примере двоичного счетчика).
  • 16 февраля. Амортизационная стоимость операций в динамическом массиве. Реализация стека при помощи массива; нахождение максимального значения в стеке за константное время.
  • 2 марта. Реализация очереди при помощи связного списка и при помощи массива; нахождение минимального элемента в очереди за константное время. Приоритетная очередь, ее реализация при помощи двоичной кучи. Сортировка кучей.
  • 9 марта. Деревья поиска. Алгоритм построения двоичного дерева поиска. Сложность поиска в двоичном дереве поиска. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой. Сбалансированные деревья поиска. Определение красно-черного дерева.
  • 16 марта. Красно-черные деревья. Удаление узла из двоичного дерева поиска.
  • 23 марта. Деревья отрезков. Динамические порядковые статистики.

Четвертый модуль

  • 3 апреля. Хеш-таблицы. Методы задания хеш-функций. Разрешение коллизий при помощи цепочек. Открытая адресация.
  • 6 апреля. Сложность операций для открытой адресации в среднем случае. Универсальное хеширование. Двухуровневое идеальное хеширование.
  • 10 апреля. Самоорганизующиеся списки и конкурентный анализ онлайн-алгоритмов.
  • 13 апреля. Динамическое программирование: выравнивание абзаца по ширине. Свойства задач, эффективно решаемых при помощи динамического программирования: наличие полиномиального числа подзадач, выразимость исходной задачи в терминах подзадач, сводимость больших подзадач к полиномиальному числу меньших подзадач. Вычисление редакционного расстояния и выравнивание последовательностей.
  • 17 апреля. Динамическое программирование на деревьях: нахождение независимого множества максимального веса в дереве. Задача о рюкзаке: жадный приближенный алгоритм; псевдополиномиальный алгоритм, основанный на динамическом программировании; приближенная схема полиномиального времени.
  • 20 апреля. Графы. Способы представления графов: матрица смежности и списки смежности. Обход графа в глубину и ширину. Поиск компонент связности в неориентированном графе.
  • 24 апреля. Топологическая сортировка за линейное время: алгоритмы, основанные на удалении вершин без входящих ребер и на поиске в глубину.
  • 27 апреля. Алгоритм проверки сильной связности ориентированного графа. Вычисление компонент сильной связности в ориентированном графе.
  • 11 мая. Поиск путей возведением в степень матрицы смежности графа. Алгоритм Флойда – Уоршелла: формулировка в терминах динамического программирования, оценка сложности, оптимизация по памяти, обнаружение циклов с отрицательным весом, восстановление кратчайших путей.
  • 15 мая. Алгоритм Беллмана – Форда. Алгоритм Дейкстры.
  • 18 мая. Минимальные остовные деревья. Алгоритм Крускала, алгоритм Прима.
  • 25 мая. Система непересекающихся множеств.
  • 27 мая. Максимальный поток. Алгоритм Форда – Фалкерсона.
  • 29 мая. Полиномиальный вариант алгоритма Форда – Фалкерсона (с поиском "широких" увеличивающих путей).
  • 1 июня. Алгоритм Эдмондса – Карпа. Алгоритм Диница. Двойственность задач о максимальном потоке и минимальном разрезе. Минимальный разрез в неориентированном графе. Алгоритм Каргера.
  • 5 июня. Конечные автоматы. Регулярные языки. Замкнутость регулярных языков по дополнению, пересечению и объединению. Минимизация конечного автомата.
  • 8 июня. Регулярные выражения. Недетерминированные конечные автоматы. Эквивалентность детерминированных и недетерминированных конечных автоматов. Замкнутость регулярных языков относительно регулярных операций. Построение конечного автомата по регулярному выражению.
  • 9 июня. Эквивалентность регулярных выражений и конечных автоматов. Нерегулярные языки. Лемма о накачке.

Домашние задания

Третий модуль

Сортировки — до 12 февраля. Для решения задачи F необязательно использовать именно алгоритм, реализованный в рамках решения задачи E.

Четвертый модуль

ДЗ 1-1: Деревья поиска — до 23:59:59 20 апреля. По техническим причинам посылки до вечера 10.04 более недоступны, большая просьба пересдать их. Дедлайн продлен до 20 апреля, приносим свои извинения.

ДЗ 1-2: Хеши и динамическое программирование — до 23:59:59 23 апреля.

ДЗ 1-3: Обход в глубину — до 23:59:59 7 мая.

ДЗ 2-1: Обход в ширину и алгоритм Дейкстры — до 23:59:59 7 июня.

ДЗ 2-2: Алгоритм Флойда, остовные деревья, потоки — до 23:59:59 16 июня. Для получения максимальной оценки достаточно решить любые 8 задач.

Контрольные работы

Тренировочный вариант мартовской контрольной работы

В четвертом модуле контрольная работа пройдет в конце апреля.

Экзамен

В конце четвертого модуля пройдет письменный экзамен. На экзамене можно пользоваться бумажными материалами и нельзя — электронными.

Задачи на конечные автоматы для подготовки к экзамену.

Консультация: 23 июня, 16:40, ауд. 205.

Задачи экзамена 24 июня 2017 г.

Оценка

Накопленная оценка формируется на основе оценки за контрольную работу (20%), оценок за два домашних задания (по 30%) и оценки за аудиторную работу (20%). Накопленная оценка составляет 70% от итоговой оценки, остальное (30%) — экзамен. Все округления — на усмотрение преподавателя.

Страницы семинаров

группа 167-1

Преподаватели и ассистенты

Подгруппа Преподаватель Учебные ассистенты Расписание занятий
162-1 lagutube [download lagu] Пн, пт (ауд. 513): 13:40 – 15:00
162-2 Филипп Синицын Арсений Турышев Пн (ауд. 513), чт (ауд. 301): 9:00 – 10:20
164-1 Федор Строк Валерия Бубнова Ср (ауд. 412): 9:00 – 11:50
164-2 Илья Макаров Валерия Бубнова Вт (ауд. 505): 13:40 – 15:00; чт (ауд. 327): 15:10 – 16:30
165-1 Евгений Салагаев Юрий Баранов Пн (ауд. 503): 9:00 – 10:20; чт (ауд. 505): 10:30 – 11:50
165-2 Иван Фефер Юрий Баранов Ср (ауд. 327): 9:00 – 10:20; чт (ауд. 420): 10:30 – 11:50
166-1 Ярослав Кищенко Дарья Вальтер Ср (ауд. 301): 10:30 – 11:50; чт (ауд. 327): 9:00 – 10:20
166-2 Михаил Густокашин Дарья Вальтер Пн (ауд. 301), чт (ауд. 501): 13:40 – 15:00
167-1 Алексей Умнов Максим Рябинин Пн, ср (ауд. 503): 13:40 – 15:00
167-2 Михаил Чичварин Максим Рябинин Ср (ауд. 605), чт (ауд. 513): 10:30 – 11:50
168-1 Михаил Дектярев Арсений Турышев Ср (ауд. 416), чт (ауд. 501): 10:30 – 11:50
168-2 Ольга Абакумова Петр Жижин Ср (ауд. 327): 10:30 – 11:50; чт (ауд. 605): 9:00 – 10:20