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

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

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

Курс "Теория алгоритмов" читается студентам 2 курса факультета ЭКТ в первом (осеннем) семестре, группам ЭКТ-23, ЭКТ-28 (кафедра ПКИМС).

План курса:

  • 8 лекций;
  • 4 лабораторные работы;
  • самостоятельная работа по материалам лекций.

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


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

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

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

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

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

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

Лекция 1

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

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


PDF

PDF

Лекция 2

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

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


PDF

PDF

Лекция 3

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

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


PDF

PDF

Лекция 4

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

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


PDF

PDF

Лекция 5

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

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


PDF

PDF

Лекция 6

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

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


PDF

PDF

Лекция 7

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

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


PDF

PDF

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

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

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

Лектор

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

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

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

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

21 декабря 2017Успеваемость

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

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

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

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

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