- Введение в алгоритмы. Видеокурс лекций на НОУ ИНТУТ
- Введение в алгоритмы. Видеокурс лекций на youtube.com.
В курсе дается введение в теорию алгоритмов. Рассматриваются формальные модели алгоритмов: машина Тьюринга, алгоритмы Маркова, Паскаль, а также основные структуры данных и алгоритмы.Дается характеристика алгоритмических языков и их исполнителей, вводятся понятия трансляции и формальных языков. Даются описание синтаксиса языка с помощью металингвистических формул и синтаксических диаграмм, общие характеристики языков программирования и их основные понятия. Вводятся абстрактные структуры данных: графы, деревья, таблицы.
Лекция 1. Понятие алгоритма и машина Тьюринга. В лекции вводится понятие алгоритма, дается исторический экскурс, определяются множества и функции. Рассказывается о тезисе Тьюринга и даются описание и пример машины Тьюринга
Лекция 2. Разновидности машины Тьюринга. Рассматриваются задача на построение анализатора на основе машины Тьюринга и алгоритм решения задачи Марвина Мински. Приводятся разновидности машин Тьюринга, рассказывается о неразрешимых проблемах и проблеме мертвого кода.
Лекция 3. Нормальные мартовские алгоритмы. Вводятся нормальные марковские алгоритмы, даются их примеры, определяются их замыкание и композиция.
Лекция 4. Понятие языка. Дается описание формальной системы Паскаль, рассказывается об алгоритме Евклида. Вводится понятие языка и типов данных.
Лекция 5. Язык программирования Паскаль. Дается краткое введение в язык программирования Паскаль, приводятся основные понятия: операторы, операции, типы данных. Даются примеры.
Лекция 6. Имена и функции в языке Паскаль. Вводятся понятия имен и функции, рассказывается о способах передачи параметров в функции, побочных эффектах функции, коллизиях имен, дается понятие отношения.
Лекция 7. Графы. Дается определение графов, деревьев, стеков, очередей, кучи. Рассказывается о недостатках этих структур.
Лекция 8. Работа со стеками, очередями и деревьями.Даются примеры работы со стеком, очередью и списком, указываются особенности работы с ними. Рассказывается о двоичных деревьях.
Лекция 9. Двоичные деревья. Приводятся варианты обхода дерева c использованием циклов, рекурсий, стеков. Вводятся понятия первичного и вторичного ключа, даются оценки алгоритмов.
Лекция 10. Деревья сравнения спусковой памяти. Рассказывается о деревьях сравнения списковой памяти, операции удаления и вставки.
Лекция 11. АВЛ-деревья. Рассказывается об АВЛ-деревьях, условиях их существования и построения, приводятся процедуры корректировки характеристик и частные случаи трансформации деревьев.
Лекция 12. Цифровой поиск. Приводится оценка вычислительной сложности АВЛ-деревьев, рассказывается о цифровом поиске, дается пример реализации программы.
Лекция 13. Методы обработки таблиц с вычисляемыми образцами.Рассказывается о методах обработки таблиц с вычисляемыми адресами, реализуются необходимые процедуры.