https://wikicshse.ru/index.php?action=history&feed=atom&title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%BD%D0%B0_%D0%9F%D0%9C%D0%98_%28%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%BE%D0%B9_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%29
Алгоритмы и структуры данных на ПМИ (основной поток) - История изменений
2026-06-06T15:11:04Z
История изменений этой страницы в вики
MediaWiki 1.45.3
https://wikicshse.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%BD%D0%B0_%D0%9F%D0%9C%D0%98_(%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%BE%D0%B9_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA)&diff=945&oldid=prev
imported>Lagutube: link death
2021-08-31T06:37:31Z
<p>link death</p>
<p><b>Новая страница</b></p><div>'''Лектор:''' [http://www.hse.ru/staff/obiedkov С. Объедков]<br />
<br />
'''[Оценки https://docs.google.com/spreadsheets/d/1xtmTV9_jYmGj34_sr1EqTKqrRji3J-1dpRIoHB7H7kc/pubhtml]<br />
<br />
'''Расписание лекций:'''<br/><br />
понедельник 10:30 – 11:50, ауд. 622<br/><br />
четверг 12:10 – 13:30, ауд. 622<br />
<br />
'''Консультации (по предварительной договоренности):'''<br/><br />
понедельник 18:00 – 20:00, к. 324<br/><br />
четверг 16:30 – 18:00, к. 324<br />
<br />
== Рекомендуемая литература ==<br />
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']<br />
# Клейнберг, Тардос. ''Алгоритмы. Разработка и применение''<br />
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''<br />
# Также см. [https://www.dropbox.com/sh/5lxaheg89isd6h9/AACOa50ihgNiu46YqhguwmDBa/algo_16-17_1course_standart.pdf конспекты].<br />
# [https://syarifsoden.blogspot.com ,основные учебники по программированию, ноутбук экран рекордер приложение ]<br />
<br />
== Лекции ==<br />
<br />
=== Третий модуль ===<br />
<br />
* '''12 января.''' Постановка задачи поиска медианы. Простые решения этой задачи. Оценка сложности алгоритмов по времени и памяти. ''О''-, ''o''-, Ω-, ω-, Θ-обозначения. Время работы в худшем, лучшем и среднем случаях. Сортировка вставками.<br />
* '''19 января.''' Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема.<br />
* '''26 января.''' Быстрая сортировка. Оптимальность сортировки слиянием.<br />
* '''2 февраля.''' Разделяй и властвуй: быстрое возведение в степень по модулю, выбор порядковой статистики за время ''O''(''n'') — рандомизированный и детерминированный алгоритмы.<br />
* '''9 февраля.''' Структуры данных. Массив с операциями инициализации, чтения и записи, выполняемыми за время ''O''(1). Структура данных для быстрого поиска и вставки на основе нескольких отсортированных массивов. Амортизационный анализ: групповой анализ и банковский метод (на примере двоичного счетчика).<br />
* '''16 февраля.''' Амортизационная стоимость операций в динамическом массиве. Реализация стека при помощи массива; нахождение максимального значения в стеке за константное время.<br />
* '''2 марта.''' Реализация очереди при помощи связного списка и при помощи массива; нахождение минимального элемента в очереди за константное время. Приоритетная очередь, ее реализация при помощи двоичной кучи. Сортировка кучей.<br />
* '''9 марта.''' Деревья поиска. Алгоритм построения двоичного дерева поиска. Сложность поиска в двоичном дереве поиска. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой. Сбалансированные деревья поиска. Определение красно-черного дерева.<br />
* '''16 марта.''' Красно-черные деревья. Удаление узла из двоичного дерева поиска.<br />
* '''23 марта.''' Деревья отрезков. Динамические порядковые статистики. <br />
<br />
=== Четвертый модуль ===<br />
<br />
* '''3 апреля.''' Хеш-таблицы. Методы задания хеш-функций. Разрешение коллизий при помощи цепочек. Открытая адресация.<br />
* '''6 апреля.''' Сложность операций для открытой адресации в среднем случае. Универсальное хеширование. Двухуровневое идеальное хеширование.<br />
* '''10 апреля.''' Самоорганизующиеся списки и конкурентный анализ онлайн-алгоритмов.<br />
* '''13 апреля.''' Динамическое программирование: выравнивание абзаца по ширине. Свойства задач, эффективно решаемых при помощи динамического программирования: наличие полиномиального числа подзадач, выразимость исходной задачи в терминах подзадач, сводимость больших подзадач к полиномиальному числу меньших подзадач. Вычисление редакционного расстояния и выравнивание последовательностей.<br />
* '''17 апреля.''' Динамическое программирование на деревьях: нахождение независимого множества максимального веса в дереве. Задача о рюкзаке: жадный приближенный алгоритм; псевдополиномиальный алгоритм, основанный на динамическом программировании; приближенная схема полиномиального времени.<br />
* '''20 апреля.''' Графы. Способы представления графов: матрица смежности и списки смежности. Обход графа в глубину и ширину. Поиск компонент связности в неориентированном графе.<br />
* '''24 апреля.''' Топологическая сортировка за линейное время: алгоритмы, основанные на удалении вершин без входящих ребер и на поиске в глубину.<br />
* '''27 апреля.''' Алгоритм проверки сильной связности ориентированного графа. Вычисление компонент сильной связности в ориентированном графе.<br />
* '''11 мая.''' Поиск путей возведением в степень матрицы смежности графа. Алгоритм Флойда – Уоршелла: формулировка в терминах динамического программирования, оценка сложности, оптимизация по памяти, обнаружение циклов с отрицательным весом, восстановление кратчайших путей.<br />
* '''15 мая.''' Алгоритм Беллмана – Форда. Алгоритм Дейкстры.<br />
* '''18 мая.''' Минимальные остовные деревья. Алгоритм Крускала, алгоритм Прима.<br />
* '''25 мая.''' Система непересекающихся множеств.<br />
* '''27 мая.''' Максимальный поток. Алгоритм Форда – Фалкерсона.<br />
* '''29 мая.''' Полиномиальный вариант алгоритма Форда – Фалкерсона (с поиском "широких" увеличивающих путей).<br />
* '''1 июня.''' Алгоритм Эдмондса – Карпа. Алгоритм Диница. Двойственность задач о максимальном потоке и минимальном разрезе. Минимальный разрез в неориентированном графе. Алгоритм Каргера.<br />
* '''5 июня.''' Конечные автоматы. Регулярные языки. Замкнутость регулярных языков по дополнению, пересечению и объединению. Минимизация конечного автомата.<br />
* '''8 июня.''' Регулярные выражения. Недетерминированные конечные автоматы. Эквивалентность детерминированных и недетерминированных конечных автоматов. Замкнутость регулярных языков относительно регулярных операций. Построение конечного автомата по регулярному выражению.<br />
* '''9 июня.''' Эквивалентность регулярных выражений и конечных автоматов. Нерегулярные языки. Лемма о накачке.<br />
<br />
== Домашние задания ==<br />
<br />
===Третий модуль===<br />
<br />
[https://official.contest.yandex.ru/contest/3855 Сортировки] — до 12 февраля. Для решения задачи F необязательно использовать именно алгоритм, реализованный в рамках решения задачи E.<br />
<br />
===Четвертый модуль===<br />
<br />
ДЗ 1-1: [https://official.contest.yandex.ru/contest/4322 Деревья поиска] — до 23:59:59 20 апреля. По техническим причинам посылки до вечера 10.04 более недоступны, большая просьба пересдать их. Дедлайн продлен до 20 апреля, приносим свои извинения.<br />
<br />
ДЗ 1-2: [https://official.contest.yandex.ru/contest/4381 Хеши и динамическое программирование] — до 23:59:59 23 апреля.<br />
<br />
ДЗ 1-3: [https://official.contest.yandex.ru/contest/4445 Обход в глубину] — до 23:59:59 7 мая.<br />
<br />
ДЗ 2-1: [https://official.contest.yandex.ru/contest/4561 Обход в ширину и алгоритм Дейкстры] — до 23:59:59 7 июня.<br />
<br />
ДЗ 2-2: [https://official.contest.yandex.ru/contest/4602 Алгоритм Флойда, остовные деревья, потоки] — до 23:59:59 16 июня. Для получения максимальной оценки достаточно решить любые 8 задач.<br />
<br />
== Контрольные работы ==<br />
[https://www.dropbox.com/s/p3nlzn6fyhdi1ll/algo-quiz1-sample.pdf?dl=0 Тренировочный вариант] мартовской контрольной работы<br />
<br />
В четвертом модуле контрольная работа пройдет в конце апреля.<br />
<br />
== Экзамен ==<br />
<br />
В конце четвертого модуля пройдет письменный экзамен. На экзамене можно пользоваться бумажными материалами и нельзя — электронными.<br />
<br />
[https://www.dropbox.com/s/0gzo35d1vv9s6ey/regular.pdf?dl=0 Задачи на конечные автоматы] для подготовки к экзамену.<br />
<br />
Консультация: 23 июня, 16:40, ауд. 205.<br />
<br />
[https://www.dropbox.com/s/9gd8o29w7rjgwot/algo-exam2017.pdf?dl=0 Задачи] экзамена 24 июня 2017 г.<br />
<br />
== Оценка ==<br />
Накопленная оценка формируется на основе оценки за контрольную работу (20%), оценок за два домашних задания (по 30%) и оценки за аудиторную работу (20%). Накопленная оценка составляет 70% от итоговой оценки, остальное (30%) — экзамен. Все округления — на усмотрение преподавателя. <br />
<br />
== Страницы семинаров ==<br />
<br />
[[АиСД_167-1|группа 167-1]]<br />
<br />
==Преподаватели и ассистенты==<br />
{| class="wikitable"<br />
|-<br />
! Подгруппа !! Преподаватель !! Учебные ассистенты !! Расписание занятий<br />
|-<br />
| 162-1 || [https://lagutube.com lagutube] || [download lagu] || '''Пн''', '''пт''' (ауд. 513): 13:40 – 15:00<br />
|-<br />
| 162-2 || [https://www.hse.ru/org/persons/174481011 Филипп Синицын] || [mailto:arture226@gmail.com Арсений Турышев] || '''Пн''' (ауд. 513), '''чт''' (ауд. 301): 9:00 – 10:20<br />
|-<br />
| 164-1 || [https://www.hse.ru/staff/fstrok Федор Строк] || [mailto:lera-bubnova@yandex.ru Валерия Бубнова] || '''Ср''' (ауд. 412): 9:00 – 11:50<br />
|-<br />
| 164-2 || [http://www.hse.ru/staff/iamakarov Илья Макаров] || [mailto:lera-bubnova@yandex.ru Валерия Бубнова] || '''Вт''' (ауд. 505): 13:40 – 15:00; '''чт''' (ауд. 327): 15:10 – 16:30<br />
|-<br />
| 165-1 || [https://www.hse.ru/org/persons/137640594 Евгений Салагаев] || [mailto:yuabaranov@edu.hse.ru Юрий Баранов] || '''Пн''' (ауд. 503): 9:00 – 10:20; '''чт''' (ауд. 505): 10:30 – 11:50<br />
|-<br />
| 165-2 || [https://www.hse.ru/org/persons/192085992 Иван Фефер] || [mailto:yuabaranov@edu.hse.ru Юрий Баранов] || '''Ср''' (ауд. 327): 9:00 – 10:20; '''чт''' (ауд. 420): 10:30 – 11:50<br />
|-<br />
| 166-1 || Ярослав Кищенко || [mailto:dasha-walter@yandex.ru Дарья Вальтер] || '''Ср''' (ауд. 301): 10:30 – 11:50; '''чт''' (ауд. 327): 9:00 – 10:20<br />
|-<br />
| 166-2 || [http://www.hse.ru/org/persons/133408680 Михаил Густокашин] || [mailto:dasha-walter@yandex.ru Дарья Вальтер] || '''Пн''' (ауд. 301), '''чт''' (ауд. 501): 13:40 – 15:00<br />
|-<br />
| 167-1 || [http://www.hse.ru/org/persons/141880775 Алексей Умнов] || [mailto:mkryabinin@edu.hse.ru Максим Рябинин] || '''Пн''', '''ср''' (ауд. 503): 13:40 – 15:00<br />
|-<br />
| 167-2 || [https://www.hse.ru/org/persons/161006240 Михаил Чичварин] || [mailto:mkryabinin@edu.hse.ru Максим Рябинин] || '''Ср''' (ауд. 605), '''чт''' (ауд. 513): 10:30 – 11:50<br />
|-<br />
| 168-1 || [http://www.hse.ru/org/persons/138215687 Михаил Дектярев] || [mailto:arture226@gmail.com Арсений Турышев] || '''Ср''' (ауд. 416), '''чт''' (ауд. 501): 10:30 – 11:50<br />
|-<br />
| 168-2 || Ольга Абакумова || [mailto:piter.zh@gmail.com Петр Жижин] || '''Ср''' (ауд. 327): 10:30 – 11:50; '''чт''' (ауд. 605): 9:00 – 10:20 <br />
|-<br />
|}</div>
imported>Lagutube