Алгоритмы и структуры данных - 1 2024/2025 4 модуль (ЭАД КНАД ВСН)

Лектор: Куренков Владимир Вячеславович

Ссылка на объявления по курсу

Ссылка на чат курса ЭАД

Ссылка на чат курса КНАД + СмолГУ

Ссылка на чат курса ВСН

Лекции и ДЗ

№	Дата	Тема	ДЗ	Дедлайн
1	01.04	Представление сетей в компьютере. Матрица смежности. Список смежности. Список ребер.	ДЗ-0	13.04
2	04.04	Обход в глубину. Связность. Поиск компонент связности в графе.	ДЗ-1	16.04
3	08.04	Обход в глубину. Проверка графа на двудольность. Диаметр и центр дерева. Поиск цикла в графе.	ДЗ-2	20.04
4	11.04	Обход в глубину. Мосты. Точки сочленения. Топологическая сортировка.	ДЗ-3	25.04
5	15.04	Задача построения дерева кратчайших расстояний: Обход в ширину.	ДЗ-4	29.04
6	18.04	Алгоритм Дейкстры.	ДЗ-5	06.05
7	22.04	Алгоритм Форда-Беллмана. Алгоритм Левита.	-	-
8	25.04	Алгоритм Флойда.	ДЗ-6	14.05
9	29.04	Базовая геометрия. Векторное и скалярное произведение векторов.	ДЗ-7	01.06
		Повтор материала. Подготовка к КР	ДЗ-8	22.05
10	13.05	Задача объединить-найти. Система не пересекающихся множеств. Алгоритм Краскала.	ДЗ-9	28.05
11	16.05	Контрольная работа. (ДЗ.0 — ДЗ.6)	-	-
12	20.05	Дерево отрезков.	ДЗ-10	04.06
13	23.05	Дерево отрезков. Операции на отрезках.	ДЗ-11	08.06
14	27.05	LCA. Метод двоичных подъёмов.	ДЗ-12	13.06
15	30.05	Деревья поиска. Добавление, удаление элемента.	-	-
16	03.06	Декартово дерево по явному ключу.	-	-
17	06.06	Декартово дерево по не явному ключу.	ДЗ-13	22.06
18	10.06	Дерево Фенвика.	-	-
19	13.06	Задача построения стабильного бракосочетания.	-	-
20	17.06	Повтор пройденного материала. Разбор экзаменационного демо-варианта.	-	-

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

Группа	БЭАД241	БЭАД242	БЭАД243	БЭАД244	БЭАД245	БЭАД246	КНАД-1	КНАД-2	ВСН-1	ВСН-2	СмолГУ-1	СмолГУ-2
Лектор	Владимир Куренков
Семинарист	Илья Самоненко	Владимир Куренков					Мария Горденко	Данил Мячин	Каймаков Кирилл		[]	[]
Ассистент	Даниил Винер	Артур Ким	Вероника Дмитренко	Нарек Хоранян	Владислав Веселов	Иван Долгих	[Даниил Котляров]	Иван Латышев	Сергей Павлухин	Мария Масленникова	Григорий Чайковский	Виктор Пентюхов

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

После лекции выдается контест, как правило, состоящий из 5 - 10 задач. Дедлайн — в 23:59, дня, указанного в таблице.

Максимальная оценка за ДЗ — 10 баллов. Все задачи в ДЗ равноценны.

Всего планируется примерно 13 ДЗ. Также выдано одно бонусное ДЗ, которым можно покрыть ДЗ, которое не сдали ранее.

То есть O_ДЗ=min(10; (ДЗ₀ + ДЗ₁ + ... + ДЗ₁₃) / 13)

Контрольная работа

Контрольная работа пройдёт 16 мая в 18.10 и 17 мая в 9.30. Вы можете написать её в любой из этих дней, но только один раз, выбрав удобный для Вас вариант.

На КР будут задачи на такие темы, как:

1. Представление сетей в компьютере
2. DFS + Проверка на двудольность + Поиск цикла
3. BFS
4. Алгоритм Дейкстры
5. Алгоритм Беллмана-Форда

Не будет: мостов, точек сочленения, диаметр и центр графа, Флойда.

Во время выполнения контрольной работы предполагается использование прокторинга. Подробнее читайте в Правилах проведения КР

Пересдача

Пересдача КР пройдет 07.06 и 09.06.

Вы можете написать пересдачу только ОДИН раз в любой из этих слотов:

• 07.06 в 11:00
• 09.06 в 13:00

Ссылку на пересдачу и форму для прокторинга пришлем в Telegram-канал непосредственно перед КР

Правила проведения аналогичны правилам проведения КР.

Формула оценки за КР.

1. Если вы не писали КР в первый раз, то Оценка = Оценка за пересдачу
2. Если вы уже писали КР, то Оценка = МАКС(1-я попытка; среднее двух попыток)

Коллоквиум

Коллоквиум пройдет с 09.06 по 15.06.

Сдача коллоквиума подразумевает устный ответ преподавателю на несколько вопросов по алгоритмам и структурам данных. Времени на подготовку не дается. На ответ отводится ~15 минут

Темы для подготовки к коллоквиуму будут объявлены позднее

Экзамен

Экзамен планируется на 25 июня в 12.00 в онлайн формате с использованием прокторинга НИУ ВШЭ.

Подробная информация о темах, а также прокторинге будет объявлена позднее на этом сайте, а также в Telegram-канале

Система оценки

Максимальная оценка за работу на семинаре - 10 баллов.

О_{модуль 4} = 0.4 * О_ДЗ + 0.15 * О_КР + 0.15 * О_коллок + 0.1 * О_сем + 0.2 * О_ЭКЗ

Итоговая оценка за курс рассчитывается по формуле: 0.5 * О_{модуль 2} + 0.5 * О_{модуль 4}

Оценки за 2 и 4 модули идут в формулу неокругленными

Блокирующих элементов контроля нет. Автоматов не предусмотрено

Таблица с оценками

Записи лекций и семинаров

https://disk.yandex.ru/d/SIha-YIf0Ngn3Q

Бонусные баллы

В домашних контестах могут быть задачи со звездочкой, за решение которых Вы можете получить бонусные баллы. Этими баллами можно перезачесть семинарскую оценку, то есть О_сем =max(О_сем; О_{бонуски})

Правила проведения КР

Контрольные мероприятия по АиСД проходят с использованием асинхронного прокторинга. Каждому студенту необходимо записать процесс выполнения заданий защиты с использованием OBS Studio, выложить результат в облачное хранилище и предоставить ссылку на запись.

Перед КР

Для участия вам потребуется:

• Компьютер с веб-камерой и микрофоном (в частности, все современные ноутбуки оборудованы ими) и выходом в интернет.
• Установить OBS Studio по ссылке https://obsproject.com/ru
• Настроить три источника входных потоков: микрофон, веб-камера и захват экрана. Подробнее о настройке в видео
• Отключить все мессенджеры и закрыть лишние вкладки.

Пожалуйста, заранее убедитесь, что вы научились записывать видео в требуемом формате - этот процесс иногда может вызывать проблемы. Все решения проблем, связанных с записью в OBS Studio описаны в интернете. Чтобы записанные файлы не занимали много места, вы можете понизить битрейт: достаточно 500 Kbps для видео и 64 для аудио. Смотрите видео по ссылке выше - там показано, как это настроить.

Видео не удаляйте пока ваш семинарист не проверит запись!

Разрешается использовать

• Сайт тестирующей системы и средами разработки, в том числе онлайн
• Документацию на https://en.cppreference.com/w/

Запрещается

• Общение с другими людьми, заранее предупредите об этом тех людей, которые находятся с вами в месте написания защиты
• Пользоваться наушниками
• Использовать своими посылками в ДЗ
• Общаться с другими участниками до конца тура - оба участника будут дисквалифицированы

Проведение контрольной работы

Действия, которые вы должны совершить до тура:

• Физически отключить и удалить любые электронные устройства и дополнительные мониторы с рабочего места
• Подготовиться к тому, что вы не сможете покидать рабочее место в течение всего времени проведения КР
• Включить запись из трех источников: экран, веб-камера и микрофон в OBS Studio. Убедитесь, что включена запись со всего экрана, а не из отдельного окна. Убедитесь, что микрофон и камера включены.
• Снять свое рабочее место со всех сторон и его окружение
• Показать чистые листы, которые вы планируете использовать во время черновиков

За 5 минут до начала работы начните запись. Опоздавшие студенты (начавшие запись не до начала тура) будут дисквалифицированы по решению семинариста. Ваши видео будут просмотрены только преподавателями и ассистентами.

Порядок действий во время тура

Во время тура возникающие по условиям задач вопросы вы должны задавать через тестирующую систему. Организационные вопросы вы также можете задать через тестирующую систему.

В случае, если вы работаете с черновиком или бумажными конспектами, направьте веб-камеру так, чтобы были видны ваши руки. Не забудьте направить веб-камеру на лицо, когда вы возвращаетесь к работе за компьютером.

Во время тура вы можете получить важные объявления от жюри через тестирующую систему. Уведомления о них появляются в правом верхнем углу в интерфейсе тестирующей системы.

В случае, если вы завершили решение задач раньше окончания защиты, вам необходимо написать об этом сообщение в тестирующей системе и завершить решение задач. В случае попыток решения задач после этого сообщения вы будете дисквалифицированы.

После окончания тура

После окончания тура в течение 4 часов необходимо разместить видео на Яндекс.Диске, Google Drive, dropbox или youtube (позаботьтесь о правилах видимости, иначе прокторинг может не быть засчитан), которое вы записывали в течение тура, в открытом доступе и сдать ссылку на него в специальную форму которую пришлют в чат.

В случае технических проблем с загрузкой видео оперативно пишите лектору