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



Времена и даты

Контрольная работа №2 пройдёт 9 декабря с 13:55 до 15:30 во время лекции. Длительность 1.5 часа.

Все рядовые контесты семестра закрываются 13 декабря в 22:00.

Рейтинговая оценка за работу в семестре, учитывающая все контесты и обе контрольные работы, окончательно выставляется и публикуется к 9:00 14 декабря.

Дифференцированный зачёт по информатике принимается дистанционно в устной форме на зачётной неделе с 14 декабря по 19 декабря по индивидуальному расписанию. Расписание сдач формируется за неделю до зачёта. Зачёт для одного экзаменуемого длится от 20 до 40 минут.

Порядок сдачи зачёта

Зачёт принимает два экзаменатора. Студент должен отвечать на вопросы без предварительной подготовки. При случайном или плановом обрыве связи студент получает другой билет.

Студенту для сдачи зачёта необходимо наличие аудио и видео аппаратуры и связь через сеть Интернет достаточного качества для участия в видеоконференции через систему Google Meet с эккаунтом your_username@phystech.edu. Также необходимо предварительно зарегистрироваться на сайте repl.it по привязке к Google-эккаунту с тем же личным эккаунтом your_username@phystech.edu. Конкретная ссылка на конференцию будет переслана по почте.

Оценивание

Рекомендуемая итоговая оценка студента по предмету — это среднее арифметическое взвешенное оценок по лабораторным работам и контрольным. Экзаменатор видит все эти оценки по отдельности, а также рекомендуемую итоговую оценку. Исходя из ответа студента итоговая оценка за зачёт может быть отклонена от рекомендуемой на ±3 балла (по 10-балльной шкале). Студент при несогласии с итоговой оценкой может потребовать апелляции, однако на апелляции оценка может быть и понижена.

Список вопросов к зачёту

Cтудент получает билет, сгенерированный из одной задачи и двух случайных вопросов — одного по синаксису С++ и другого по алгоритмам и структурам данных. Задача решается под наблюдением преподавателя в системе repl.it. При решении задачи важно показать умение рассуждать, выбирать правильные структуры данных и стандартные контейнеры С++, догадываться какой алгоритм требуется применить.

Вопросы по синтаксису С++

  1. Контейнер std::list. Конструирование, методы добавления и удаления элементов, амортизированная асимптотическая сложность операций.
  2. Контейнер std::vector. Конструирование, методы добавления и удаления элементов, амортизированная асимптотическая сложность операций.
  3. Контейнер std::set. Контейнер std::map. Конструирование, методы добавления и удаления элементов, амортизированная асимптотическая сложность операций. Порядок обхода элементов итератором, требования к пользовательскому типу для использования в качестве ключа в таблице.
  4. Контейнеры std::unordered_set и std::unordered_map, добавление и удаление элементов, порядок обхода элементов итератором, требования к пользовательскому типу для использования в качестве ключа в таблице.
  5. Итераторы для работы с контейнерами в C++. Понятие итератора как универсального средства доступа к элементам линейно перечислимого типа данных, цикл по диапазону (range-based-for) и стандартный алгоритм std::for_each.
  6. Основы объектного подхода к конструированию кода. Объект как совокупность данных и функций над ними (инкапсуляция), классы и объекты, принцип сокрытия данных, модификаторы доступа public и private и по умолчанию, конструирование и конструктор по умолчанию.
  7. Управление ресурсами в C++. Концепция RAII. Что такое ресурс и зачем им нужно управлять. Что такое деструктор. Проблемы с оператором присваивания и копирующим конструктором. “Правило пяти”.
  8. Полиморфизм на основе шаблонов. Шаблоны функции. Параметры шаблона. Значения параметров по умолчанию. Отличие шаблонов от обычных функций, генерация на этапе компиляции (инстанцирование), раздувание кода (code flood).
  9. Полиморфизм на основе шаблонов. Шаблонные классы. Пример использования шаблона класса.

Вопросы по алгоритмам

  1. Хеш-функция как сжимающее отображение. Необратимость. Коллизии. Полиномиальный хеш и алгоритм Рабина-Карпа, асимптотическая сложность и выбор параметров полиномиального хеша.
  2. Хеш-функция как сжимающее отображение. Коллизии. Использование хеширования в криптографии, для контроля целостности данных. Фильтр Блума для уменьшения обращений к большим объемам данных.
  3. Хеш-таблицы. Реализация “множества” и “ассоциативного массива”. Асимптотическая сложность поиска, вставки и удаления. Проблема коллизий, метод цепочек и открытая адресация. Коэффициент заполнения таблицы.Необходимость перехеширования.
  4. Бинарные деревья поиска: АВЛ-дерево. Использование бинарных деревьев для реализации множеств и ассоциативных массивов, проблема балансировки и самобалансирующиеся деревья, повороты как преобразования сохраняющие инварианты дерева, принцип балансировки АВЛ-дерева, добавление и удаление элементов.
  5. Бинарные деревья поиска: красно-чёрное дерево. Использование бинарных деревьев для реализации множеств и ассоциативных массивов, проблема балансировки и самобалансирующиеся деревья, повороты как преобразования сохраняющие инварианты дерева, принцип балансировки красно-чёрного дерева, добавление и удаление элементов.
  6. Понятие конечного автомата. Детерминированный и недетерминированный конечные автоматы. Алгоритм распознавания слова конечным автоматом.
  7. Понятие регулярного языка. Представление регулярного языка посредством регулярного выражения, символы-джокеры (*, ?, + и т.п.). Преобразование детерминированного конечного автомата в регулярное выражение.
  8. Определение графа. Степень вершины, петли, кратные рёбра. Изоморфизм. Цепи, пути и циклы. Выделение компонент связности обходом в глубину.
  9. Сильная и слабая связность графа. Компоненты связности. Изолированная вершина. Выделение компонент связности обходом в ширину.
  10. Определение дерева. Свойства дерева. Остовное дерево графа. Построение минимального остовного дерева. Алгоритм Крускала.
  11. Способы представления графа в памяти: список рёбер, матрица смежности, списки смежности. Топологическая сортировка DAG.
  12. Алгоритм Дейкстры. Асимптотическая сложность. Восстановление пути.
  13. Алгоритм Флойда-Уоршелла. Асимптотическая сложность. Восстановление пути.
  14. Алгоритм Форда-Беллмана. Асимптотическая сложность. Восстановление пути.
  15. Обход графа в ширину. Дерево обхода. Проверка двудольности графа.
  16. Обход графа в глубину. Дерево обхода. Поиск мостов в графе.

Вопросы на повышение оценки в спорных случаях:

  1. Внутренняя структура std::priority_queue: бинарная куча, построение, добавление и удаление максимального/минимального элемента из кучи, сортировка с использованием бинарной кучи (пирамидальная сортировка).
  2. Асимптотическая сложность алгоритмов std::find, std::lower_bound и std::upper_bound на неотсортированных и отсортированных данных. Алгоритмы std::sort и std::stable_sort, асимптотическая сложность и асимптотическое потребление памяти, различие алгоритмов. Сортировка списка.
  3. Использование const для дополнительного статического контроля. Инициализация неизменяемых внутренних данных (const) и ссылок, различие методов и функций, передача объектов в качестве параметров, методы с модификатором const.
  4. Правосторонняя ссылка (r-value reference), конструктор перемещения и оператор перемещающего присваивания, плюсы и минусы управления ресурсами на основе перемещения. Пример использования перемещения.
  5. Проблема экспоненциального роста состояний в определенных языках для детерминированных автоматов, алгоритм распознавания для недетерминированных автоматов, эквивалентность множеств языков, заданных автоматами, и регулярных языков.
  6. Конечные автоматы и регулярные выражения. Представление регулярного языка посредством регулярного выражения, символы-джокеры (*, ?, + и т.п.), преобразование регулярного выражения в недетерминированный конечный автомат (алгоритм Томсона), преобразование конечного автомата в регулярное выражение, метод удаления состояний и метод транзитивного закрытия.
  7. Минимизация конечного автомата. Проблема алгоритмической неразрешимости эквивалентности двух машин Тьюринга и разрешимость эквивалентности двух конечных автоматов через построение минимального, изоморфные конечные автоматы. Алгоритмы минимизации детерминированных конечных автоматов, классы эквивалентности и k-эквивалентность, транзитивное замыкание таблицы неэквивалентности и алгоритм Хопкрофта.
  8. Поиск точек сочленения (шарниров) в графе.
  9. Проверка графа на ацикличность или нахождение цикла обходом в глубину.
  10. Нахождение кратчайшего цикла в невзвешенном графе.