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

  • досрочный экзамен: 3 июня, 9-304, 12:00 (проводится в форме беседы с аудиторией по теории с индивидуальной оценкой вклада каждого участника)
  • 9 июня, 9-309, 10:00 -- консультация для групп 1 и 2
  • 10 июня, 9-309, 10:00 -- экзамен для групп 1 и 2
  • 18 июня, 9-309, 10:00 -- консультация для групп 3, 4 и 5
  • 22 июня, 9-309, 10:00 -- экзамен для групп 3, 4 и 5
  • 1 июля, 9-309, 10:00 -- переэкзаменовка для всех групп
  • приблизительно 15 сентября, точный день, время и место будут указаны осенью -- вторая и последняя переэкзаменовка

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

Необходимые

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

Желательные

  • Умение работать со стандартной библиотекой шаблонов STL и/или с контейнерами Qt
  • Знание сложных алгоритмов (хэш-поиск, сортировка Хоара, сортировка двоичной кучей, сортировка Шелла, алгоритм Дейкстры, минимаксный алгоритм перебора) и структур данных (дерево, хэш-таблица, куча)
  • Знакомство с понятием автоматизированного теста, умение создавать простые автоматизированные тесты

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

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

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

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

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

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

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

Экзамен проводится в форме написания программы на стационарном компьютере (в случае недостатка стационарных компьютеров в аудитории в порядке исключения может быть разрешено написание программы на собственном ноутбуке студента). Каждый билет содержит одну задачу, которая должна быть решена в виде программы на языке C++ с применением методов объектно-ориентированного программирования. Задачи имеются двух типов: посвященные алгоритмам и структурам данных (обычно задача заключается в написании и тестировании определённого класса) и посвященные GUI (такая задача решается в виде проекта на Qt Widgets, по желанию можно использовать Qt 4-й либо 5-й версии).

Время, предоставляемое на решение задачи - 1 час 30 минут. При недостаточности отведенного интервала времени по усмотрению преподавателя может быть назначено дополнительное время до 30 минут, с возможным снижением оценки.

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

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

За продемонстрированное решение ставится оценка: 2 (программа не решает поставленную задачу) или от 3 до 5 (программа решает поставленную задачу в большинстве случае или всегда). Для задачи по алгоритмам условия получения каждой из положительных оценок указаны в билете. Для GUI-задачи дополнительно оценивается стиль и аккуратность решения.

В случае положительной оценки (3-5) за решённую задачу задаётся теоретический вопрос (по GUI, если задача по алгоритмам и наоборот). Ответ на вопрос может повысить или понизить полученную оценку, но не более чем на один балл. В случае отрицательной оценки (2) за решённую задачу экзамен прерывается, теоретический вопрос не задаётся.

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

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

Примеры задач на алгоритмы и структуры

Стек

Написать шаблон, реализующий указанный интерфейс:

template <class T> class IStack {
public:
    virtual int size() = 0;
    virtual bool isEmpty() = 0;
    // извлекает элемент из стека и возвращает его значение
    // если стек пуст -- генерировать исключение
    virtual T pop();
    // добавляет указанный элемент в стек
    virtual void push(const T& elem);
};

Оценить трудоёмкость основных методов с помощью O(...). По возможности добиться отсутствия ограничения на размер стека, возможно лучшей производительности и затрат памяти. Уметь объяснить принятые решения.

Шаблоны STL / QT использовать не разрешается.

Очередь

Написать шаблон, реализующий указанный интерфейс:

template <class T> class IStack {
public:
    virtual int size() = 0;
    virtual bool isEmpty() = 0;
    // извлекает элемент из очереди и возвращает его значение
    // если стек пуст -- генерировать исключение
    virtual T take();
    // добавляет указанный элемент в очередь
    virtual void put(const T& elem);
};

Оценить трудоёмкость основных методов с помощью O(...). По возможности добиться отсутствия ограничения на размер очереди, возможно лучшей производительности и затрат памяти. Уметь объяснить принятые решения.

Шаблоны STL / QT использовать не разрешается.

Таблица

Написать шаблон, реализующий указанный интерфейс (таблица ключ-значение):

template <class Key, class Value> class ITable {
public:
    virtual int size() = 0;
    virtual bool isEmpty() = 0;
    // добавляет новую пару ключ / значение
    // если данный ключ уже есть в таблице -- его значение заменяется на новое
    virtual void put(const Key& key, const Value& value);
    // получить значение, соответствующее заданному ключу
    virtual Value get(const Key& key);
};

Оценить трудоёмкость основных методов с помощью O(...). По возможности добиться отсутствия ограничения на размер таблицы, возможно лучшей производительности и затрат памяти. Уметь объяснить принятые решения.

Шаблоны STL / QT использовать не разрешается.

Матрица

Написать шаблон, реализующий указанный интерфейс (двумерная таблица):

template <class T> class IMatrix {
public:
    // число рядов
    virtual int rows() = 0;
    // число колонок
    virtual int columns() = 0;
    // добавляет новый ряд, arr -- указатель на массив с элементами ряда размерностью не менее columns()
    virtual void addRow(T* arr) = 0;
    // добавляет новую колонку, arr -- указатель на массив с элементами колонки размерностью не менее rows()
    virtual void addColumn(T* arr) = 0;
    // возвращает ссылку на элемент по заданным индексам ряда и колонки
    virtual T& element(int row, int column) = 0;
};

Оценить трудоёмкость основных методов с помощью O(...). По возможности добиться отсутствия ограничения на размер матрицы, возможно лучшей производительности и затрат памяти. Уметь объяснить принятые решения.

Шаблоны STL / QT использовать не разрешается.

Граф

Написать класс, реализующий указанный интерфейс (граф):

class IGraph {
public:        
    // Добавить узел графа (первый добавленный узел имеет номер 0, второй 1, третий 2, ...)
    virtual void addNode() = 0;
    // Вернуть количество узлов в графе (узлы могут иметь индексы от 0 до nodes()-1 )
    virtual int nodes() = 0;
    // Соединить два заданных узла (first, second -- номера узлов)
    virtual void connect(int first, int second);
    // Рассчитать минимальную длину пути между узлами first и second (каждая пройденная дуга считается за 1)
    // Если пути не существует, возвращает -1
    virtual int length(int first, int second);
};

Оценить трудоёмкость основных методов с помощью O(...). По возможности добиться отсутствия ограничения на размер графа, возможно лучшей производительности и затрат памяти. Уметь объяснить принятые решения.

Примеры задач на проектирование GUI

Стрельба

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

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

Крестики-нолики 3х3

Написать программу, реализующую классическую игру "крестики-нолики 3х3" человека против компьютера. Крестики ходят первыми, человек может выбрать, за кого играет. Реализовать возможно лучший алгоритм игры для компьютера (решение совсем без компьютерного алгоритма засчитано не будет).

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

Телефонная книга

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

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

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

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

Примеры задач 2012 года

ПРИМЕЧАНИЕ: в таком виде задачи вряд ли встретятся на экзамене, тем не менее порешать их может быть полезно.

Пример 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

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