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

/!\ Ниже приводится практикум по курсу АиЯИ на основе Паскаля. Предполагается вычитать задачи и адаптировать его к курсу АиЯИ на основе Питона.

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

Практикум по первой части можно не модифицировать, т. к. не предполагается модификация лекций.

Обозначения:

Практикум

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

/!\ TODO задачник по Python?

Занятие 1. Системы счисления (с. с.)

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

Задачи:

На дом: задачи того же типа

Занятие 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. Метаязыки

Металингвистические формулы (БНФ), синтаксические диаграммы.

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

Задачи:

На дом:

Занятие 6. Контрольная работа № 1

(по темам занятий 1-5)

Занятие 7. Язык Питон. Числовые типы.

Идентификаторы. Переменные

. Запись чисел. Операции и стандартные функции для чисел. Арифметические выражения. Математические функции

. Оператор присваивания

. Связывание. Имена. Операция связывания. Множественное присваивание

.

Задачи: 1.1, 1.4

, 1.5

, 1.13–1.16

, 1.17, 1.18

, 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. Ввод-вывод. Строки. Преобразование типов. Форматирование вывода.

Занятие 9. Программа. Ввод-вывод. Операторы

Структура программы. Раздел переменных. Стандартные процедуры ввода-вывода

Строковая природа ввода-вывода. Строковые константы. Преобразование типов. Форматирование вывода. Ввод с преобразованием типа, использование .split(). Ввод с вычислением введённого выражения с помощью eval(). Достоинства и недостатки обоих способов.

Тему «Пустой, составной и условный операторы.» перенести на следующее занятие

Задачи: 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. Условный оператор и циклы

Занятие 10. Константы. Переходы. Циклы

Задачи: 3.22

, 3.24, 3.26

На дом: 3.27

, 5.2(г)

, 5.6(и,к), 5.7(е), 5.11(б–д)

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

Темы заданий:

  1. числовые и логический типы;
  2. программы без цикла.

Возможные задания: 1) 3.28(в,д,з), 3.29(а,д,е); 2) 4.12(а,б,г–ж)

Занятие 12. Циклы

Реализация классических алгоритмов. Структурное программирование. Досрочный выход из for-циклов. Обращение к элементу строки. else для циклов на примере задачи поиска

. Вложенные циклы.

Задачи: 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

Занятие 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

Занятие 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.

Python/PythonAlgorithmCourse/Practicum (последним исправлял пользователь FrBrGeorge 2015-06-24 02:09:06)