Содержание
Регламент экзамена
Система оценивания
Полученные в рамках семестра баллы за компоненты курса, описанные в рейтинговой системе, конвертируются в оценку за экзамен по следующим правилам:
Таблица 1. Границы баллов для перевода в экзаменационную оценку.
| Оценка | Граница баллов |
|---|---|
| Удовлетворительно | >=55 |
| Хорошо | >=75 |
| Отлично | >=95 |
Подтверждение оценки
Любая оценка за экзамен, получаемая по рейтингу, кроме «Неудовлетворительно», требует подтверждения на экзамене.
- Отказ от подтверждения оценки соответствует отказу от оценки по рейтингу, т.е. решение полного билета.
Повышение оценки
Если студента не удовлетворяет оценка по итогам работы в семестре (на основании баллов), он может отказаться от нее и сдать экзамен
- накопленная за семестр оценка теряется без возможности отката
- экзамен представляет из себя полный экзаменационный билет по темам дисциплины
Допсессии, комиссии, дни качества и прочее
Допсессия и комиссия
Для студентов, несдавших экзамен в рамках основной сессии (т.е. получивших «Неудовлетворительно» при сдаче экзамена):
- накопленная за семестр оценка обнуляется (поскольку студент не смог её подтвердить на экзамене)
- экзамен проводится по правилам полного экзамена
Для студентов, недопущенных до экзамена (например, несдача курсовой работы) или пропустивших экзамен по уважительной причине:
- накопленная за семестр оценка сохранятся
- экзамен проводится по стандартным правилам:
- все положительные оценки требуют подтверждения путём решения упрощенного экзаменационного билета
- в случае оценки «Неудовлетворительно» по рейтингу или повышения оценки - решение полного экзаменационного билета
На комиссионных пересдачах студенты пишут полный экзамен независимо от баллов рейтинга.
День качества
Курсовая работа
Повышение оценки за курсовую происходит путём выполнения нового варианта курсовой на соответствующую оценку.
- Для получения нового варианта необходимо написать своему преподавателю.
Экзамен
Повышение оценки в рамках дня качества соответствует правилам, описанным в разделе "Повышение оценки"
Экзаменационные билеты
В данном разделе описаны виды и составлящие экзаменационных билетов. Примеры билетов приведены в конце страницы.
Каждый компонент билета выполняется студентов самостоятельно без использования каких-либо сторонних ресурсов и материалов.
Упрощенный билет
Подтверждение оценок на экзамене предполагает упрощенный экзаминационный билет, состоящий из теоретического минимума и практических задач, и беседу с преподавателем.
- Оценивание решений теор. минимума и задач проводится до или во время беседы с преподавателем.
- Беседа с преподавателем не даёт возможности исправить/изменить решения практических задач или получить время на доработку
Теоретический минимум
- является первым и обязательным этапом экзамена для подтверждения любой оценки
- представляет из себя тест из 20 вопросов (с выбором ответа или свободным ответом)
- выполняется в течение 15 минут
Темы вопросов: структуры данных и АТД, сортировки, хэш-таблицы, деревья (в том числе БТД и Rope), жадные алгоритмы.
Если результат студента по теоретическому минимуму меньше 50% - оценка за экзамен снижается на 1 балл
- При подтверждении оценки «Удовлетворительно» в случае несдачи теор. минимума студент получает «Неудовлетворительно»
Практические задачи
- Подтверждение оценки «Удовлетворительно» - решение одной практической задачи
- Подтверждение оценки «Хорошо» - решение двух практических задач
- Подтверждение оценки «Отлично» - решение двух практических задач
Подтверждение более высокой оценки автоматически включает задачи более низких оценок. Таким образом, для подтверждения оценки «Отлично» требуется решить 5 задач, для «Хорошо» - 3 задачи.
Время, отведенное на решение практических задач, зависит от подтверждаемой оценки (т.е. от кол-ва задач) - 30/60/90 минут для оценок «Удовлетворительно»/«Хорошо»/«Отлично» соответственно.
Полный билет
Полный билет содержит
- теоретический анализ
- расширенный теоретический минимум (30 вопросов со свободным ответом на 30 минут)
- Примечание от 14.01: вопросы со свободным ответом заменены на утверждения, которые нужно отметить как верные / неверные - время на компоненту снижено до 25 минут.
- практические задачи - по 2 задачи на каждую оценку (Удовлетворительно/Хорошо/Отлично)
- более высокая оценка автоматически включает задачи более низких оценок (т.е. на оценку «Отлично» нужно решить 6 задач, на «Хорошо» - 4 задачи)
- на решение всех задач (независимо от желаемой оценки) отводится 90 минут
Теоретический анализ
Полный список вопросов теор. анализа приведен на странице Вопросы теоретического анализа.
За два дня до экзамена* студенту, изъявившему желание писать полный экзамен, случайным образом выдаются 6 вопросов по теоретическому материалу дисциплины: 3 вопроса из блока «Удовлетворительно» и 3 вопроса из блока «Хорошо / Отлично»
- Студент самостоятельно готовится по данным вопросам, чтобы на экзамене предоставить максимально полные ответы по ним
- На экзамене для написания ответов отводится 60 минут
- Вопросы блока «Удовлетворительно»
- Обязательны для написания
- Оцениваются бинарно - 0/1 (максимум 3 балла за весь блок)
- Если дан неполный ответ или ответ с ошибками, он считается неверным и оценивается как 0
- Если за вопросы данного блока получено
- <2 баллов - ставится оценка «Неудовлетворительно».
- >=2 баллов - студент может претендовать на оценку не выше «Удовлетворительно».
- Вопросы блока «Хорошо/Отлично»
- Обязательны для написания только если студент претендует на оценку «Хорошо» или «Отлично»
- Оцениваются бинарно - 0/1 (максимум 3 балла за весь блок)
- Если дан неполный ответ или ответ с ошибками, он считается неверным и оценивается как 0
- Если за вопросы данного блока получено
- <2 баллов - блок считается несданным, а оценка за экзамен ограничивается по правилам блока «Удовлетворительно»
- >=2 баллов - блок считается сданным, ограничений на оценку за экзамен нет.
Результаты данного этапа могут (и будут) влиять на итоговую оценку за экзамен в спорных и иных случаях.
Краткая сводка:
- если студент претендует на оценку «Удовлетворительно» - ему достаточно написать не менее 2х вопросов из блока «Удовлетворительно»
- если студент претендует на оценку «Хорошо / Отлично» - ему требуется написать блок «Удовлетворительно» И блок «Хорошо / Отлично»
- если студент не сдает блок «Удовлетворительно» - ставится оценка «Неудовлетворительно» (вне зависимости от ответов на следующий блок вопросов)
Теоретический минимум и практические задачи
Аналогично разделу «Подтверждение оценки», отличие только в количестве вопросов / задач (описаны ранее).
Пример компонентов экзаменационного билета
Теоретический анализ
Полный список вопросов приведен на странице Вопросы теоретического анализа.
Теоретический минимум
- Какова временная сложность поиска элемента в отсортированном массиве с использованием двоичного поиска?
- Какую структуру данных лучше всего использовать для реализации очереди и почему?
- Приведите примеры устойчивых сортировок?
- Для какого случая хеш-таблицы эффективны?
- Что означает «балансировка» в АВЛ-дереве?
- Какова разница между обходом дерева в глубину и в ширину? Приведите пример для объяснения.
- Что такое хеш-функция? Каковы её основные свойства?
- Какие проблемы могут возникнуть при использовании хеш-функций? Опишите способы их решения.
- Какой из алгоритмов сортировки основан на подходе «Разделяй и властвуй»?
- Что происходит при большом повороте в АВЛ-дереве?
- Что представляет собой стек?
- Какая из структур данных подходит для реализации алгоритма обхода дерева в ширину?
- Приведите примеры трёх жадных алгоритмов и их критерий жадности
- Опишите основные свойста красно-черного дерева
- Какую временную сложность имеет операция вставки в куче?
- Какие структуры данных не поддерживают произвольный доступ к элементам?
- Какие преимущества имеет использование самобалансирующихся деревьев? Приведите примеры применения.
- Опишите алгоритм работы сортировки Timsort. В чем его преимущества по сравнению с другими сортировками?
Практические задачи
Пример «билета» с набором задач на каждую оценки (более высокая оценка включает задачи более низких оценок).
Задачи выполняются строго последовательно.
Удовлетворительно
- Реализуйте класс бинарного дерева Tree с использованием класса узла Node и функцию для нахождения путей от корня до листа длины в диапазоне [a, b], за один обход дерева. Проверьте работу функции на различных конфигурациях деревьев. Обоснуйте и подтвердите сложность алгоритма (график теор. и практич. времени)
Хорошо
- Проверьте за один проход, является ли бинарное дерево 1) линейным списком с диапазоном значений [c, d]. 2) АВЛ-деревом высотой больше A и меньше B.
- Реализуйте модифицированный односвязный и двусвязный списки, позволяющие за О(1) получить минимальное/максимальное значение в списке, с сохранением асимптотики операций. Подтвердите сложность операций, сравнив с простыми списками
Отлично
- Реализуйте два алгоритма сортировки: слиянием и вставками. Сравните их производительность, а также производительность встроенной сортировки, на случайных, почти отсортированных и обратно отсортированных массивах.
- Реализуйте хеш-таблицу с методом цепочек, вместо цепочек - любой класс с методами add/remove/find (по умолчанию - односвязный список). Подберите различные конфигурации данных / хеш-функции и сравните скорость работы с использованием цепочки 1) по умолчанию 2) бинарного дерева поиска