Вопросы к устному зачёту

Процедура приёма зачёта

Оценка по информатике ставится в результате устного ответа на дифференцированном зачёте.

Сдача происходит по билетам. В билете содержится два вопроса из основного списка. На подготовку студенту отводится не более 20 минут. Преподаватель слушает ответы на вопросы в билете, а также может задать дополнительные вопросы.

Список вопросов

Теория

  1. Ссылочная модель данных в Python. Изменяемые и неизменяемые типы данных. Проблема копирования.
  2. Операторы присваивания в Python. Множественное присваивание и варианты обмена переменных значениями.
  3. Операторы if, elif, else. Цикл while, операторы break, continue, else.
  4. Цикл for, операторы break, continue, else. Функция range().
  5. Функции в Python. Позиционные и именованные параметры.
  6. Проблема изменяемых параметров по умолчанию. Стек вызова функций.
  7. Рекурсия. Прямой и обратный ход рекурсии. Стек вызовов при рекурсии.
  8. Динамическое программирование. Решение задач ДП циклами и рекурсией. Рекурсия с мемоизацией (ленивая динамика).

Простые алгоритмы

  1. Проверка последовательности чисел на наличие элемента с заданными свойствами и на соответствие всех элементов заданному свойству.
  2. Однопроходные алгоритмы обработки последовательности: подсчёт, сумма, произведение.
  3. Поиск максимума и подсчёт количества элементов, равных максимальному.
  4. Нахождение трёх максимальных элементов в последовательности за один проход.
  5. Поиск местоположения максимума в последовательности за один проход.
  6. Системы счисления. Перевод из одной системы счисления в другую.
  7. Проверка простоты числа. Метод грубой силы.
  8. Разложение числа на множители.
  9. Алгоритм Евклида нахождения НОД.
  10. Вычисление чисел Фибоначчи.
  11. Наивный поиск подстроки в строке. Реализация без использования стандартных методов str.
  12. Задача о количестве траекторий Кузнечика на числовой прямой.
  13. Проверки корректности скобочной последовательности с помощью стека.
  14. Сортировка подсчётом. Оценка временной сложности алгоритма.
  15. Алгоритм обращения чисел в массиве. Реализация циклом, без срезов.
  16. Алгоритм циклического сдвига в массиве. Реализация циклом, без срезов.
  17. Задача упорядочивания элементов в массиве. Проверка упорядоченности массива за O(N).

Сложные алгоритмы

  1. Решето Эратосфена. Оценка временной сложности алгоритма.
  2. Сортировка вставками. Оценка временной сложности алгоритма.
  3. Сортировка выбором. Оценка временной сложности алгоритма.
  4. Сортировка методом пузырька. Оценка временной сложности алгоритма.
  5. Поразрядная сортировка. Оценка временной сложности алгоритма.
  6. Быстрая сортировка Хоара. Временная сложность алгоритма (без док-ва).
  7. Сортировка слиянием. Оценка временной сложности алгоритма.
  8. Двоичный поиск в отсортированном массиве (левый и правый). Оценка временной сложности алгоритма. Двоичный поиск по ответу.
  9. Ханойские башни.
  10. Рекурсивная генерация всех чисел длины M.
  11. Генерация всех перестановок (рекурсивная).
  12. Задача о траектории наименьшей стоимости для Кузнечика. Восстановление траектории наименьшей стоимости.
  13. Наибольшая общая подпоследовательность.
  14. Наибольшая возрастающая подпоследовательность.
  15. Задача о рюкзаке
  16. Вычисление расстояния Левенштейна.
  17. Z-функция строки. Наивное вычисление и его оптимизация. Z-алгоритм. Оценка временной сложности алгоритма.
  18. Префикс-функция. Алгоритм Кнута-Морриса-Пратта. Оценка временной сложности алгоритма.
  19. Обратная Польская нотация. Вычисление выражения при помощи стека.
  20. Преобразование математического выражения в обратную польскую нотацию.

Оценка на зачёте

Основанием для рейтинговой оценки служат три оценки:

  1. Контрольная №1
  2. Контрольная №2
  3. Средняя оценка за все контесты

Преподаватель, экзаменующий студента, видит все эти оценки по отдельности, а также рекомендуемую итоговую оценку, которая вычисляется по этим пяти оценкам автоматически. Если устный ответ соответствует (отличаеться не более чем на два балла) рекомендуемой оценке (показывает уровень практических навыков программирования), преподаватель её выставляет студенту. В противном случае — проверяет навыки программирования студента поставив задачу, подобную любой из контестов.

Успехов в подготовке к зачёту!