Контрольная работа АиСД 4 2025/2026

Контрольная работа проводится на лекционной паре 27.04.2026 с 11:10 по 12:30 в формате контеста.

Ссылка на вход: https://official.contest.yandex.ru/contest/93618/enter/

На контесте будет 5-8 задач по темам:

• Представление графов в компьютере. Матрица смежности. Список смежности. Список ребер.
• Проверка графа на связность, выделение компонент связности, проверка на двудольность с помощью одного из алгоритмов обхода графа
• Построение дерева, нахождение диаметра и центра дерева
• Поиск и восстановление цикла в графе (ориентированный и неориентированный вариант)
• Топологическая сортировка ориентированного графа
• Алгоритм поиска в ширину, нахождение рёберно-кратчайшего расстояния
• Поиск кратчайшего пути во взвешенном графе

Чем можно пользоваться во время работы?

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

Чем нельзя пользоваться во время работы?

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

Не путайте с системой автодополнения кода (когда по нажатию, например CTRL + пробел, у вас дописывается оператор или функция). Автодополнение можно.

Нельзя привлекать других людей для решения задач контрольной работы.

Нельзя использовать чужой код решения задач, в том числе сохранённый заранее. Т.е. нельзя накачать себе решения задач на графы и доставать "из кармашка". Можно брать свои решения из ДЗ и семинаров и можно заранее написанные базовые реализации алгоритмов (DFS, BFS, Дейкстра, Флойда, Форда-Беллмана).

Критерии оценки

Для оценки принимаются только задачи, которые прошли все тесты и получили вердикт ОК. Баллы не зависят от сложности задачи, оценивается количество решенных задач.

1 задача - 1 балл 2 задачи - 3 балла 3 задачи - 5 баллов 4 задачи - 7 баллов 5 задач - 10 баллов 6 задач и более - 10 баллов и счастливая улыбка преподавателя :) Перевод в итоговый балл: 1 первичный балл = 0,2 итоговых баллов.

Во время выполнения работы будет доступна таблица результатов.