Лекции по программированию

Материалы для 2-го курса мехмата

В. В. Борисенко

Третий (осенний) семестр

Материалы 4-го (весеннего) семестра


Содержание лекций 3-го семестра (для части лекций имеется их полная запись)

  • Лекция 1.
  • Лекция 2.
      Обработка исключений в языке C++. Стек, реализация стека на базе массива. Обратная польская запись формул. Проект "Стековый калькулятор" (StackCalc.zip). Аппаратная реализация стека. Размещение локальных переменных в аппаратном стеке, механизм вызова функций и передачи параметров.
      Задачи по проекту "Стековый калькулятор".
  • Лекция 3.
      Статические члены и методы классов. Наследование классов. Виртуальные методы и абстрактные классы. Программирование в оконных средах: общие принципы. Преимущества объектно ориентированного в случае программирования в оконной среде. Проект "Графическое окно" (GWindow.zip) как пример простейшей библиотеки классов для поддержки программирования в среде X-Windows (Unix).
      Программирование под X11, краткое введение (Brian Hammond).
      Задачи по теме "Графика".
  • Лекция 4.
      Структуры данных: последовательного доступа -- стек, очередь, дек, двусвязный и односвязный списки; прямого доступа -- массив (вектор), динамический массив, матрица, множество, нагруженное множество. Реализация стека и дека (очереди) на базе массива. Битовая реализация ограниченного множества целых чисел. Способы реализация циклов "для каждого элемента": итераторы, методы типа "forEach".
  • Лекция 5.
      Схема построения цикла с помощью инварианта. Применения этой схемы: алгоритм Евклида, алгоритм быстрого возведения в степень, бинарные алгоритмы умножения и деления, расширенный алгоритм Евклида, вычисление логарифма без разложения в ряд.
  • Лекция 6.
      Непрерывные реализации множества: наивная реализация, реализация с помощью бинарного поиска. Применение сxемы построения цикла с помощью инварианта в алгоритме бинарного поиска.
  • Лекция 7.
      Библиотека классов и система разработки приложений Qt (читается "Кьют"). Разработка оконных (графических) приложений в Qt. Классы QApplication и QWidget, структура простейшей оконной программы. Виртуальные методы класса QWidget, обрабатывающие оконные события:
          virtual void paintEvent(QPaintEvent* event);
          virtual void mousePressEvent(QMouseEvent* event);
      
      и др. Механизм инициации событий и связи событий с их обработчиками: ключевые слова signal, slot, emit, статический метод connect класса QObject; препроцессирование текста с помощью утилиты moc (Meta-Object Compiler). Иллюстрация механизма связи сигналов и слотов на примере обработчика нажатия на кнопку типа QPushButton.
      Создание файла Qt-проекта *.pro и файла "Makefile" с помощью утилиты qmake (в Qt версии 4):
          qmake -project
          qmake
          make
      
      (первая команда создает файл проекта, вторая по файлу проекта создает Makefile, третья компилирует проект и при отсутствии ошибок создает файл приложения; например, пусть исходные файлы с расширениями *.h и *.cpp находятся в директории "abcd", тогда в ней будет создан файл проекта "abcd.pro", затем "Makefile", файл приложения будет называться "abcd").

      Пример несложного проекта: построение графика интерполяционного полинома Ньютона по узлам интерполяции, отмечаемым кликами мыши, архив Newton.zip (файлы "main.cpp", "newton.h", "newton.cpp", "Newton.pro").

      Замечание: в Qt5 в файл проекта "Newton.pro", который создается командой

          qmake -project
      
      надо вручную добавить строку
          QT += core gui widgets
      

  • Лекция 8.
      Задача сортировки массива. Оценка минимального числа сравнений в произвольном алгоритме сортировки.
      Наиболее популярные алгоритмы сортировки.
      1. Алгоритм быстрой сортировки quickSort. Реализация алгоритма, сочетающая итерацию и рекурсию, при которой рекурсия применяется только к меньшей половине массива (что обеспечивает логарифмическую оценку глубины рекурсии). Инвариант цикла для этой схемы.
        Применение схемы построения цикла с помощью инварианта для написания функции partition, разделяющей массив на три отрезка: элементы не больше медианы, медиана, элементы не меньше медианы.
      2. Пирамидальная сортировка (или сортировка кучей) heapSort: идея, применение схемы построения цикла с помощью инварианта для написания программы и доказательства ее правильности. Реализация функции sieve восстановления бинарной кучи.
      Java-апплет, графически иллюстрирующий различные алгоритмы сортировки.
  • Лекция 9.
      Стабильные алгоритмы сортировки (сохраняющие относительный порядок равных элементов).
      1. Сортировка слиянием mergeSort, идея. Классический двусторонний (2-Way) алгоритм сортировки слиянием: реализация функции merge слияния двух упорядоченных массивов, рекурсивная (нисходящая) и итеративная (восходящая) схемы реализации алгоритма сортировки.
        Улучшение классического алгоритма сортировки слиянием: использование вспомогательного массива вдвое меньшего размера, реализация функции mergeBlocks слияния двух соседних упорядоченных блоков одного массива, которая получает результат в том же массиве, а не во вспомогательном.
      2. Сортировка слиянием inPlaceMergeSort, не использующая вспомогательной памяти (т.е. исполняемая только с помощью элементарных команд сравнения compare и обмена swap элементов массива): идея, рекурсивная реализация функции слияния блоков inPlaceMergeBlocks.
      3. RADIX-сортировка (поразрядная сортировка), идея, возможные схемы ее реализации, оценки времени работы и объема вспомогательной памяти.
      Java-апплет, графически иллюстрирующий различные алгоритмы сортировки.
  • Лекция 10.
      Бинарная куча (Priority Queue): определение, свойства, реализация на базе массива. Алгоритм Дийкстры нахождения кратчайшего пути в графе (транспортной сети). Применение бинарной кучи в алгоритме сортировки кучей и в алгоритме Дийкстры.
  • Лекция 11.
      Непрерывные и ссылочные реализации структур данных. Идея ссылочной реализации, достоинства и недостатки непрерывных и ссылочных реализаций.

      Реализация Л2-списка на С++: классы L2ListHeader и L2List. Особенность реализации с использованием динамической памяти: элементы списка являются объектами класса, который наследуется из класса L2ListHeader; поэтому у класса L2ListHeader и у наследуемых из него классов должен быть виртуальный деструктор.

  • Лекция 12.
      Проект "Текстовый редактор" (TextEdit.zip). Класс Text, представляющий Л2-список строк, и класс TextLine, представляющий строку текста. Особенности реализации класса TextLine:
      • используется как элемент Л2-списка, поэтому наследуется из класса L2ListHeader;
      • представляет собой динамический массив символов;
      • имеет конструктор, инициализирующий объект по адресу строки в стиле языка Си, и оператор приведения к типу Си-строки (т.е. к типу "const char*");
      • реализует все привычные операции для текстовых строк (конкатенация, вставка/удаление символов и т.п.).
      Реализация класса TextEdit, представляющего собой текстовый редактор в оконной системе X-Windows:
      • наследуется из класса GWindow ("Графическое окно");
      • хранит текст в объекте "text" типа "Text". Класс "Text" наследуется из класса "L2List" и представляет собой Л2-список строк типа TextLine;
      • координаты курсора (измеряемые в колонках и строках) относительно начала текста хранятся в переменных cursorX, cursorY;
      • координаты окна относительно начала текста и его размер хранятся в переменных windowX, windowY, windowWidth, windowHeight;
      • хранится статическая таблица соответствия между кодами нажатых клавиш и методами, реализующими соответствующие команды. Когда пользователь нажимает клавишу, осуществляется поиск в этой таблице и вызывается соответствующий метод, если команда найдена.
      Задачи по проекту "Текстовый Редактор".
  • Лекция 13.
      Бинарные деревья и деревья поиска. Идея реализации множества и нагруженного множества с помощью бинарного дерева поиска. Алгоритмы поиска и добавления элемента для деревьев поиска. Алгоритм нахождение следующей вершины дерева и обхода вершин дерева в порядке их возрастания. Сбалансированные и почти сбалансированные деревья, AVL-деревья.
  • Лекция 14.
      Красно-черные деревья: определение и свойства. Восстановление структуры красно-черного дерева при добавлении элемента: операции вращения вершины вправо и влево, рассмотрение различных случаев при добавлении элемента с нарушением свойств красно-черного дерева. Реализация нагруженного множества на основе красно-черного дерева: проект "TreeSet.zip".
      Задачи по теме "Красно-черные деревья".
  • Лекция 15.
      Реализация множества и нагруженного множества, основанная на использовании хеш-функции. Идея реализации: расслоение множества на N небольших подмножеств. Иллюстрация -- записная книжка: аналогом хеш-функции является первая буква фамилии, страницы нумеруются значениями хеш-функции, т.е. буквами алфавита. Требования к хеш-функции. Коллизии, cпособы разрешения коллизий:
      1. Хеш-таблица представляет собой массив голов однонаправленных списков, список с индексом h хранит элементы со значением хеш-функции равным h, где h=0, 1, ..., N-1.
      2. Хеш-таблица представляет собой массив элементов того же типа, что и элементы множества, с индексом типа 0..N-1. Дополнительно используется массив "мощность слоя" целого типа с индексом типа 0..N-1 и массив "остаток" с индексом типа 0..MAX-1, где MAX - некоторая константа, не меньшая, чем потенциальное число элементов множества. Элемент массива "мощность слоя" с индексом h хранит общее число элементов множества, значение хеш-функции от которых равно h. Один из таких элементов хранится в ячейке хеш-таблицы с индексом h, остальные -- в массиве "остаток".
      3. Хеш-таблица представляет собой массив элементов того же типа, что и элементы множества, с индексом типа 0..N-1. Никаких дополнительных массивов не используется. Считаем, что множество может содержать не более чем N-1 элемент. "Пустая" ячейка хеш-таблицы отмечается специальным значением, которое не может содержаться в множестве. При добавлении элемента x к множеству сначала вычисляется значение хеш-функции от него: h=hash(x). Если элемент хеш-таблицы с индексом h занят, то к h прибавляется некоторая фиксированная константа D, где D взаимно просто с N, затем вычисляется остаток от деления полученного числа на N. Таким образом вычисляется новое значение h. Если опять ячейка с индексом h занята, операция снова повторяется, пока не найдется свободная ячейка. Всего может быть не более N-1 повторения. Поиск элемента осуществляется аналогично. Числа N и D в этой реализации обычно выбираются простыми, наример, N=5009, D=1021. Удалять элементы из множества в этой реализации нельзя.

      Проект "Хеш-реализация нагруженного множества" HashSet.zip (используется первый способ разрешения коллизий).
      Задачи по теме "Хеш-реализация множества".


Четвертый семестр