Алгоримты



Аннотация

По существу курс можно было бы назвать «Введение в алгоритмы». Рассматриваются формальные модели алгоритмов: машина Тьюринга, алгоритмы Маркова, Паскаль. Следующий блок: основные структуры данных и алгоритмы.
Содержание курса
Введение в теорию алгоритмов. Интуитивное понятие алгоритма. Свойства алгоритмов. Понятие об исполнителе алгоритма.
Уточнение понятия алгоритма. Алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Тезис Тьюринга и его обоснование. Нормальные алгоритмы Маркова. Принцип нормализации и его обоснование. Композиции машин Тьюринга и нормальных алгоритмов Маркова. Понятие об алгоритмической неразрешимости.>
Алгоритмическая сложность. Связь понятия алгоритма с понятием функции.
Характеристика алгоритмических языков и их исполнителей. Понятие трансляции.
Понятие о формальных языках. Способы строгого описания формальных языков, понятие о метаязыках. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул и синтаксических диаграмм.
Язык программирования. Обшие характеристики языков программирования.. Алфавит, имена, служебные слова, стандартные имена, числа, текстовые константы, разделители.
Структура программы на Паскале. Заголовок программы. Блок.
Типы данных, их классификация. Переменные и константы. Скалярные типы данных и операции над ними, старшинство операций, стандартные функции. Выражения и правила их вычисления. Оператор присваивания. Перечислимые и ограниченные типы данных.
Простые и сложные операторы. Пустой, составной, условный операторы и оператор перехода. Метки. Оператор варианта.
Файлы. Стандартные процедуры функции ввода-вывода.
Операторы цикла. Программирование рекуррентных соотношений. Составные типы данных. Массивы.
Описание процедуры и оператор процедуры. Формальные и фактические параметры. Способы передачи параметров. Локализация имен. Разрешение коллизий.Функции, побочные эффекты.
Итерации и рекурсии. Комбинированный тип. Оператор присоединения. Множества. Ссылочный тип данных. Динамические переменные.
Структуры данных. Абстрактные структуры данных: графы, деревья, таблицы. Отношения. Отображение абстрактных структур данных на структуры хранения: векторная память, списки. Стеки и очереди.
Таблицы. Последовательные таблицы. Деревья сравнений. Перемешанные таблицы. Оценки алгоритмической сложности.
Кассические алгоритмы. Этапы разработки программ.

Литература


  • Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. Н . Наука. 1980.

  • Минский М. Вычисления и автоматы. М.: Мир. 1971.

  • Вирт Н., Йенсен К. Паскаль. Руководство для пользователя и описание языка. М.: Финансы и статистика. 1989.

  • Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. М.: Наука. 1988.

  • Вирт Н. Алгоритмы + структура данных = программа. М.: Мир. 1985.

  • Кнут Д. Основные алгоритмы, т. 1. Сортировка и поиск, т. 2. М.: Наука. 1985.

  • Сибуя М, Ямомото Т. Алгоритмы обработки даных. М.: Мир.1985.

  • Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. М.:> МЦНТО. 2000.

  • А.Ахо,.Д.Хопкрофт, Д.Ульман. Структуры даных и алгоритмы. М.: Изд-во Вильямс. 2000.