Лекции по программированию
Материалы для 2-го курса мехмата
В. В. Борисенко
-
Лекция 1.
-
Лекция 2.
Обработка исключений в языке C++.
Стек, реализация стека на базе массива.
Обратная польская запись формул.
Проект "Стековый калькулятор"
(StackCalc.zip).
Аппаратная реализация стека. Размещение локальных переменных
в аппаратном стеке, механизм вызова функций и передачи параметров.
Задачи по проекту
"Стековый калькулятор".
-
Лекция 3.
-
Лекция 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.
Задача сортировки массива.
Оценка минимального числа сравнений в произвольном
алгоритме сортировки.
Наиболее популярные алгоритмы сортировки.
-
Алгоритм быстрой сортировки quickSort.
Реализация алгоритма, сочетающая итерацию и рекурсию,
при которой рекурсия применяется только к меньшей
половине массива (что обеспечивает логарифмическую оценку
глубины рекурсии). Инвариант цикла для этой схемы.
Применение схемы построения
цикла с помощью инварианта для написания функции partition,
разделяющей массив на три отрезка: элементы не больше медианы,
медиана, элементы не меньше медианы.
-
Пирамидальная сортировка (или сортировка кучей) heapSort:
идея, применение схемы построения цикла с помощью
инварианта для написания программы и доказательства
ее правильности. Реализация функции sieve восстановления
бинарной кучи.
Java-апплет,
графически иллюстрирующий различные алгоритмы сортировки.
Лекция 9.
Стабильные алгоритмы сортировки (сохраняющие
относительный порядок равных элементов).
-
Сортировка слиянием mergeSort, идея. Классический двусторонний
(2-Way) алгоритм сортировки слиянием: реализация
функции merge слияния двух упорядоченных массивов,
рекурсивная (нисходящая) и итеративная (восходящая) схемы
реализации алгоритма сортировки.
Улучшение классического алгоритма сортировки слиянием:
использование вспомогательного массива вдвое меньшего размера,
реализация функции mergeBlocks слияния двух соседних
упорядоченных блоков одного массива,
которая получает результат в том же массиве,
а не во вспомогательном.
-
Сортировка слиянием inPlaceMergeSort, не использующая
вспомогательной памяти
(т.е. исполняемая только с помощью элементарных команд
сравнения compare и обмена swap элементов массива):
идея, рекурсивная реализация функции слияния блоков
inPlaceMergeBlocks.
-
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пособы разрешения
коллизий:
-
Хеш-таблица представляет собой массив голов однонаправленных
списков, список с индексом h хранит элементы со
значением хеш-функции равным h, где h=0, 1, ..., N-1.
-
Хеш-таблица представляет собой массив элементов того же
типа, что и элементы множества, с индексом типа 0..N-1.
Дополнительно используется массив "мощность слоя" целого
типа с индексом типа 0..N-1 и массив "остаток" с индексом
типа 0..MAX-1, где MAX - некоторая константа, не меньшая, чем
потенциальное число элементов множества. Элемент массива
"мощность слоя" с индексом h хранит общее число элементов
множества, значение хеш-функции от которых равно h.
Один из таких элементов хранится в ячейке хеш-таблицы с
индексом h, остальные -- в массиве "остаток".
-
Хеш-таблица представляет собой массив элементов того же
типа, что и элементы множества, с индексом типа 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 (используется
первый способ разрешения коллизий).
Задачи по теме
"Хеш-реализация множества".
|