АиСД-2 Экзамен — различия между версиями

Текущая версия на 18:41, 12 декабря 2025

с 12.00 до 13.30 - письменная часть - контест из 5 теоретических вопросов по 5 заданий к каждом на Яндекс контесте. Каждое задание оценивается независимо в 0,3 балла.

В набор задач войдут задачи из банка задач к экзамену. Экзамен проходит онлайн с подключением к zoom трансляции.

с 14.00 - устная часть экзамена.

В устную часть приглашаются все, кто набрал хотя бы 4,5 балла (15 правильных ответов из 25)

Вы записываетесь на один из доступных временных слотов и подключаетесь по ссылке к zoom На устной части экзамена вам достаётся билет из 3-х вопросов. Вопросы формируются из банка вопросов к экзамену. По каждому вопросу билета экзаменующий может задавать дополнительные вопросы.

Банк задач и вопросов к экзамену:

Банк заданий и вопросов к экзамену состоит из открытой и закрытой части в отношении 80/20. Открытая часть размещается в свободном доступе не позднее 13 декабря.

Оценка за экзамен:

Каждое задание вопроса оценивается независимо в 0,3 балла (max = 7,5сза все задания)

Ответ на каждый вопрос устной части оценивается в баллах от 0 до 1,5 с шагом 0,5 (max = 4,5)

Итоговая оценка = min(10, контест + устный ответ)

Вопросы к письменной части экзамена по АиСД, 2 модуль

Тема B "Теория чисел"

Алгоритм Евклида

1. Какое минимальное количество шагов (делений с остатком) требуется алгоритму Евклида для вычисления НОД(34, 21)?
2. Напишите пропущенную строку в итеративной реализации алгоритма Евклида на Python:

   def gcd(a, b):
       while b != 0:
           pass
       return a

1. Напишите формулу нахождения НОК натуральных чисел a, b используя функцию нахождения НОД двух чисел - gcd(a, b).
2. Напишите оценку по времени в O нотации для алгоритма нахождения НОД для чисел a и b
3. Для решения задачи "Полоска бумаги имеет размеры A × B. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?" Использовали реализацию алгоритма Евклида с вычитанием. Напишите условие, которое позволит сократить решение задачи для тестов, где одно из входных чисел очень велико, а другое равно 1.

   n, m = map(int, input().split())
   k = 1

   else:
       while n != m:
           k += 1
           if n > m:
              n-= m
           else:
               m-= n
       print(k)

Вопросы к устной части экзамена по АиСД, 2 модуль

Тема "Алгоритмы: классификация, сложность"

Тема "Теория чисел"

Тема "Линейный поиск в массиве данных"

Тема "Структуры данных: множества, словари, стеки, деки, очереди"

Тема "Жадные алгоритмы"

Тема "Обработка событий"

Тема "Бинарный поиск"

Тема "Квадратичные сортировки"

Тема "Комбинаторные рекурсивные алгоритмы"

Тема "Рекурсивные сортировки: быстрая сортировка, сортировка слиянием"

Тема "Структура данных - куча. Пирамидальная сортировка"

Тема "Динамическое программирование"