Сроки проведения

• группы 1081/1,2 - консультация 22 июня, пятница, аудитория 9-309, 16:00; экзамен 23 июня, суббота, аудитория 9-309, 10:00;
• группы 1081/3,4 - консультация 23 июня, суббота, аудитория 9-309, 14:00; экзамен 25 июня, понедельник, аудитория 9-309, 10:00;
• переэкзаменовка - 27 июня, среда, аудитория 9-309, 10:00;
• вторая переэкзаменовка состоится в сентябре, о времени и месте проведения будет объявлено дополнительно (3 июля переэкзаменовки НЕ БУДЕТ).

Знания и навыки

Необходимые

• Умение проектировать отдельные классы и простые иерархии классов
• Создание простых приложений с графическим интерфейсом в Qt Creator (Qt) или Microsoft Visual Studio (MFC)
• Знание наиболее распространённых графических компонентов и умение их использовать
• Создание, компиляция, запуск и отладка программного проекта

Желательные

• Умение работать со стандартной библиотекой шаблонов STL и/или с контейнерами Qt
• Знание распространённых алгоритмов поиска и сортировки и умение их использовать
• Знание устройства рекурсивных алгоритмов перебора
• Знакомство с понятием автоматизированного теста, умение создавать простые автоматизированные тесты

Порядок подготовки

Подготовку распределите равномерно. Во время подготовки к экзамену рекомендуется заниматься программированием по 6-8 часов в день (из которых 1-2 часа должно посвящаться теории, остальное - практике). Не откладывайте все на конец. Если при подготовке возникают вопросы - напишите письмо преподавателю. Также вопросы можно будет задать на консультации.

Перечитайте конспект лекций. Особое внимание следует уделить лекциям 2, 5, 7-8, а также лекциям 10-12 осеннего семестра. Просмотрите примеры к лекциям.

Большую часть времени подготовки следует уделить самостоятельному решению задач. В идеале, каждый день подготовки вы должны решать по 2-3 задачи. Примеры задач приведены ниже. Также вы можете решать задачи, выданные вам и вашим одногруппникам ранее на упражнениях, домашних заданиях, а также рассмотренные на лекциях (не подглядывая в решение лектора).

NB: консультация предназначена для того, чтобы студенты могли задать преподавателю вопросы по изученному материалу. На консультации не будет дополнительной лекции по программированию, магических рекомендаций о том, как сдать экзамен и тому подобных вещей. Консультация необязательна для посещения. Объявления, касающиеся времени и порядка проведения экзамена, будут размещаться на этой странице.

Советы экзаменуемому

1. Выспитесь. Лихорадочная подготовка в последнюю ночь ни к чему хорошему не приведет.
2. Первым делом внимательно прочитайте условие задачи. Убедитесь, что вы понимаете его полностью. В случае малейших сомнений задайте вопрос экзаменатору.
3. До написания программы прикиньте на бумаге алгоритм решения задачи (хотя бы ключевые моменты) и иерархию необходимых для решения классов.
4. Решая задачу, пользуйтесь только теми конструкциями и методами, в которых вы разбираетесь хорошо. Большинству студентов рекомендуется использовать методы объектно-ориентированного программирования.
5. Не торопитесь и не суетитесь. Отведенного времени больше чем достаточно для решения любой экзаменационной задачи.

Порядок проведения

Экзамен проводится в форме написания программы на стационарном компьютере (в случае недостатка стационарных компьютеров в аудитории в порядке исключения может быть разрешено написание программы на собственном ноутбуке студента). Каждый билет содержит одну задачу, которая должна быть решена в виде программы на языке C++; желательно применение методов объектно-ориентированного программирования. Если задача предполагает реализацию графического интерфейса, студент может использовать одну из двух библиотек: Qt или MFC; приветствуется использование дизайнера графического приложения. Время, предоставляемое на решение задачи - 2 часа 30 минут. При недостаточности отведенного интервала времени по усмотрению преподавателя может быть назначено дополнительное время от 15 до 60 минут, с соответствующим снижением оценки.

На экзамене разрешается пользоваться любыми бумажными источниками, а также электронными конспектами лекций. Не разрешается пользоваться любыми внешними носителями информации (флешками, CD, DVD и так далее; электронный конспект лекций предоставляется экзаменатором). Не разрешается консультироваться с кем-либо, кроме экзаменатора.

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

За продемонстрированное решение ставится оценка по 10-балльной шкале.

Описание шкалы оценок

Стиль (до 5 баллов, оценки кумулятивны)

Оценки за стиль применяются только в случае, если программа компилируется и в целом соответствует решаемой задаче.

• был успешно применен метод объектно-ориентированного проектирования: от +1 до +3 балла
• были применены готовые классы/шаблоны/алгоритмы, изученные в ходе весеннего семестра: от +1 до +2 балла

Результаты (до 4 баллов, оценки кумулятивны)

• программа запускается и завершается без появления сообщений об ошибках запуска, ошибках отладки и пр. +1 балл
• программа дает правильные результаты для большинства вариантов входных данных +1 или +2 балла
• программа дает правильные результаты на любых входных данных +1 балл

Теоретический вопрос

• +2 балла за правильный ответ
• +1 балл за частично правильный ответ

Штрафные баллы

• программа содержит грубые ошибки, связанные с незнанием студентом правил языка программирования -1 балл, в особо злостных случаях -2 балла
• программа содержит многократные дублирования кода -1 балл, в особо злостных случаях -2 балла
• использовано дополнительное время сверх двух часов -1 балла за каждые 30 минут (дополнительное время ограничивается одним часом)
• во входном файле приведена дополнительная информация, не указанная в задании (например, количество элементов в нем) -1 балл
• входные данные формируются в самой программе, вместо чтения их из файла -3 балла

Для получения оценки "удовлетворительно" необходимо набрать 4 балла по 10-балльной шкале, оценки "хорошо" - 6 баллов, оценки "отлично" - 8 баллов. При получении оценки в диапазоне от 2 до 7 баллов преподаватель задает студенту дополнительный вопрос по теории, в случае правильного ответа добавляется 1 или 2 балла по 10-балльной шкале. При ответе на теоретический вопрос пользоваться литературой не разрешается.

Темы для теоретических вопросов

1. Принципы использования шаблонов
2. Готовые шаблоны-контейнеры STL: vector, list, deque, map, hash_map, string.
3. Алгоритмы поиска (простой, бинарный, хэш-поиск, другие).
4. Алгоритмы сортировки (простой, двоичной кучей, Хоара, другие).
5. Виды отношений между классами, включение, наследование, диаграммы классов.
6. Основные принципы работы GUI-приложений, основные их отличия от консольных приложений.
7. Устройство графического приложения в Qt или MFC.
8. Сигналы и слоты (Qt); сообщения и обработчики (MFC).
9. Автоматизированные тесты.
10. Рекурсивные алгоритмы перебора (на примере задачи коммивояжёра или задачи поиска наилучшего хода).
11. Автоматное программирование.
12. Наиболее распространённые графические компоненты.
13. Использование дизайнеров графических интерфейсов, способы размещения компонентов (layouts).
14. Формат XML, назначение, использование в программах.

Примеры задач

Пример 1

Написать программу, изображающую в окне мишень из десяти концентрических окружностей (самая большая соответствует одному очку, следующая – двум, …, самая маленькая – десяти очкам). Пользователь производит «выстрелы» нажатиями на левую клавишу мыши, следы от выстрелов отмечаются крестиками. Программа подсчитывает и выводит число сделанных выстрелов и число набранных очков. Должна быть возможность сбросить все выстрелы и начать счет заново.

В этой программе ОБЯЗАТЕЛЬНО использование графического интерфейса.

Пример 2

Написать программу, реализующую электронную телефонную книгу. Требуемые возможности:

• добавление новой записи (фамилия человека и его номер телефона);
• поиск номера телефона по заданной фамилии человека;
• сохранение телефонной книги в файле на диске (желательно в формате XML);
• загрузка телефонной книги из файла на диске.

Считайте, что фамилии всех людей различны, и каждому человеку соответствует только один номер телефона. Для сохранения и загрузки можно использовать файл с заранее заданным именем (например, phonebook.xml).

В этой программе ОБЯЗАТЕЛЬНО использование графического интерфейса.

Пример 3

Во входном файле jumps.txt приведены результаты соревнований по прыжкам в длину, например:

Михайлов 715 - - 728 - 710
Васильев 693 - 708 - 720 688
Бурсаков 710 - - - 681 729
Сидоров 699 695 692 - 704 -

Для каждого прыгуна приведены результаты шести прыжков в сантиметрах, прочерками отмечены неудачные попытки. Написать программу, выдающую по фамилии прыгуна лучший среди его результатов. Использовать алгоритм БИНАРНОГО ПОИСКА или ХЭШ-ПОИСКА (готовые функции поиска НЕ ИСПОЛЬЗОВАТЬ). Фамилия прыгуна вводится пользователем с клавиатуры.

Пример 4 (задача о рюкзаках)

Во входном файле in.txt указано число предметов (первая строка) и вес каждого из предметов, например:

9
4 6 5 9 3 1 2 5

Задача заключается в том, чтобы разместить данные предметы в минимальном количестве одинаковых рюкзаков. Грузоподъёмность рюкзаков пользователь вводит с клавиатуры. Способ размещения следует вывести в выходной файл. Например, если пользователь ввел с клавиатуры число 9, то заданные 8 предметов можно разместить в 4 рюкзаках следующим образом:

4 bags
1: 9
2: 6 3 
3: 5 4
4: 5 2 1

Для решения данной задачи рекомендуется использовать алгоритм рекурсивного перебора.