Скачать 23.88 Kb.
|
Алгоритмы и алгоритмические языки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. |