ПРОГРАММИРОВАНИЕ

Лектор: член-корр. РАЕН, д.ф.-м.н., профессор В.Н. Касьянов

2024 / 2025 учебный год

1. Введение

Понятие алгоритма и его основные свойства, блок-схемные определения как пример уточнения понятия алгоритма. Понятие компьютера, принципы Фон-Неймана. Основные приемы упрощения решения задач на компьютере. Понятие операционной системы, загрузчика, редактора связей, ассемблера и макроассемблера.

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

2. Простые программы без циклов

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

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

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

Выражения. Операторы. Оператор присваивания. Составной оператор. Ввод-вывод. Общий вид программы.

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

Блок-схемы. Условные операторы. Операторы выбора. Доказательство свойств ветвящихся программ.

3. Итеративные программы

Оператор цикла с условием на продолжение. Доказательство свойств итеративных программ, понятие ограничивающего выражения. Оператор цикла с условием на окончание. Операторы цикла с параметрами. Другие операторы управления порядком выполнения.

Метод промежуточных утверждений для блок-схемного представления алгоритмов, теорема о его корректности.

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

4. Программы обработки структурированных данных

Структурированные типы данных: структуры и массивы. Матрицы и таблицы. Представление массивов и структур на машинном уровне, упаковка и выравнивание, виды массивов в языках программирования. Записи с вариантами и объединения. Множества, их представление на машинном уровне.

Файлы в языках программирования. Средства ввода и вывода. Библиотечные типы.

Средства описания свойств программ со структурированными данными.

5. Программы с подпрограммами

Механизм подпрограмм, простая структура вызовов-возвратов, задачи, сопрограммы и подпрограммы прерывания. Описание и вызов подпрограммы. Блоки и правила локализации имен. Локальные, глобальные и стандартные имена. Вычисление единственного значения – функции, побочные эффекты.

Механизм параметров, ключевые и позиционные параметры, способы подстановки параметров. Правила связывания фактических и формальных параметров в разных языках программирования. Изменение действий – входные параметры. Получение результатов – выходные параметры. Реализация "обобщенных" алгоритмов в виде подпрограмм с параметрами подпрограммами.

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

Использование подпрограмм для пошаговой разработки программ, особенности восходящего и нисходящего подходов.

6. Более сложные программы

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

Стеки и очереди, способы их реализации.

Деревья, упорядоченные и бинарные деревья. Способы их реализации. Обходы деревьев. Деревья поиска целых чисел, их использование для решения задач сортировки.

Графы, способы их реализации. Обходы графов.

Абстрактные и инкапсулированные типы данных.

Принципы и основы структурного программирования. Модули и модульное проектирование программ.

План семинарских занятий

1. Понятие алгоритма и программы. Построение линейных программ обработки числовых данных.

2. Стандартные и конструируемые простые типы данных. Построение ветвящихся программ.

3. Операторы цикла с условием на продолжение и окончание. Обработка текстов и числовых последовательностей переменной длины.

4. Типы структур. Обработка последовательностей структур переменной длины.

5. Типы массивов. Операторы цикла с параметрами. Задачи сортировки и поиска.

6. Обработка таблиц и матриц.

7. Промежуточная контрольная на составление двух программ, одна из которых требует обработки матрицы, а другая - обработки таблицы.

8. Файлы. Задача внешней сортировки.

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

10. Рекурсия. Рекурсивные методы поиска и сортировки. Порождение комбинаторных объектов.

11. Указатели. Работа со списками, очередями и стеками.

12. Древовидные структуры и их реализация. Обходы деревьев.

13. Графы и их реализация. Алгоритмы обработки графов.

14. Модули и модульное проектирование программ.

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

Задания по компьютерному практикуму

Студент получает три индивидуальных семестровых задания из разных тематических разделов сборника заданий [11].

Литература

1. Абрамов С.А., Зима Е.В. Начала информатики. М.: Наука, 1980.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

3. Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс. М.: Мир, 1990, Часть 1,2.

4. Бежанова М.М., Поттосин И.В. Современные понятия и методы программирования. М.: Научный мир. 2000.

5. Брой М. Информатика. М.: Диалог- МИФИ, 1996, Часть 1-4.

6. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. М.: Мир, 1981.

7. Вирт Н. Систематическое программирование: Введение. М.: Мир, 1977.

8. Грис Д. Наука программирования. М.: Мир, 1984.

9. Керниган Б., Ритчи Д., Фбюэр А. Язык программирования Си. Задачи по языку Си. М.: Финансы и статистика, 1985.

10. Касьянов В.Н. Курс программирования на Паскале в заданиях и упражнениях. Новосибирск: НГУ, 2001.

11. Касьянов В.Н., Касьянова Е.В. Практикум по программированию. Новосибирск: НГУ, 2013.

12. Касьянов В.Н., Касьянова Е.В. Теория вычислений. Новосибирск: НГУ, 2018.

13. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб: БХВ-Петербург, 2003.

14. Кнут Д. Искусство программирования. М.: Мир, 1976, Том 1-3.

15. Лавров С.С. Программирование. Математические основы, средства, теория. СПб: БХВ-Петербург, 2001.

16. Мейер Б., Бодуэн К. Методы программирования. М.: Мир, 1982, Том 1,2.

17. Хьюз Дж., Мичтом Дж. Структурный подход к программированию. М.: Мир, 1985.
18. Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 1995.