Булах Дмитрий Александрович
к.т.н., доцент кафедры ПКИМС

Теория алгоритмов

Теория алгоритмов

Курс "Теория алгоритмов" читается студентам 2 курса, обучающиимся на кафедре ПКИМС(группы ЭН-24, ЭН-25), в третьем (осеннем) семестре.

План курса:

  • 8 лекций;
  • 4 лабораторные работы.

К лекциям предусмотрена самостоятельная работа.

Изучение дисцины "Теория алгоритмов" заканчивается зачётом.


КРАТКАЯ АННТОАЦИЯ

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

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

Теория алгоритмов

Материалы к лекциям

Лекция Рассматриваемые вопросы Презентация PDF Задания для СРС

Лекция 1

Общие сведения об алгоритмах

Определения алгоритма. Основные свойства алгоритмов и различные формы их записи. Классфификация алгоритмов с точки зрения последовательности исполнения и принципа работы, парадигмы разработки алгоритмов. Понятие сложности алгоритма.


PDF

PDF

Лекция 2

Основные способы организации данных

Дискретные, линейные, нелинейные структуры данных. Списочные структуры данных. Матрицы и обработка матриц. Хеши. Деревья.


PDF

PDF

Лекция 3

Обработка линейных структур данных

Алгоритмы сортировки линейных структур данных. Алгоритмы с квадратичной сложностью: сортировка вставками, выбором, обменом. Алгоритмы с логарифмической сложностью: слиянием, быстрая (Хоара). Блочная сортировка, сортировка подсчётом. Поиск по бору.


PDF

PDF

Лекция 4

Графы. Общие сведения.

Общие сведения о графах, способы представления графов, простейшие алгоритмы на графах: Дейкстра, Флойд, Краскал.



Лекция 5

Основы алгоритмов компрессии данных

Потоковые и блочные алгоритмы сжатия, однопроходные и многопроходные алгоритмы сжатия. 7-битное кодирование. RLE, Huffman, LZW, BWT.



Лекция 6

Подходы к защите данных.

Классификация и основы построения алгоритмов шифрования данных.



Лекция 7

Вероятностные и эвристические алгоритмы

Алгоритмы, построенные на основе эвристик и вероятностных методов: генетический алгоритм, алгоритм работы нейронных сетей, муравьиные алгоритмы, алгоритм моделирования отжига.



Тематика лабораторных работ

Лабораторная работа Рассматриваемые вопросы Материалы

Лабораторная работа №1

Основы работы в MS Visual Studio.

Создание проекта, редактирование программного кода, компиляция и сборка проекта, работа с отладчиком. Измерение времени работы программного кода. Работа с консолью, циклами, одномерными массивами.


Материалы не предусмотрены

Лабораторная работа №2

Основы работы с контейнерами STL

Оценка производительности контейнеров std::vector, основные операции с контейнером. Реализация и оценка производительности алгоритмов сортировки.


Материалы не предусмотрены

Лабораторная работа №3

Обработка одномерных массивов

Обработка одномерных массивов на примере написания интерпретаторов подмножества языка Brainfuck. Чтение текстовых файлов.


Материалы не предусмотрены

Лабораторная работа №4

Обработка матричных структур данных

Обработка матричных структур данных на примере реализации простого клеточного автомата.


Материалы не предусмотрены

Ваши преподаватели

Лектор

Дмитрий Булах
Булах Дмитрий Александрович

к.т.н., доцент кафедры ПКИМС

Помогают на лабораторных работах

...
Преподаватель не назначен
...
Заплетина Мария Андреевна
магистрант каф. ПКИМС
группа ПКИМС-24
...
Жестков Сергей Геннадьевич
магистрант каф. ПКИМС
группа ПКИМС-14
...
Кожаева Татьяна Дмитриевна
магистрант каф. ПКИМС
группа ПКИМС-14
...
Заплетина Мария Андреевна
магистрант каф. ПКИМС
группа ПКИМС-14
...
Жестков Сергей Геннадьевич
студент каф. ПКИМС
группа ЭКТ-42
...
Кожаева Татьяна Дмитриевна
студентка каф. ПКИМС
группа ЭКТ-42
Кирилл Жезлов
Жезлов Кирилл Александрович
магистрант каф. ПКИМС
группа ПКИМС-14
Павел Стругов
Стругов Павел Александрович
магистрант каф. ПКИМС
группа ПКИМС-14

14 октября 2019Успеваемость

Итоговая аттестация

Рекомендуемая литература

Клик по обложке - переход к файлообменнику
Роберт Седжвик
Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск.

Роберт Седжвик
Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах.

А. Ахо,
Дж. Хопкрофт,
Дж. Ульман
Структуры данных и алгоритмы.