НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Кафедра вычислительной математики
ПРОГРАММА
курса лекций по
ПРОГРАММИРОВАНИЮ
для студентов 1-го курса
по специальностям
"механика" и "прикладная математика"
на 1987-88 учебный год
I семестр

1. Введение (/I/ - разделы 1-7; /2/ - гл.I; /3/ - введение; /4/ -введение, параграфы 1.1, 2.1, 2.2, 4.16 4.2, 6.3).

Основные понятия: алгоритм, ЭВМ, программа и данные, стандартные подпрограммы и языки высокого уровня, основные этапы решения задач на ЭВМ.

Синтаксис и семантика языка. Лексемы и понятия. Способы задания синтаксиса: металингвистические формулы и синтаксические диаграммы. Алфавит Паскаля и правила записи Паскаль-программ.

2. Построение простых ациклических программ (/I/ - раздел 8; /2/ - гл. 2-3; /3/ - гл.I).

Стандартные типы данных; простые типы данных; переменные и константы; операции и стандартные функции; логический тип; тип целый; вещественный тип; литерный тип.

Выражения. Старшинство операций. Операторы: понятие оператора (простого и сложного); оператор присваивания, составной оператор, операторы ввода и вывода, условный оператор. Общий вид программы: заголовок, разделы описаний (разделы констант и переменных) и операторная часть.

Доказательство свойств программ: внешняя спецификация программы; метод промежуточных утверждений.

3. Построение итеративных программ (/I/ - разделы 9, 13, 15; /2/ - гл.3; /3/ - гл.2).

Управление вычислениями и блок-схемы.

Операторы цикла: оператор цикла с условием на продолжение, свойства оператора цикла, оператор цикла с условием на окончание, операторы цикла с параметрами.

Пошаговая разработка программ.

4. Разработка программ со структурированными данными (/I/ - раздел 11; /2/ - параграфы 5.1, 5.2, гл.6; /3/ - гл. 3).

Простые типы данных, определяемые программистом: раздел определений типов; задание отрезков типов; типы, заданные перечислением значений.

Структурированные типы данных: записи, массивы, матрицы и таблицы.

Доказательство свойств программ со структурированными данными.

5. Разработка программ с подпрограммами (/I/ - разделы 12 и 15; /2/ - гл.4; /3/ - гл.4).

Процедуры, их описания и операторы вызова. Формальные и фактические параметры, правила их соответствия. Изменение действия - параметры-значения. Получение результатов - параметры-переменные. Вычисление единственного значения - функции.

Блоки, области действия описаний и области существования объектов, локальные и нелокальные объекты. Использование процедур и функций для пошаговой разработки программ: нисходящий и восходящий подходы.

Рекурсия. Понятие глубины рекурсии - текущей и максимальной. Поколения переменных. Достоинства и недостатки рекурсивного представления алгоритмов. Метод структурной индукции.
 

Темы семинарских занятий

1. Понятие алгоритма и программы. Средства и организация численных вычислений (/6/ - параграф I; /8/ - N 1.1).

2. Линейная нотация и способы задания синтаксиса (/6/ - параграф 1;
/8/ - N 1.16, 1.17).

3. Логический и литерный типы (/6/ - параграф I; /8/ - N 1.6 - 1.11)

4. Составной и условный операторы (/6/ - параграф 2; /8/ - N 1.2 - 1.5, 1.12 - 1.15)

5. Оператор цикла с условием на продолжение (/6/ - параграфы 3 - 6;
/8/ - N 2.1 - 2.51).

6. Пошаговая разработка программ. Часовая контрольная на составление программы для обработки последовательности переменной длины.

7. Разбор результатов контрольной работы. Понятие стандартного и определяемого типа. Определение констант и простых типов (/8/ - N 2.53-2.54).

8. Типы массивов и записей (/6/ - параграфы 7, 8; /8/ - N 4.1 - 4.22).

9. Операторы циклов с параметрами (/6/ - параграфы 7-9; /8/- N 3.1-3.27).

10. Процедуры. Параметры-значения и параметры-переменные (/6/ - параграф II; /8/ - варианты а задач N 5.1 - 5.6).

11. Функции, их отличия от процедур (/6/ - параграф 11; /8/- варианты б задач N 5.1 -5.6).

12. Обработка матриц и таблиц с использованием процедур и функций (/6/ - параграфы 9-11; /8/ - N 5.7 - 5.26).

13. Итоговая контрольная. Состоит из двух задач. Одна из них аналогична задаче из первой контрольной, а другая - это задача, предполагающая реализацию таблицы и требующая процедуры для ввода таблицы и функции для поиска в таблице элемента, удовлетворяющего определенным свойствам.
 
 

2 семестр

6. Техника решения задач на ЭВМ (/2/ - гл. 10; /7/- параграф 3.5, гл.4 и 5).

Оформление задания для выполнения Паскаль-программ на ЭВМ. Этапы прохождения задания на ЭВМ и диагностика ошибок на каждом этапе. Отладка и система тестов. Счетчики и вставка утверждений.

7. Дополнительные средства языка Паскаль (/1/ - разделы 10, 14; параграф 12.4; /2/ - параграфы 5.3 -5.5, гл. 7,9).

Операторы выбора. Метки и операторы перехода, их дисциплинированное употребление.

Необходимость объединения типов - записи с вариантами. Типы множеств. Типы файлов. Эквивалентность и согласование типов.

Процедуры и функции как параметры.

8. Вопросы реализации внеязыковых типов данных (/2/ - гл.8; /4/ - гл.3;
/7/ - параграфы 9.1, 10.1).

Типы списков, стеков и очередей. Типы деревьев. Реализация списков, стеков, очередей и деревьев с помощью массивов и записей.

Указатели и генерация элементов памяти. Использование указателей и динамических переменных для реализации списков, стеков, очередей и деревьев.

9. Элементы языка Фортран (/4/ - параграфы 7.1 - 7.4, 7.6; /7/ - параграф 11.1).

Алфавит Фортрана, константы и имена. Правила записи Фортран-программ.

Типы и размеры значений. Массивы и расположение их элементов. Описания и возможность умолчаний, задание начальных значений. Эквивалентность переменных.

Выражения и встроенные функции. Операторы присваивания.

Операторы управления вычислениями: операторы безусловных и вычисляемых переходов, условные операторы, операторы продолжения и останова, циклы.

Форматы, форматные ввод и вывод, список вывода и неявные циклы.

Простые программы на Фортране, описательная и операторная части, операторные функции.

Структурированные Фортран-программы и средства повышения наглядности Фортран-программ.

10. Модульное программирование на Фортране (/4/ - параграфы 6.1, 7.5, 7.7, 7.8; /7/ - параграф 11.2).

Модульная структура программы на Фортране: головной модуль, модули-подпрограммы, модули-функции. Задание общих данных модулей. Модули инициализации.

Реализация сложно структурированных данных на языке Фортран. Нисходящее проектирование Фортран-программ.

11. Особенности решения задач на Фортране (/7/ - параграфы 11.3 -11.5).

Оформление задания на выполнение Фортран-программы и этапы прохождения задания через ЭВМ.

Средства отладки Фортран-программ: диагностика ошибок, пакеты и операторы отладки. Особенности отладки Фортран-программ. Защитное программирование на Фортране.
 

Темы семинарских занятий

1. Использование процедур и функций для пошаговой разработки программ (/6/ - параграфы 9-11; /8/ - N 5.7 - 5.26).

2. Рекурсивные процедуры и функции (/6/ - параграф 12; /8/ - N 6.12-6.23).

3. Множества и файлы (/8/ - N 8.1 - 8.29).

4. Организация динамической памяти и ее использование для реализации списков и деревьев (/8/ - N 7.1 -7.15).

5. Основные конструкции языка Фортран (в сравнении с аналогичными конструкциями языка Паскаль)(/5/ - N 135-255).

6. Организация ввода-вывода и структурное программирование на языке Фортран (/5/ - N 271-359).

7. Модульное программирование на Фортране (/5/ - N 360-386).

8. Итоговая контрольная. Состоит из двух задач: одна - эта задача на составление Фортран-программы для обработки последовательности переменной длины, а другая - Паскаль-программы для обработки последовательности таблиц.

9. Зачет.

Литература
Учебники

1. Вирт Н. Систематическое программирование. Введение.- М.: Мир, 1977.
2. Грогоно П. Программирование на языке Паскаль. - М.:Мир,1982.
3. Касьянов В.Н. Основы программирования на языке Паскаль.- Новосибирск: НГУ, 1987.
4. Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. - М.: Наука, 1980.

Задачники

5. Бухтияров А.М., Фролов Г.Д. Сборник задач по программированию на алгоритмических языках.- М.:Наука, 1978.
6. Касьянов В.Н., Сабельфельд В.К. Сборник заданий по программированию. - Новосибирск: НГУ, 1986.
7. Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.:Наука, 1986.
8. Сборник упражнений по программированию на языке Паскаль /Агафонов В.Н., Бежанова М.М., Поттосин И.В., Сабельфельд В.К.- Новосибирск: НГУ, 1985.

Дополнительная литература

9. Вирт Н. Алгоритмы + структуры данных = программы. М.:Мир,1985.
10. Грис Д. Наука программирования. - М.:Мир, 1984.
11. Йенсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка. - М.:Финансы и статистика, 1982.
12. Уэзерелл Ч. Этюды для программирования. - М.:Мир,1982.

 

Программу составил
доцент В.Н. Касьянов