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

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

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

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

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

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

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

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

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

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

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

• 1 задача - 1 балл
• 2 задачи - 3 балла
• 3 задачи - 5 баллов
• 4 задачи - 7 баллов
• 5 задач - 10 баллов
• 6 задач и более - 10 баллов и счастливая улыбка преподавателя :)

Перевод в итоговый балл: 1 первичный балл = 0,2 итоговых баллов.

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

После проведения КР будет проведена проверка работы на самостоятельное решение, для исключение списывания или использования LLM. Списанные работы аннулируются полностью.

Как подтвердить самостоятельность выполнения работы?

Во время КР нужно сделать запись экрана и после выложить её на файлообменник, загрузить ссылку в форму сдачи работы.

Для участия вам потребуется компьютер с веб-камерой и микрофоном (в частности, все современные ноутбуки оборудованы ими) и выходом в интернет.

Рекомендуем, но это не единственный способ:

• Вам необходимо установить OBS Studio по ссылке https://obsproject.com/ru
• Вам необходимо настроить три источника входных потоков: микрофон, веб-камера и захват экрана.
• За 5 минут до начала работы начните запись. Ваши видео будут просмотрены только преподавателями и ассистентами.
• Записанные видео нужно сдать в течение часа после окончания написания защиты
• Видео не удаляйте пока не будет оценки!
• Во время работы разрешается пользоваться:

     - средами разработки (не онлайн), с отключенными AI подсказками
     - своими кодами, из домашних или семинарских работ, отправленных в проверяющую систему
     - справочной информацией https://docs.python.org/3/  (https://docs.python.org/3/)

• нужно ОБЯЗАТЕЛЬНО в начале сделать такую вещь, показать и оно запишется

      - на unix-like системах (macOS, Linux) - полный вывод команды cat /proc/cpuinfo (если у кого-то на маке не работают через cat, то вот  команда ioreg -l | grep -e Manufacturer -e 'Vendor Name')
      - на windows нажать сочетание win + r, ввести msinfo32 и показать все что написано в окне

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