Geum.ru

Курс, 1-й семестр лекции (51 час), экзамен практикум на ЭВМ (68 часов), зачет (с оценкой) Кафедра, отвечающая за курс

Вид материалаЛекции

Содержание


Введение в теорию алгоритмов.
Языки программирования.
Динамические структуры данных.
Этапы разработки программ
Подобный материал:

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


1 курс, 1-й семестр

лекции (51 час), экзамен

практикум на ЭВМ (68 часов), зачет (с оценкой)

Кафедра, отвечающая за курс: системного программирования

Составители программы: чл.-кор. РАН, проф. Иванников В. П.,

доц., канд. физ.-мат. наук Пильщиков В. Н.,

проф., доктор физ.-мат. наук Соловьев С. Ю.

Лекторы: чл.-кор. РАН, проф. Иванников В. П. (1 п.),

доц., канд. физ.-мат. наук Пильщиков В. Н. (2 п.),

проф., доктор физ.-мат. наук Соловьев С. Ю. (3 п.)

Аннотация


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

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


Введение в теорию алгоритмов. Интуитивное понятие алгоритма. Свойства алгоритмов.

Уточнение понятия алгоритма. Машина Тьюринга; тезис Тьюринга. Нормальные алгоритмы Маркова; принцип нормализации. Понятие об алгоритмической неразрешимости.

Характеристика алгоритмических языков. Понятие трансляции.

Понятие о формальных языках. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул и синтаксических диаграмм.

Языки программирования. Общие характеристики языков программирования.

Структура программы на языке Паскаль. Заголовок программы. Блок.

Типы данных, их классификация. Переменные и константы. Скалярные типы данных и операции над ними, стандартные функции. Выражения. Оператор присваивания. Перечислимые и ограниченные типы данных. Стандартные процедуры и функции ввода-вывода.

Операторы, их классификация. Пустой, составной, условный операторы и оператор перехода. Метки. Оператор варианта. Операторы цикла. Структурное программирование.

Составные типы данных. Массивы. Комбинированный тип, оператор присоединения. Множества. Файлы.

Описание процедуры и оператор процедуры. Формальные и фактические параметры. Способы передачи параметров. Локализация имен. Разрешение коллизий. Функции, побочные эффекты. Итерация и рекурсия.

Ссылочные типы данных. Динамические переменные.

Динамические структуры данных. Списки, стеки, очереди, бинарные деревья. Их представление и основные алгоритмы обработки.

Таблицы. Последовательные таблицы. Деревья сравнений. Перемешанные таблицы. Оценки алгоритмической сложности.

Этапы разработки программ. Методы разработки программ (пошаговая детализация и др.). Тестирование и методы составления системы тестов. Отладка.

Литература


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

2. Корухова Л.С., Шура-Бура М.Р. Введение в алгоритмы – М.: МГУ, 1997.

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

4. Pascal ISO 7185:1990 – ссылка скрыта

5. Вирт Н., Йенсен К. Паскаль. Руководство для пользователя и описание языка. – М.: «Компьютер», 1993.

6. Вирт Н. Алгоритмы + структура данных = программа. – СбП.: Невский проспект, 2005.

7. Кнут Д. Искусство программирования. Том 1 - Основные алгоритмы. 3-е изд. – М.: Вильямс, 2000.

8. Кнут Д. Искусство программирования. Том 3 - Сортировка и поиск. 2-е изд. – М.: Вильямс, 2005.

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