Алгоритмы и структуры данных 1 (ДРИП 24/25) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Основная информация)
(→‎Домашние задания)
 
(не показано 7 промежуточных версии этого же участника)
Строка 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://yandex.ru Ведомость курса]
+
[https://docs.google.com/spreadsheets/d/1R5wezJJvk50Z8uCeyHX3n8OpQuqGJ7YGki-z-0-1fng/edit?hl=ru&gid=1630914914#gid=1630914914 Ведомость курса]
 
<br>
 
<br>
  
Строка 35: Строка 35:
 
Проводятся по понедельникам с 9:30 до 10:50 и с 13:00 до 14:20.
 
Проводятся по понедельникам с 9:30 до 10:50 и с 13:00 до 14:20.
  
−
  '''Лекции 1-2, 09.09.24''' [[https://t.me/c/2329929891/7 презентация], [https://t.me/c/2329929891/5 конспект]].  
+
=== 2 модуль ===
−
TBA
+
 
 +
  '''Лекции 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] || TBA
+
| 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
 
|-
 
|-
−
| 5 || [https:///official.contest.yandex.ru/contests/67984/enter ДЗ-5] || TBA
+
| 10 || [https://official.contest.yandex.ru/contest/73992 ДЗ-10] || 10.02.2025 23:59
 
|-
 
|-
−
| 6 || [https:///official.contest.yandex.ru/contests/67985/enter ДЗ-6] || TBA
+
| 11 || [https://official.contest.yandex.ru/contest/73993 ДЗ-11] || 17.02.2025 23:59
 
|-
 
|-
−
| 7 || [https:///official.contest.yandex.ru/contests/67986/enter ДЗ-7] || TBA
+
| 12 || [https://official.contest.yandex.ru/contest/73994 ДЗ-12] || 03.03.2025 23:59
 
|}
 
|}
  
 
== Оценки ==
 
== Оценки ==
−
[TBA Ведомость курса]
+
[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> Оценки за контрольную работу и за экзамен являются '''блокирующими'''.
  
 
== Контрольная работа ==
 
== Контрольная работа ==
−
TBA
+
Пройдет 11 января 2025 года в аудитории G411 в формате коллоквиума. Список вопросов для подготовки и задач на платформе Leetcode доступен в чате в телеграме.
  
 
== Экзамен ==
 
== Экзамен ==
 
TBA
 
TBA

Текущая версия на 01:57, 2 марта 2025

Основная информация

Курс читается на 1 курсе в 2-3 модуле на программе ДРИП.

Чат курса в телеграм

Форма для анонимной обратной связи (постоянная)

Ведомость курса

Группа 241 242
Лектор

Горденко Мария Константиновна
tg: @mgordenko

Семинарист

Мария Горденко
tg: @mgordenko
Пн 11:10-12:30, 14:40-16:00

Никита Майнуленко
tg: @Ni_Mans
Пт 09:30-12:30

Ассистенты

Илья Тямин, tg: @mrshrimp_it
Тамирлан Яхьяев, tg: @alvoro_ty
Федор Князев, tg: @theknyazev

Лекции

Проводятся по понедельникам с 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

Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_1_(ДРИП_24/25)&oldid=89964»