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

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

АННОТАЦИЯ

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

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

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

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

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

Название темы

Аудиторные занятия (часы)

Самостоятельная работа студента

лекции

практикум

1.

Введение в теорию алгоритмов

8

8

16

2.

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

36

44

80

3.

Динамические структуры данных

10

12

22

Зачеты

-

8

8

Итого:

54

72

126

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

252

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

Лекции

Часть 1. Введение в теорию алгоритмов

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

Часть 2. Алгоритмические языки. Язык Паскаль

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

Часть 3. Динамические структуры данных

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

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

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

Занятие 1.

Занятие 2.

Занятие 3.

Занятие 4.

Занятие 5.

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

Задачи
троичное число без знака и со знаком, без незначащих нулей;
  • алгебраическая сумма из двоичных чисел;
    • слова вида anbm (n=m≥0, n=m>0, n>m≥0);

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

Занятие 6.

Занятие 7.

Занятие 8.

Занятие 9.

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

Занятие 10.

Занятие 11.

Занятие 12.

Занятие 13.

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

Занятие 14.

Занятие 15.

Занятие 16.

Занятие 17.

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

Занятие 18.

Занятие 19.

Занятие 20.

Занятие 21.

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

Занятие 22.

Занятие 23.

Занятие 24.

Занятие 25.

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

Занятие 26.

Занятие 27.

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

Занятие 28.

Занятие 29.

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

Занятие 30.

Занятие 31.

Занятие 32.

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

ЛИТЕРАТУРА

Основная литература

  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.

PascalAAL (последним исправлял пользователь FrBrGeorge 2015-06-19 16:50:15)