ОСНОВНОЙ КУРС ДЛЯ СПЕЦИАЛИСТОВ «Алгоритмы и алгоритмические языки»

Обязательный курс для студентов-специалистов 1 курса, читается в 1 семестре

• Лекции – 54 часа, практикум – 72 часа
• Экзамен (в письменной форме), зачет (с оценкой)
• За курс отвечает кафедра алгоритмических языков
• Авторы программы: доцент Л.С. Корухова, доцент В.Н. Пильщиков
• Лекторы в 2007/2008 уч. году: чл.-корр. РАН В.П. Иванников, профессор С.Ю. Соловьев, доцент В.Н. Пильщиков

АННОТАЦИЯ

«Алгоритмы и алгоритмические языки» является начальным курсом по программированию на факультете. Цель курса – ввести базовые понятия программирования.

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

Практическую поддержку курсу обеспечивает «Практикум на ЭВМ». Основные цели практикума:

• практическое изучение алгоритмического языка Паскаль;
• приобретение навыков разработки, тестирования и отладки программ для ЭВМ;
• приобретение практического опыта работы на ЭВМ, в системах программирования.

Практикум включает в себя как семинарские занятия (примерно 75% времени), направленные на закрепление теоретического материала, так и выполнение индивидуальных заданий. В последнем случае студентам заранее предлагается несколько (5-6) несложных задач практически по каждой из изучаемых тем, студенты должны самостоятельно разработать программы решения всех задач, а преподаватель проверяет на компьютере одну-две из этих программ.

ТЕМАТИЧЕСКИЙ ПЛАН КУРСА

1. Введение в теорию алгоритмов 8 8 16 2. Алгоритмические языки. Язык Паскаль 36 44 80 3. Динамические структуры данных 10 12 22

Зачеты - 8 8

• Итого:

54 72 126

• Всего:

(аудиторные занятия и самостоя­тельная работа)

252

СОДЕРЖАНИЕ КУРСА

• Лекции

Часть 1. Введение в теорию алгоритмов Интуитивное понятие алгоритма. Свойства алгоритмов. Уточнение понятия алгоритма, алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Нормальные алгоритмы Маркова. Основные схемы объединения алгоритмов (композиция, разветвление, цикл). Тезис Тьюринга и принцип нормализации, их обоснование. Алгоритмически неразрешимые проблемы. Неразрешимость проблем самопримени­мости, останова и эквивалентности алгоритмов. Модельная ЭВМ. Машинное представление данных. Машинный язык как практический формальный способ записи алгоритмов. Недостатки машинных языков.

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

Часть 3. Динамические структуры данных Списки. Представление списков и реализация основных операций на ними в языке Паскаль. Варианты списков (с заглавным звеном, циклические, двунаправленные). Стек, очередь. Векторное и списковое представления их, реализация операций на ними. Двоичные (бинарные) деревья. Обход дерева с использованием стека, очереди и рекурсии. Деревья поиска (сравнений), алгоритмы поиска, вставки и удаления элементов. Таблицы, операция поиска по ключу. Последовательные таблицы (неупорядоченные и упорядоченные). Понятие о (временнóй) оценке сложности алгоритмов в худшем случае и в среднем. Оценка сложности оптимального алгоритма поиска по ключу. Бинарный поиск в упорядоченных таблицах. Методы сортировки, оптимальные оценки числа сравнений и перемещений при сортировке. Представление таблиц в виде деревьев поиска (сравнений), оценки сложности поиска по ключу в таких таблицах. АВЛ-деревья, оценки сложности поиска, алгоритм вставки. Перемешанные таблицы (хэш-таблицы). Функции расстановки. Устранение коллизий методами закрытого хеширования (линейных проб) и открытого хеширования (цепочек).

Практикум на ЭВМ

Ниже номера задач даны по задачнику [5] для занятий 2-4 и по задачнику [6] для занятий 6-30.

Занятие 1. Системы счисления (с.с.). Определение позиционной с.с. Алгоритмы перевода из одной с.с. в другую. Двоичная система и системы с основанием 2k, правила перевода.

• Задачи: перевод конкретных чисел из одной с.с. в другую;
  • сравнение и сложение чисел, записанных в разных с.с.; перевод чисел из 10-й системы в 2-ю (через 16-ю) и обратно; перевод чисел из 16-й системы в 8-ю (через 2-ю) и обратно
  На дом: задачи того же типа

Занятие 2. Машина Тьюринга (МТ). Структура МТ. Правила записи и выполнения программы МТ.

• Задачи: 1.2, 1.3, 1.7, 1.19, 1.21, 1.24, 1.28, 1.31, 1.33 На дом: 1.6, 1.22, 1.29, 1.30, 1.32, 1.34(б)

Занятие 3. Нормальные алгоритмы Маркова (НАМ). Подстановки. Правила записи и выполнения НАМ.

• Задачи: 2.1, 2.2, 2.11, 2.14, 2.15, 2.16, 2.22, 2.26, 2.43, 2.44, 2.46, 2.49, 2.53 На дом: 2.10, 2.12, 2.20, 2.27, 2.47, 2.55(а,б)

Занятие 4. Задачи по теории алгоритмов. Применимость алгоритма к слову, самоприменимость, эквивалентность и композиция алгоритмов.

• Задачи: 3.2(а–г), 3.4, 3.5(а,г), 3.6 (а,в), 3.9, 3.10(б,е), 3.14(а,в), 3.15(а,в), 3.17(б), 3.19(а) На дом: 3.3(б), 3.5(б,в), 3.6(д), 3.8, 3.10(ж), 3.11(б), 3.14(г), 3.17(в), 3.19(в)

Занятие 5. Метаязыки. Металингвистические формулы (БНФ), синтаксические диаграммы. (В каждой задаче требуется описать в виде БНФ и в виде синтаксической диаграммы указанное словесно понятие)

• Задачи: троичное число без знака и со знаком, без незначащих нулей;
  • алгебраическая сумма из двоичных чисел;

    слова вида anbm (n=m0, n=m>0, n>m0); палиндром из a и b; слово из равного числа a и b; четное троичное число

  На дом: непустая последовательность десятичных чисел, между которыми – запятая, а в конце – точка;
  • любая последовательность из a, b и круглых скобок, сбалансированная по скобкам

Занятие 6. Контрольная работа №1 (по темам занятий 1-5)

Занятие 7. Язык Паскаль. Числовые типы. Идентификаторы. Переменные. Запись чисел. Операции и стандартные функции для чисел. Арифметические выражения. Оператор присваивания.

• Задачи: 1.1, 1.4, 1.5, 1.13–1.19, 1.26(а,в,г), 1.27, 1.28, 1.29(а,б), 1.30(а,б,е–л), 1.34, 1.41(в.е), 1.45(а), 1.46 На дом: 1.21, 1.26(б), 1.29(г,д), 1.33(б,в), 1.40(б,в), 1.45(б), 1.47–1.52

Занятие 8. Логический тип. Отношения. Логические операции и стандартные функции. Логические выражения.

• Задачи: 2.2, 2.3(а–д), 2.5, 2.7, 2.8(г), 2.9(г), 2.10(б–е), 2.12(а–г,к), 2.14(б,е), 2.15(б,в), 2.16(д), 2.17(а,б), 2.19(а–е) На дом: 2.10(ж,з), 2.12(д–з), 2.14(ж), 2.15(г), 2.17(в), 2.19(ж,з)

Занятие 9. Программа. Ввод-вывод. Операторы. (2.9г, 2.17в) Структура программы. Раздел переменных. Стандартные процедуры ввода-вывода. Пустой, составной и условный операторы.

• Задачи: 3.2, 3.7, 3.10, 3.12, 3.13(в), 3.14, 3.17, 3.29(ж), 4.2, 4.5(а,в,г), 4.7(в), 4.8, 4.9, 4.10, 4.12(ж) На дом: 3.19, 3.20, 3.27, 3.28(к), 3.29(б), 4.5(ж), 4.6(в), 4.11, 4.12(в)

Выдача заданий практикума (см. занятие 11).

Занятие 10. Константы. Переходы. Циклы. Константы, раздел констант. Оператор перехода, раздел меток. Операторы цикла. Ограничения на for-циклы.

• Задачи: 3.22, 3.24, 3.26, 4.16, 4.19, 5.5, 5.6(б–д), 5.7(в), 5.11(а,е), 5.16, 5.18 На дом: 3.27, 5.2(г), 5.6(и,к), 5.7(е), 5.11(б–д)

Занятие 11. Работа на ЭВМ.

• Темы заданий: 1) числовые и логический типы; 2) программы без цикла. Возможные задания: 1) 3.28(в,д,з), 3.29(а,д,е); 2) 4.12(а,б,г–ж)

Занятие 12. Циклы. Реализация классических алгоритмов. Структурное программирование. Досрочный выход из for-циклов. Вложенные циклы.

• Задачи: 5.8, 5.10, 5.19(а,б), 5.20(а), 5.21(а), 5.22, 5.26, 5.30(а), 5.34, 5.36 На дом: 5.17, 5.20(в), 5.21(б), 5.27, 5.28, 5.30(в), 5.37, 5.45

Занятие 13. Символьный тип. Особенности символьного типа (состав, количество и упорядоченность символов). Стандартные функции и операции для символов.

• Задачи: 6.1–6.8, 6.11–6.13, 6.17, 6.23(б), 6.26(д), 6.29, 6.30, 6.41(а) На дом: 6.19, 6.23(г), 6.24, 6.25, 6.26(б,в), 6.34

Выдача заданий практикума (см. занятие 15).

Занятие 14. Перечислимые и ограниченные типы. Оператор варианта. Нестандартные типы данных, раздел типов. Перечислимые типы. Ограниченные типы. Оператор варианта.

• Задачи: 7.4, 7.5, 7.7(а,в), 7.9, 7.16, 7.18, 7.19, 7.21, 7.13(а,б), 7.25, 7.28, 7.30 На дом: 7.6, 7.22, 7.24, 7.26, 7.27, 7.29, 7.33

Занятие 15. Работа на ЭВМ.

• Темы заданий: 1) циклы; 2) символьный тип. Возможные задания: 1) 5.12, 5.24, 5.48, 5.52, 5.54, 5.55; 2) 6.21, 6.31, 6.32, 6.33, 6.41(в,д)

Занятие 16. Массивы (векторы). Описание массивов, типы индексов, индексированные переменные.

• Задачи: 8.2, 8.4, 8.6(б,г,д), 8.12, 8.13(а), 8.16(а,д), 8.25(а), 8.26, 8.29(б,г,ж), 8.41(а) На дом: 8.13(б), 8.14, 8.20(в), 8.25(в), 8.27, 8.29(а), 8.41(б), 8.43

Занятие 17. Массивы (матрицы, строки). Описание многомерных массивов. Строковые типы, дополнительные возможности при работе со строками.

• Задачи: 9.2, 9.3(б,г), 9.7, 9.10(а,в), 9.18(а), 9.24(а), 10.1, 10.5(а–в), 10.7, 10.12(а,б) На дом: 9.8, 9.14(в), 9.18(в), 9.24(б), 10.8, 10.11, 10.12(в), 10.13

Выдача заданий практикума (см. занятие 19).

Занятие 18. Контрольная работа №2 (по темам занятий 7–17).

Занятие 19. Работа на ЭВМ.

• Темы заданий: 1) векторы; 2) матрицы, строки. Возможные задания: 1) 8.51, 8.53, 8.55, 8.56, 8.57, 8.59; 2) 9.26, 9.27, 9.31, 10.16(а,в), 10.19

Занятие 20. Процедуры и функции. Раздел процедур и функций. Описание процедур и обращение к ним (оператор процедуры). Формальные и фактические параметры, параметры-значения и параметры-переменные. Локализация имен и меток. Описание функций и обращение к ним. Различие между процедурами функциями.

• Задачи: 11.2(б,в), 11.14, 11.17, 11.22(а,б), 11.29(а), 11.30(а), 11.33(а) На дом: 11.2(д), 11.16, 11.18, 11.22(е), 11.29(в), 11.30(б), 11.31(е)

Занятие 21. Процедуры и функции. Передача параметров по значению и по ссылке. Рекурсивные процедуры и функции. Опережающие описания (forward).

• Задачи: 11.8(а), 12.11, 12.6, 12.12(е), 12.15, 12.23, 12.25, 12.30 На дом: 11.8(б,в), 11.33(в), 12.7, 12.12(в,ж), 12.16, 12.18, 12.24

Выдача заданий практикума (см. занятие 23).

Занятие 22. Процедуры и функции. Записи, оператор присоединения. Побочные эффекты функций. Параметры-функции и параметры-процедуры. Описание записей, локализация имен полей записи, обращение к полям записи. Оператор присоединения.

• Задачи: 11.40, 11.44, 11.46, 13.2(б,г), 13.6, 13.13(д,е), 13.14, 13.18(а), 13.21(а–в), 13.24(а) На дом: 11.41, 11.49, 13.9, 13.17, 13.19(б), 13.21(г,д), 13.24(б), 13.28

Занятие 23. Работа на ЭВМ.

• Темы заданий: 1) процедуры и функции; 2) рекурсия. Возможные задания: 1) 11.50, 11.54, 11.55, 11.56, 11.58, 11.60
  • 2) 12.14, 12.17, 12.26, 12.32, 12.33, 12.35

Занятие 24. Множества. Описание множеств. Конструктор множества. Операции над множествами. Выражения множественного типа.

• Задачи: 14.2–14.13, 14.15, 14.19, 14.20(а), 14.21(а,б), 14.23, 14.25, 14.27(а,б), 14.29(а) На дом: 14.21(в,г), 14.24, 14.27(в), 14.29(г), 14.31, 14.34

Занятие 25. Файлы. Описание файлов. Стандартные процедуры и функции для файлов. Текстовые файлы, дополнительные возможности при работе с текстовыми файлами.

• Задачи: 15.7, 15.13(а), 15.19, 15.23, 15.28(а), 15.38, 15.39, 15.42(а), 15.44(а), 15.46 На дом: 15.8, 15.22, 15.27, 15.33, 15.42(б), 15.44(в), 15.45, 15.48

Выдача заданий практикума (см. занятие 27).

Занятие 26. Файлы. Ссылки. Расширенные возможности при обмене с текстовыми файлами (как при вводе-выводе). Внутренние и внешние файлы. (Особенности работы с файлами в языке Турбо Паскаль – для выполнения следующих заданий практикума.) Динамические переменные и доступ к ним по ссылкам. Ссылочные типы и переменные, операции над ссылками.

• Задачи: 15.53, 15.55, 15.59, 16.4–16.8, 16.11(б), 16.15(б) На дом: 15.54, 15.62, 16.10(в), 16.11(в), 16.13, 16.14, 16.15(а)

Занятие 27. Работа на ЭВМ.

• Темы заданий: 1) файлы и множества; 2) файлы и записи. Возможные задания: 1) 14.38(а–д) (с заменой ввода на чтение из внешнего текстового файла, в котором каждое слово находится в одной строке); 2) 15.63(а–д)

(Замечание: для этих заданий преподаватель должен заранее подготовить внешние файлы.)

Занятие 28. Списки. Понятие списка, отличие от массива. Описание списков. Основные операции над списками. Рекурсивная обработка списков.

• Задачи: 16.18(д,е,л), 16.22(а,б,е), 16.23(а,б,д), 16.25, 16.30(в,з) На дом: 16.19(а), 16.22(г), 16.23(е), 16.29(д), 16.30(г,д,ж,о)

Занятие 29. Очередь. Стек. Двоичные деревья. Очередь и стек: определение, векторное и списковое представления, основные операции. Двоичные (бинарные) деревья: определение, представление и описание; обход дерева с использованием очереди, стека и рекурсии.

• Задачи: 17.2(а), 17.4(в), 17.7(б,ж), 17.8(б,е,и) На дом: 17.2(в), 17.4(а), 17.5(б), 17.7(е,з), 17.8(г,з,к)

Выдача заданий практикума (см. занятие 31).

Занятие 30. Двоичные деревья. Представление формул в виде двоичных деревьев. Деревья поиска (сравнений).

• Задачи: 17.15(а,в,г), 17.17(а,г,ж,з,и) На дом: 17.15(б), 17.17(б,к)

Занятие 31. Работа на ЭВМ.

• Тема заданий: динамические структуры данных Возможные задания – задание №2 из пособия [7].

Занятие 32. Контрольная работа №3 (по темам занятий 20-30).

Оставшиеся занятия: доработка заданий практикума, зачеты.

ЛИТЕРАТУРА Основная литература 1. Э.З. Любимский, В.В. Мартынюк, Н.П. Трифонов. Программирование. – М., «Наука», 1980. 2. В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова. Введение в язык Паскаль. – М., Наука. 1988. 3. Н. Вирт. Алгоритмы и структуры данных. – СбП., Невский диалект, 2001. 4. В.П. Иванников, Л.С. Корухова, В.Н. Пильщиков. Курс «Алгоритмы и алгоритмические языки». Варианты письменного экзамена. (Методическое пособие.) – М., ф-т ВМК МГУ, МАКС Пресс. 2007. 5. В.Н. Пильщиков, В.Г. Абрамов В.Г., А.А. Вылиток, И.В. Горячая. Машина Тьюринга и алгоритмы Маркова. Решение задач. (Учебно-методическое пособие.) – М., ф-т ВМК МГУ, МАКС Пресс, 2006. 6. В.Н. Пильщиков. Язык Паскаль: упражнения и задачи. – М., Научный мир, 2003. 7. Н.П. Трифонов, В.Н. Пильщиков. Задания практикума на ЭВМ. (Учебное пособие для студентов 1-го курса.) – М., ф-т ВМК МГУ, МАКС Пресс, 2007.

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