Документ взят из кэша поисковой машины. Адрес оригинального документа : http://sp.cs.msu.ru/courses/progs2006/alg_lang.doc Дата изменения: Wed Jun 14 19:13:51 2006 Дата индексирования: Mon Oct 1 21:49:59 2012 Кодировка: koi8-r

Алгоритмы и алгоритмические языки

1 курс, 1-й семестр
лекции (51 час), экзамен
практикум на ЭВМ (68 часов), зачет (с оценкой)
Кафедра, отвечающая за курс: системного программирования
Составители программы: чл.-кор. РАН, проф. Иванников В. П.,
доц., канд. физ.-мат. наук Пильщиков В. Н.,
проф., доктор физ.-мат. наук Соловьев С. Ю.
Лекторы: чл.-кор. РАН, проф. Иванников В. П. (1 п.),
доц., канд. физ.-мат. наук Пильщиков В. Н. (2
п.),
проф., доктор физ.-мат. наук Соловьев С. Ю. (3
п.)

Аннотация

Рассматриваются формальные модели алгоритмов (машина Тьюринга,
алгоритмы Маркова), язык программирования Паскаль, основные структуры
данных и алгоритмы их обработки.

Программа курса

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

Литература

1. Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. - М.:
Наука, 1980.
2. Корухова Л.С., Шура-Бура М.Р. Введение в алгоритмы - М.: МГУ, 1997.
3. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. -
М.: Наука, 1988.
4. Pascal ISO 7185:1990 -
http://www.moorecad.com/standardpascal/iso7185.pdf
5. Вирт Н., Йенсен К. Паскаль. Руководство для пользователя и описание
языка. - М.: «Компьютер», 1993.
6. Вирт Н. Алгоритмы + структура данных = программа. - СбП.: Невский
проспект, 2005.
7. Кнут Д. Искусство программирования. Том 1 - Основные алгоритмы. 3-е изд.
- М.: Вильямс, 2000.
8. Кнут Д. Искусство программирования. Том 3 - Сортировка и поиск. 2-е изд.
- М.: Вильямс, 2005.
9. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. -
М.: Вильямс, 2000.