Алгоритмы и структуры данных 1 (ДРИП 24/25): различия между версиями
fix |
|||
| (не показано 11 промежуточных версий этого же участника) | |||
| Строка 7: | Строка 7: | ||
[https://docs.google.com/forms/d/e/1FAIpQLSdl4AYE62oIr7td70knKddl2bhEiNU8OU-FzMuMgS_05uKYtg/viewform Форма для анонимной обратной связи (постоянная)] | [https://docs.google.com/forms/d/e/1FAIpQLSdl4AYE62oIr7td70knKddl2bhEiNU8OU-FzMuMgS_05uKYtg/viewform Форма для анонимной обратной связи (постоянная)] | ||
[https:// | [https://docs.google.com/spreadsheets/d/1R5wezJJvk50Z8uCeyHX3n8OpQuqGJ7YGki-z-0-1fng/edit?hl=ru&gid=1630914914#gid=1630914914 Ведомость курса] | ||
<br> | <br> | ||
| Строка 15: | Строка 15: | ||
|- | |- | ||
| Лектор || colspan="2" | | | Лектор || colspan="2" | | ||
Горденко Мария Константиновна <br> tg: [https://t.me/ | Горденко Мария Константиновна <br> tg: [https://t.me/mgordenko @mgordenko] | ||
|- | |- | ||
| Семинарист || | | Семинарист || | ||
| Строка 26: | Строка 26: | ||
|- | |- | ||
| Ассистенты || colspan="2" | | | Ассистенты || colspan="2" | | ||
Илья Тямин | Илья Тямин, tg: [https://t.me/mrshrimp_it @mrshrimp_it] <br> | ||
Тамирлан Яхьяев | Тамирлан Яхьяев, tg: [https://t.me/alvoro_ty @alvoro_ty] <br> | ||
Федор Князев | Федор Князев, tg: [https://t.me/theknyazev @theknyazev] <br> | ||
|- | |- | ||
} | |} | ||
== Лекции == | == Лекции == | ||
Проводятся по понедельникам с 9:30 до 10:50 и с 13:00 до 14:20. | Проводятся по понедельникам с 9:30 до 10:50 и с 13:00 до 14:20. | ||
'''Лекции 1-2, 09. | === 2 модуль === | ||
'''Лекции 1-2, 02.11.24''' [[https://t.me/c/2329929891/99 презентация], [https://t.me/c/2329929891/97 конспект]]. | |||
Введение в алгоритмы, O-большое (асимптотика), линейный поиск, бинарный поиск | |||
'''Лекции 3-4, 14.11.24''' [[https://t.me/c/2329929891/105 презентация]]. | |||
Квадратичные сортировки: Selection Sort, Insertion Sort, Bubble Sort, условие Айверсона. Линейные сортировки: Counting Sort, понятие устойчивости сортировки, Radix Sort, LSD и MSD модификации Radix Sort. Сортировка Шелла, последовательность Седжвика, сортировка расческой. Порядковые статистики: алгоритм "медиана медиан" (рекурсивный). Понятие скользящего окна. Сортировка событий | |||
'''Лекции 5-6, 18.11.24''' [[https://t.me/c/2329929891/108 презентация]]. | |||
Рекурсия. Задача о Ханойских башнях. Merge Sort. Понятие префиксных сумм. Метод двух указателей. Сканирующая прямая (scanline). Quick Sort (быстрая сортировка). Понятие двоичной кучи. Heap Sort. | |||
'''Лекции 7-8, 25.11.24''' [[https://t.me/c/2329929891/113 презентация]]. | |||
Сортировка Шелла. Последовательности для выборы элементов при сортировке. Сортировка расческой. Порядковые статистики (задача SELECT). Алгоритм "медиана медиан". Повторение: префиксные суммы, scanline. Динамическое программирование. Задача о рюкзаке с вариациями. Задача о шахматном коне. | |||
'''Лекции 9-10, 02.12.24''' [[https://t.me/c/2329929891/123 презентация]]. | |||
Хеш-функция: что это. Хеширование. Коллизии. Открытая и закрытая адресация. Алгоритмы поиска подстроки в строке. Z-функция. КМП (алгоритм Кнута-Мориса-Пратта). Алгоритм Ахо-Корасик. Бор. | |||
'''Лекции 11-12, 09.12.24''' [[https://t.me/c/2329929891/126 презентация]]. | |||
Структуры данных. Stack. Queue. Deque. Связные списки. Разреженные таблицы. Задача RSQ. RMQ без модификаций. Sqrt-декомпозиция. | |||
=== 3 модуль === | |||
'''Лекции 13-14, 13.01.25''' [[https://t.me/c/2329929891/140 презентация]]. | |||
Теория графов: основные понятия. Операции над графами. Варианты хранения графов в памяти. Обходы графов: DFS, BFS. Маршруты. Понятие дерева. Компоненты связности (сильная, слабая). Поиск циклов. Проверка графа на двудольность. Топологическая сортировка графа. | |||
'''Лекции 15-16, 20.01.25''' [[https://t.me/c/2329929891/146 презентация]]. | |||
Мост в графе. Поиск мостов в графе. Алгоритм Косарайю. Алгоритм Тарьяна. Обзор и сравнение | |||
'''Лекции 17-18, 20.01.25''' [[https://t.me/c/2329929891/149 презентация1], [https://t.me/c/2329929891/151 презентация2]]. | |||
Компоненты сильной связности. Алгоритм Косарайю. Алгоритм Тарьяна. Минимальные остовы: алгоритм Прима, алгоритм Краскала. | |||
'''Лекция 19-20, 03.02.25''' [[https://t.me/c/2329929891/151 презентация1]]. | |||
Минимальные остовы: алгоритм Прима, алгоритм Краскала. Системы непересекающихся множеств. | |||
'''Лекция 20-21, 10.02.25''' [[https://t.me/c/2329929891/156 презентация]]. | |||
Кратчайшие пути в графе: алгоритм Дейкстры, Форда-Белмана, Флойда-Уоршелла. | |||
'''Лекция 22-23, 24.02.25''' [[https://t.me/c/2329929891/159 презентация]]. | |||
Потоки. Максимальный поток. Минимальный разрез. Многополюсная сеть. Максимальный поток минимальной стоимости. Алгоритм Диницы | |||
== Домашние задания == | == Домашние задания == | ||
| Строка 53: | Строка 90: | ||
| 3 || [https:///official.contest.yandex.ru/contests/71547/enter ДЗ-3] || 27.11.2024 23:59 | | 3 || [https:///official.contest.yandex.ru/contests/71547/enter ДЗ-3] || 27.11.2024 23:59 | ||
|- | |- | ||
| 4 || [https:///official.contest.yandex.ru/contests/71549/enter ДЗ-4] || | | 4 || [https:///official.contest.yandex.ru/contests/71549/enter ДЗ-4] || 05.12.2024 23:59 | ||
|- | |||
| 5 || [https:///official.contest.yandex.ru/contests/67984/enter ДЗ-5] || 12.12.2024 23:59 | |||
|- | |||
| 6 || [https:///official.contest.yandex.ru/contests/67985/enter ДЗ-6] || 19.12.2024 23:59 | |||
|- | |||
| 7 || [https://official.contest.yandex.ru/contest/71552/standings ДЗ-7] || 20.01.2025 23:59 | |||
|- | |||
| 8 || [https://official.contest.yandex.ru/contest/73990/enter/?retPage=standings ДЗ-8] || 27.01.2025 23:59 | |||
|- | |||
| 9 || [https://official.contest.yandex.ru/contest/73991 ДЗ-9] || 10.02.2025 23:59 | |||
|- | |- | ||
| | | 10 || [https://official.contest.yandex.ru/contest/73992 ДЗ-10] || 10.02.2025 23:59 | ||
|- | |- | ||
| | | 11 || [https://official.contest.yandex.ru/contest/73993 ДЗ-11] || 17.02.2025 23:59 | ||
|- | |- | ||
| | | 12 || [https://official.contest.yandex.ru/contest/73994 ДЗ-12] || 03.03.2025 23:59 | ||
|} | |} | ||
== Оценки == | == Оценки == | ||
[ | [https://docs.google.com/spreadsheets/d/1R5wezJJvk50Z8uCeyHX3n8OpQuqGJ7YGki-z-0-1fng/edit?hl=ru&gid=1630914914#gid=1630914914 Ведомость курса] | ||
Оценка за курс считается как 0.3*КР + 0.3*ДЗ + 0.1*Активность + 0.3*Экзамен. | Оценка за курс считается как 0.3*КР + 0.3*ДЗ + 0.1*Активность + 0.3*Экзамен. | ||
Округление арифметическое и осуществляется только для итоговой оценки. <br> Оценки за контрольную работу и за экзамен являются '''блокирующими'''. | Округление арифметическое и осуществляется только для итоговой оценки. <br> Оценки за контрольную работу и за экзамен являются '''блокирующими'''. | ||
== Контрольная работа == | == Контрольная работа == | ||
Пройдет 11 января 2025 года в аудитории G411 в формате коллоквиума. Список вопросов для подготовки и задач на платформе Leetcode доступен в чате в телеграме. | |||
== Экзамен == | == Экзамен == | ||
TBA | TBA | ||
Текущая версия от 22:57, 1 марта 2025
Основная информация
Курс читается на 1 курсе в 2-3 модуле на программе ДРИП.
Форма для анонимной обратной связи (постоянная)
| Группа | 241 | 242 |
|---|---|---|
| Лектор |
Горденко Мария Константиновна | |
| Семинарист |
Мария Горденко |
Никита Майнуленко |
| Ассистенты |
Илья Тямин, tg: @mrshrimp_it | |
Лекции
Проводятся по понедельникам с 9:30 до 10:50 и с 13:00 до 14:20.
2 модуль
Лекции 1-2, 02.11.24 [презентация, конспект].
Введение в алгоритмы, O-большое (асимптотика), линейный поиск, бинарный поиск
Лекции 3-4, 14.11.24 [презентация].
Квадратичные сортировки: Selection Sort, Insertion Sort, Bubble Sort, условие Айверсона. Линейные сортировки: Counting Sort, понятие устойчивости сортировки, Radix Sort, LSD и MSD модификации Radix Sort. Сортировка Шелла, последовательность Седжвика, сортировка расческой. Порядковые статистики: алгоритм "медиана медиан" (рекурсивный). Понятие скользящего окна. Сортировка событий
Лекции 5-6, 18.11.24 [презентация].
Рекурсия. Задача о Ханойских башнях. Merge Sort. Понятие префиксных сумм. Метод двух указателей. Сканирующая прямая (scanline). Quick Sort (быстрая сортировка). Понятие двоичной кучи. Heap Sort.
Лекции 7-8, 25.11.24 [презентация].
Сортировка Шелла. Последовательности для выборы элементов при сортировке. Сортировка расческой. Порядковые статистики (задача SELECT). Алгоритм "медиана медиан". Повторение: префиксные суммы, scanline. Динамическое программирование. Задача о рюкзаке с вариациями. Задача о шахматном коне.
Лекции 9-10, 02.12.24 [презентация].
Хеш-функция: что это. Хеширование. Коллизии. Открытая и закрытая адресация. Алгоритмы поиска подстроки в строке. Z-функция. КМП (алгоритм Кнута-Мориса-Пратта). Алгоритм Ахо-Корасик. Бор.
Лекции 11-12, 09.12.24 [презентация].
Структуры данных. Stack. Queue. Deque. Связные списки. Разреженные таблицы. Задача RSQ. RMQ без модификаций. Sqrt-декомпозиция.
3 модуль
Лекции 13-14, 13.01.25 [презентация].
Теория графов: основные понятия. Операции над графами. Варианты хранения графов в памяти. Обходы графов: DFS, BFS. Маршруты. Понятие дерева. Компоненты связности (сильная, слабая). Поиск циклов. Проверка графа на двудольность. Топологическая сортировка графа.
Лекции 15-16, 20.01.25 [презентация].
Мост в графе. Поиск мостов в графе. Алгоритм Косарайю. Алгоритм Тарьяна. Обзор и сравнение
Лекции 17-18, 20.01.25 [презентация1, презентация2].
Компоненты сильной связности. Алгоритм Косарайю. Алгоритм Тарьяна. Минимальные остовы: алгоритм Прима, алгоритм Краскала.
Лекция 19-20, 03.02.25 [презентация1].
Минимальные остовы: алгоритм Прима, алгоритм Краскала. Системы непересекающихся множеств.
Лекция 20-21, 10.02.25 [презентация].
Кратчайшие пути в графе: алгоритм Дейкстры, Форда-Белмана, Флойда-Уоршелла.
Лекция 22-23, 24.02.25 [презентация].
Потоки. Максимальный поток. Минимальный разрез. Многополюсная сеть. Максимальный поток минимальной стоимости. Алгоритм Диницы
Домашние задания
Проводятся в системе Яндекс.Контест. Для решения задач необходимо использовать выданные на корпоративную почту логины и пароли.
После окончания срока сдачи, все посылки, получившие статус AC (accepted for testing), будут проверены ассистентом, после чего будет выставлен полный или частичный балл.
| № | Ссылка | Дедлайн сдачи |
|---|---|---|
| 1 | ДЗ-1 | 13.11.2024 23:59 |
| 2 | ДЗ-2 | 20.11.2024 23:59 |
| 3 | ДЗ-3 | 27.11.2024 23:59 |
| 4 | ДЗ-4 | 05.12.2024 23:59 |
| 5 | ДЗ-5 | 12.12.2024 23:59 |
| 6 | ДЗ-6 | 19.12.2024 23:59 |
| 7 | ДЗ-7 | 20.01.2025 23:59 |
| 8 | ДЗ-8 | 27.01.2025 23:59 |
| 9 | ДЗ-9 | 10.02.2025 23:59 |
| 10 | ДЗ-10 | 10.02.2025 23:59 |
| 11 | ДЗ-11 | 17.02.2025 23:59 |
| 12 | ДЗ-12 | 03.03.2025 23:59 |
Оценки
Оценка за курс считается как 0.3*КР + 0.3*ДЗ + 0.1*Активность + 0.3*Экзамен.
Округление арифметическое и осуществляется только для итоговой оценки.
Оценки за контрольную работу и за экзамен являются блокирующими.
Контрольная работа
Пройдет 11 января 2025 года в аудитории G411 в формате коллоквиума. Список вопросов для подготовки и задач на платформе Leetcode доступен в чате в телеграме.
Экзамен
TBA