Иванников В.П.

Иванников_Виктор_Петрович_MG_1226_BLK

В курсе дается введение в теорию алгоритмов. Рассматриваются формальные модели алгоритмов: машина Тьюринга, алгоритмы Маркова, Паскаль, а также основные структуры данных и алгоритмы.Дается характеристика алгоритмических языков и их исполнителей, вводятся понятия трансляции и формальных языков. Даются описание синтаксиса языка с помощью металингвистических формул и синтаксических диаграмм, общие характеристики языков программирования и их основные понятия. Вводятся абстрактные структуры данных: графы, деревья, таблицы.
default

Лекция 1. Понятие алгоритма и машина Тьюринга. В лекции вводится понятие алгоритма, дается исторический экскурс, определяются множества и функции. Рассказывается о тезисе Тьюринга и даются описание и пример машины Тьюринга

default-1Лекция 2. Разновидности машины Тьюринга.  Рассматриваются задача на построение анализатора на основе машины Тьюринга и алгоритм решения задачи Марвина Мински. Приводятся разновидности машин Тьюринга, рассказывается о неразрешимых проблемах и проблеме мертвого кода.

defaultЛекция 3. Нормальные мартовские алгоритмы. Вводятся нормальные марковские алгоритмы, даются их примеры, определяются их замыкание и композиция.

default-1Лекция 4. Понятие языка. Дается описание формальной системы Паскаль, рассказывается об алгоритме Евклида. Вводится понятие языка и типов данных.

defaultЛекция 5. Язык программирования Паскаль. Дается краткое введение в язык программирования Паскаль, приводятся основные понятия: операторы, операции, типы данных. Даются примеры.

defaultЛекция 6. Имена и функции в языке Паскаль. Вводятся понятия имен и функции, рассказывается о способах передачи параметров в функции, побочных эффектах функции, коллизиях имен, дается понятие отношения.

defaultЛекция 7. Графы. Дается определение графов, деревьев, стеков, очередей, кучи. Рассказывается о недостатках этих структур.

default-1Лекция 8. Работа со стеками, очередями и деревьями.Даются примеры работы со стеком, очередью и списком, указываются особенности работы с ними. Рассказывается о двоичных деревьях.

defaultЛекция 9. Двоичные деревья. Приводятся варианты обхода дерева c использованием циклов, рекурсий, стеков. Вводятся понятия первичного и вторичного ключа, даются оценки алгоритмов.

default-1Лекция 10. Деревья сравнения спусковой памяти. Рассказывается о деревьях сравнения списковой памяти, операции удаления и вставки.

defaultЛекция 11. АВЛ-деревья. Рассказывается об АВЛ-деревьях, условиях их существования и построения, приводятся процедуры корректировки характеристик и частные случаи трансформации деревьев.

defaultЛекция 12. Цифровой поиск. Приводится оценка вычислительной сложности АВЛ-деревьев, рассказывается о цифровом поиске, дается пример реализации программы.

default-1Лекция 13. Методы обработки таблиц с вычисляемыми образцами.Рассказывается о методах обработки таблиц с вычисляемыми адресами, реализуются необходимые процедуры.

 

Leave a Reply