Программирование
| Вид материала | Лекции |
- Введение в линейное программирование линейное программирование (ЛП), 139.72kb.
- Аттестационное тестирование в сфере профессионального образования, 72.49kb.
- Лекции по дисциплине «Социальное моделирование и программирование», 44.69kb.
- Программа вступительного экзамена по специальности 05. 13. 18 Математическое моделирование,, 115.33kb.
- Курс является базовым как для изучения других математических дисциплин, так и для более, 36.89kb.
- 1 Обобщенное программирование. Обобщенное программирование это еще одна парадигма программирования,, 55.18kb.
- Учебная программа (Syllabus) Дисциплина: Программирование на алгоритмических языках, 201.87kb.
- Программа дисциплины Математическое программирование Семестры, 10.84kb.
- Линейное программирование, 346.17kb.
- Н. И. Лобачевского Факультет Вычислительной математики и кибернетики Кафедра Математического, 132.68kb.
Министерство образования Российской Федерации
Санкт-Петербургский государственный электротехнический
университет “ЛЭТИ”
РАБОЧАЯ ПРОГРАММА
дисциплины
“ П Р О Г Р А М М И Р О В А Н И Е ”
Для подготовки дипломированных специалистов по специальностям:
073000 – “ПРИКЛАДНАЯ МАТЕМАТИКА”
220400 – “ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ”
Для подготовки бакалавров по направленям:
510200 – “ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА”
552800 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА”
Санкт-Петербург
2000
Санкт-Петербургский государственный электротехнический
университет “ЛЭТИ”
“УТВЕРЖДАЮ”
Проректор по учебной работе
проф. ___________ Ушаков В.Н.
РАБОЧАЯ ПРОГРАММА
Дисциплины
“ П Р О Г Р А М М И Р О В А Н И Е ”
Для подготовки дипломированных специалистов по специальностям:
073000 – “ПРИКЛАДНАЯ МАТЕМАТИКА”
220400 – “ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ”
Для подготовки бакалавров по направленям:
510200 – “ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА”
552800 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА”
Факультет компьютерных технологий и информатики (ФКТИ)
Кафедра математического обеспечения и применения ЭВМ (МО ЭВМ)
Курс – 1
Семестры – 1, 2
| Лекции | 78- ч. | | Экзамен – 1, 2 | семестр |
| | | | | |
| | | | | |
| Лабораторные занятия | 31- ч. | | Зачет – 1, 2 | семестр |
| | | | | |
| Курсовое проектирование | 31- ч. | | Курсовая работа – 1, 2 | семестр |
| Аудиторные занятия | 140- ч. | | |
| Самостоятельные занятия | 110- ч. | (число часов из учебного плана) | |
| Всего часов | 250- ч. | | |
2000
Рабочая программа обсуждена на заседании кафедры МО ЭВМ
“____”_______________2000г., протокол №______.
Рабочая программа составлена в соответствии с государственными образовательными стандартами по направлениям и специальностям –
073000 – “ПРИКЛАДНАЯ МАТЕМАТИКА”
220400 – “ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ”
510200 – “ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА”
552800 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА”
Рабочая программа согласована с рабочими программами изученных ранее дисциплин:
1) Информатика (1 семестр)
Рабочая программа утверждена на методической комиссии ФКТИ
“____”_____________2000г.
Цель и задачи дисциплины
Цели дисциплины
Целью дисциплины «Программирование» является изучение и освоение базовых понятий, методов и приемов программирования, применяемых на всех основных этапах жизненного цикла программы. Дисциплина является базовой в программистском образовании дипломированных специалистов по специальностям: 073000 – “Прикладная математика”, 220400 – “Программное обеспечение вычислительной техники и автоматизированных систем” и бакалавров по направленям: 510200 – “Прикладная математика и информатика”, 552800 – “Информатика и вычислительная техника”.
Задачи дисциплины
- Сформировать взгляд на программирование как на систематическую научно-практическую деятельность, носящую массовый характер (производство программ заданного качества в заданные сроки).
- Сформировать базовые теоретические понятия (возможно, на элементарном уровне), лежащие в основе процесса конструирования программ, в том числе:
- Заложить основы разработки надёжных программ, акцентируя внимание как на методах аналитической верификации и разработке корректных программ, так и на технике (технологии) их испытания (тестирования и отладки).
- Заложить в основу конструирования и использования сложных (динамических) структур данных модель (парадигму) абстрактного типа данных, с последующим переходом к объектно-ориентированному подходу.
- Дать навыки технологии разработки корректных программ, (относительно) инвариантные к используемому языку программирования высокого уровня и опирающиеся на универсальную модель вычислительной машины.
- Научить реализации корректных программ на выбранном рабочем языке программирования (Паскаль) с учётом особенностей его конкретной реализации на персональной ЭВМ (конкретной системы программирования – Турбо Паскаль).
- Продемонстрировать теоретически и на практике целесообразность и возможность конструктивного использования базовых теоретических понятий, методов и приемов (абстрактных схем) программирования.
- Сформировать начальные представления и знания об анализе сложности алгоритмов и программ.
Требования к уровню освоению содержания дисциплины
В результате изучения дисциплины студенты должны
- (а) Знать
- способы постановки и спецификации задач для решения на ПЭВМ;
- основные современные методы и средства разработки корректных структурированных алгоритмов и программ;
- технологию работы на персональной ЭВМ (ПЭВМ) , правила и приемы диалоговой работы на ПЭВМ при программировании типовых задач;
- объектно-ориентированные расширения языка Паскаль;
- способы записи и документирования алгоритмов и программ;
- способы испытания и отладки программ;
(б) Уметь
- самостоятельно осуществлять постановку и спецификацию задачи для решения на ПЭВМ;
- самостоятельно составлять, отлаживать, тестировать и документировать программы на языке Паскаль персональных ЭВМ (Турбо Паскаль);
- доказывать корректность ключевых фрагментов составленных алгоритмов и программ;
(в) Иметь представление о
- методах и проблемах доказательства правильности программ;
- анализе некоторых задач и алгоритмов;
- проблемах оптимизации программ;
- абстрактных типах данных (на примерах), их спецификации, представлении и реализации в языке Паскаль;
- основных понятиях объектно-ориентированного программирования и их реализации в языке Турбо Паскаль;
- технологии производства программ.
Содержание рабочей программы
Введение
Предмет дисциплины и ее задачи. Содержание и форма проведения занятий. Связь с другими дисциплинами учебного плана специальности.
Часть 1. Основные задачи разработки, верификации и анализа программ
Тема 1.1. Этапы и проблемы решения задач на ПЭВМ
Решение задач на ПЭВМ. Основные этапы и проблемы конструирования программ. Постановка задачи и спецификация. Цели и методы верификации программ. Аналитическая верификация (доказательство корректности) и испытание программы. Программа как продукт. Что такое хороший алгоритм и хорошая программа?
Тема 1.2. Верификация и анализ алгоритмов и программ
Пример разработки, верификации и анализа алгоритма. Алгоритм Евклида для нахождения НОД двух чисел. Разработка и запись алгоритма в виде блок-схемы. Метод математической индукции и его применение в доказательстве правильности алгоритма. Метод индуктивных утверждений.
Анализ алгоритма Евклида. Простой анализ: логарифмическая сложность, сравнение с тривиальным алгоритмом нахождения НОД. Числа Фибоначчи и анализ алгоритма Евклида. Теорема Ламе.
Обобщенный алгоритм Евклида. Алгоритм Евклида для многочленов.
Проблемы верификации программ. Конструктивный подход: конструирование и верификация. Автоматизация верификации программ.
Часть 2. Введение в программирование на языке Паскаль
Тема 2.1. Общие сведения о языке Паскаль и системе программирования
Общая характеристика языка. Основные объекты программы. Классификация действий и данных.
Программа на языке Паскаль: синтаксис и семантика. Пример программы.
Система программирования на языке Паскаль. Трансляция программ (компиляция и интерпретация). Выполнение программы. Системы поддержки процесса подготовки и выполнения программ.
Тема 2.2. Простые стандартные (предописанные) типы данных
Тип данных как совокупность значений и действий. Принцип строгой типизации. Номенклатура простых типов языка Паскаль. Ординальные (скалярные) типы. Предописанные типы.
Целый тип (Integer). Множество значений, операции, предописанные функции. Определение переменных. Константы. Выражения: синтаксис и семантика. Оператор присваивания.
Булевский (логический) тип (Boolean). Множество значений, операции, предописанные функции. Определение переменных. Константы. Выражения: синтаксис и семантика. Оператор присваивания. Особенности логических выражений в языке Паскаль и старшинство операций. Полное и неполное вычисление логических выражений.
Символьный тип (Char). Множество значений, предописанные функции. Определение переменных. Константы. Особенности реализаций. Способы использования символьного типа в программах.
Вещественный тип (Real). Множество значений, операции, предописанные функции. Определение переменных. Константы. Выражения: синтаксис и семантика. Оператор присваивания. Особенности машинного представления вещественных чисел. Представление с плавающей точкой. Свойства машинной арифметики. Машинное эпсилон. Примеры.
Ввод и вывод значений стандартных типов с использованием стандартных файлов.
Тема 2.3. Основные управляющие структуры и их реализация в языке Паскаль
Основные управляющие структуры программирования. Простая программа и теорема структуры. Примеры преобразования структур.
Структурные операторы языка Паскаль (элементарное рассмотрение). Составной оператор. Условный оператор. Операторы цикла с предусловием и с постусловием: сходство, различие, преобразования. О стиле записи структурных операторов в разных языках программирования.
Бинарный алгоритм Евклида: разработка, структурный вариант, оптимизация и преобразование в неструктурный вариант.
Тема 2.4. Процедуры и функции
Метод последовательных уточнений (пошаговой декомпозиции) и концепция подпрограммы (модуля) в программировании.
Описание и оператор процедуры в языке Паскаль. Формальные и фактические параметры. Классификация параметров по назначению: входные, выходные, модифицируемые (транзитные). Способы передачи параметров. Параметры-значения, параметры-переменные, параметры-константы, процедуральные параметры.
Локальные и глобальные переменные, область действия.
Функции в языке Паскаль. Описание и использование. Побочный эффект. Функциональные параметры. Особенности реализации в разных версиях языка.
Часть 3. Основы конструирования корректных программ
Тема 3.1. Итерация как базисная схема обработки данных
Общая схема цикла с предусловием. Вектор (множество) состояния программы, схема программы и ее интерпретация. Схема итерации и ее свойства. Примеры схемы итерации и ее интерпретаций. Математическая модель итерации. Примеры.
Вычисление рядов как пример итерации. Вычисление рядов и особенности машинной арифметики "вещественных" чисел.
Тема 3.2. Основные правила аналитической верификации программ
Алгоритм (программа) и вычислительный процесс. Сходство и различие задач и методов испытания программы и аналитического доказательства ее корректности.
Аналитический метод верификации программ. Предутверждения и постутверждения. Основные правила для элементарных фрагментов: последовательное соединение, "слияние путей", ветвление, присваивание. Примеры. Слабейшее предусловие (предутверждение) и сильнейшее постусловие (постутверждение). Верификация структуры ветвления. Верификация циклических фрагментов. Пример: схема цикла с предусловием.
Тема 3.3. Правила вывода для структурных операторов языка Паскаль
Последовательная нотация и правила вывода. Правила вывода для составного оператора и условного оператора.
Правило вывода для оператора цикла с предусловием. Инвариант цикла. Ограничивающая функция. Теорема об инварианте и ограничивающей функции цикла с предусловием. Примеры.
Правило вывода для оператора цикла с постусловием. Теорема об инварианте и ограничивающей функции для цикла с постусловием. Примеры.
Индуктивные утверждения и хооровский инвариант цикла.
Тема 3.4. Проектирование цикла с помощью инварианта
Конструктивное использование понятия инварианта цикла при проектировании циклов. Математическая модель схемы проектирования цикла с помощью инварианта. Общий план проектирования цикла с помощью инварианта. Сравнение базисных схем итерации и проектирования цикла с помощью инварианта.
Пример проектирования цикла с помощью инварианта: алгоритм возведения в натуральную степень. "Индийское" возведение в степень и двоичная запись показателя степени. Алгоритм, основанный на анализе двоичной записи показателя "справа налево". Анализ алгоритма.
Часть 4. Обработка структурированных типов данных
Тема 4.1. Последовательность как способ организации данных и файловый тип в языке Паскаль
Математическая модель последовательности над заданным алфавитом. Файл как реализация последовательности.
Определение файлов в языке Паскаль. Базовые операции (Write, Read, Reset, Rewrite, Close) с файлами: наглядное представление и формальная модель (спецификация). Внешние файлы. Связывание файловых переменных с внешней средой. Файлы типа Text.
Типовые действия с файлами: генерация, чтение, копирование.
Особенности работы с текстовыми файлами. Функция Eoln. Типовые действия с текстовыми файлами. Особенности предописанных процедур ввода и вывода.
Тема 4.2. Индуктивные функции на пространстве последовательностей
Определение индуктивной функции на пространстве последовательностей. Схема вычисления индуктивной функции. Схема с вводом элементов последовательности из файла. Примеры. Стационарное значение индуктивной функции.
Индуктивное расширение функций. Примеры. Разные пространства и доопределения. Примеры: вычисление значений полинома и его производных, задача о равнинах, задача о связанной подпоследовательности с максимальной суммой.
Тема 4.3. Перечисляемый и диапазонный типы в языке Паскаль
Перечисляемый тип в языке Паскаль: определение типа, константы, переменные, операции, предописанные функции, реализация ввода и вывода.
Диапазонный типы в языке Паскаль. Базовый тип. Определение диапазонного типа. Операции и предописанные функции. Явное определение и анонимный тип. Примеры использования.
Тема 4.4. Массивовый тип в языке Паскаль
Массив как составной тип данных. Определение типа. Определение переменных-массивов. Операции с переменными-массивами. Логическая структура массивов. Доступ к элементам массива (адресация).
Примеры работы с массивами. Операторы циклов с параметром в языке Паскаль: синтаксис и семантика. Циклы с параметром и обработка массивов. Особенности использования переменных диапазонного и перечислимого типов как индексов массивов и параметров циклов. Примеры.
Тема 4.5. Верификация программ при работе с массивами
Расширение возможностей способов записи утверждений: кванторы. Квантор существования: неформальное и формальное определения, примеры. Квантор всеобщности: определения и примеры. Квантор количества. Примеры использования кванторов в утверждениях о массивах. Картинки и вырезки (сегменты) массивов.
Правило вывода для операторов цикла с параметром.
Примеры конструирования и верификации программ с одномерными массивами. Индуктивные функции на массивах. Задача о равнинах: решение с массивом и его сравнение с решением, использующим файл.
Тема 4.6. Процедуры и программирование действий с массивами
Массивы в качестве параметров процедур и функций. Процедуры и функции как инструмент определения и реализации действий с массивами. Особенности использования многомерных массивов и их компонент в качестве параметров процедур и функций. Примеры обработки матриц с использованием процедур.
Открытые массивы в языке Турбо Паскаль.
Тема 4.7. Линейный и бинарный поиск
Задача поиска элемента массива. Линейный поиск. Варианты решения. Доказательство корректности. Общая схема линейного просмотра.
Задача поиска места элемента в упорядоченном массиве. Спецификация задачи. Разработка корректной программы бинарного поиска. Анализ алгоритма бинарного поиска. Дерево бинарного поиска. Оптимальность алгоритма бинарного поиска.
Оптимизация программы бинарного поиска. Быстрый вариант с развертыванием цикла.
Тема 4.8. Сложные типы данных
Записные типы. Определения. Синтаксис и семантика (множество значений, константы, операции). Записи со структурированными полями. Массивы записей. Примеры использования. Оператор присоединения with. Записи с вариантами. Рекомендации по применению. Оособенности применения записей в программах.
Множественные типы. Определение типа. Конструкторы множеств. Операции над множествами. Примеры использования. Особенности реализации.
Тема 4.9. Строки
Строки. Определение, операции над строками. Представление строк (с явной длиной, с символом ограничителем). Реализация типовых операций над строками (анализ и редактирование строк).
Тип string языка Турбо Паскаль. Стандартные операции над данными типа string.
Обработка текстов. Тексты, разделенные на слова. Представление и обработка текстов, разделенных на страницы.
Тема 4.10. Модули в языке Турбо Паскаль.
Назначение, реализация и примеры использования. Модули как средство абстракции данных.
Часть 5. Рекурсия в программировании
Тема 5.1. Рекурсивные определения и алгоритмы
Рекурсивные определения и рекурсивные функции. Рекурсивные алгоритмы. Выполнение рекурсивных алгоритмов: подготовка трассы, стек (магазин).
Анализ рекурсивных алгоритмов. Рекуррентные уравнения. Соотношение время-память для рекурсивных алгоритмов.
Тема 5.2. Программирование рекурсивных алгоритмов
Рекурсивные процедуры и функции в языке Паскаль. Опережающее описание. Приемы рекурсивного программирования (нисходящая и восходящая рекурсия, накапливающие параметры). Примеры: простая рекурсия, программы с несколькими рекурсивными вызовами, косвенная рекурсия (взаимно-рекурсивные подпрограммы).
Преобразование рекурсивных программ в итеративные (“избавление” от рекурсии). Примеры.
Часть 6. Динамические структуры данных
Тема 6.1. Ссылочный тип в языке Паскаль и рекурсивные типы данных
Ссылочные и идентифицированные (динамические) переменные. Действия над ссылками и динамическая память.
Применение ссылочных переменных при программировании на языке Паскаль. Определяемые рекурсивные типы данных. Цепное представление последовательностей. Линейный список с произвольным доступом. Представление в связанной памяти. Программирование основных операций.
Тема 6.2. Программирование линейных списков
Линейный однонаправленный список (Л1-список) как абстрактный тип данных. Функциональная спецификация Л1-списка.
Ссылочная реализация Л1-списка в связанной памяти. Представление и реализация Л1-списка на языке Паскаль.
Ссылочная реализация ограниченного Л1-списка на базе вектора. Представление и реализация на языке Паскаль.
Разновидности линейных списков: циклические, двунаправленные (Л2-списки). Примеры.
Часть 7. Элементы объектно-ориентированного программирования в языке Турбо Паскаль
Тема 7.1. Объекты в языке Турбо Паскаль
Основные идеи объектно-ориентированного программирования. Объектовый тип и экземпляр объектового типа. Данные и методы объекта. Инкапсуляция. Наследование. Полиморфизм.
Объекты как средство абстракции данных. Объекты языка Турбо Паскаль. Типы данных (статические массивы, записи, массивы записей) и их представление при помощи объектов. Реализация векторного представления Л1-списка.
Тема 7.2. Наследование
Наследование членов-переменных и методов. Переопределение методов. Проблемы наследования статических методов.
Тема 7.3. Полиморфизм и динамические объекты.
Полиморфизм. Виртуальные методы. Динамические объекты. Конструктор, деструктор.
Использование динамических объектов. Представление линейных списков (ЛС-1, Л2-списки, циклические списки).
Часть 8. Технология конструирования программ
Тема 8.1. Жизненный цикл и этапы конструирования программ
Жизненный цикл программы. Анализ требований, проектирование, реализация, сопровождение. Особенности и этапы проектирования. Испытание (тестирование и отладка) программ. Сквозные мероприятия: документирование, подготовка и планирование испытаний. Программный продукт.
Тема 8.2. Спецификации программ
Анализ требований и постановка задачи. Формализация постановки задачи. Особенности постановки задачи для ПЭВМ. Спецификация задачи (программы). Свойства и средства спецификации. Анализ и описание диалога. Сценарий диалога. Пример спецификации диалоговой программы.
Заключение
Основные тенденции и направления развития методов и языков программирования на ПЭВМ. Инструментальная поддержка и автоматизация конструирования программ.
Перечень лабораторных работ
| № | Наименование работы | Номер темы |
| | 1 семестр | |
| 1 | Освоение работы с оболочкой (системой программирования) Турбо Паскаль. Работа с готовыми программами: Алгоритм Евклида и Числа Фибоначчи; экспериментирование. | 2.1, 1.2 |
| 2 | Программирование ветвлений ( if-then-else). | 2.2, 2.3 |
| 3 | Рекуррентные вычисления, цикл While-do, только с целыми типами. | 2.2, 2.3, 3.1 |
| 4 | Рекуррентное вычисление суммы ряда, вещественные типы. | 2.2, 2.3, 3.1 |
| 5 | Процедуры и функции. Модификация программ из лабораторных работ 3 и 4 с использованием процедур и/или функций. | 2.4 |
| 6 | Индуктивные функции на последовательностях (последовательных файлах). | 4.1, 4.2 |
| 7 | Одномерные массивы. | 4.3-4.6 |
| 8 | Двумерные массивы | 4.3-4.6 |
| | 2 семестр | |
| 9 | Файлы-множества (однопроходные алгоритмы). | 3.4, 4.1, 4.2 |
| 10 | Рекурсия | 5.1, 5.2 |
| 11 | Строки (представление строк – запись с явной длиной и с ограничителем). | 4.9 |
| 12 | Тексты, разбитые на страницы. Программа, использующая подпрограммы лабораторной работы №11. | 4.9 |
| 13 | Динамическая память. Линейный список с произвольным доступом. | 6.1, 6.2 |
| 14 | Объекты (статические массивы, записи, массивы записей – представление). Реализация, тестирование модуля. | 4.10, 7.1 |
| 15 | Объекты (статические). Программа, использующая модуль лабораторной работы № 14. | 4.10, 7.1 |
| 16 | Объекты (динамические). Линейный однонаправленный список (Л1-список). Ссылочная реализация в связанной памяти и на базе вектора. Реализация, тестирование модуля. Программа, использующая модуль. | 4.10, 6.2, 7.3 |
Перечень аудиторных занятий по курсовому проектированию*
| № | Наименование темы занятия | Номер темы программы |
| | 1 семестр | |
| 1 | Основные сведения об интегрированной среде Турбо Паскаль (ТП). Требования и порядок выполнения лабораторных работ. Типы целый и bool в ТП. Тип Real в ТП. | 2.1-2.3 |
| 2 | Программирование цикла While-do (разбор примера к лаб.раб.3). | 2.2, 2.3, 3.1 |
| 3 | Рекуррентное вычисление суммы ряда, вещественные типы. Вывод результатов в файл. | 2.2, 2.3, 3.1, 4.1 |
| 4 | Процедуры и функции. Разбор примеров модификации программ для лаб.раб.5. Параметр-функция. | 2.4 |
| 5 | Примеры на индуктивные функции. Индуктивные функции на последовательностях с элементами типа Char. | 4.1, 4.2 |
| 6 | Верификация программ. Упражнения на правила вывода. | 3.2-3.4 |
| 7 | Одномерные массивы. | 4.3-4.6 |
| 8 | Многомерные массивы. | 4.3-4.6 |
| | 2 семестр | |
| 9 | Файлы-множества. | 3.4, 4.1, 4.2 |
| 10 | Рекурсия. | 5.1, 5.2 |
| 11 | Строки. Представление строк (запись с явной длиной, с ограничителем). Тестирование программ. Методики белого и черного ящика. | 4.9, 8.1 |
| 12 | Обработка текстов. Тексты, разделенные на слова. Представление и обработка текстов, разделенных на страницы. | 4.9, 8.2 |
| 13 | Указатели. Динамические переменные. Использование динамических переменных. | 6.1 |
| 14 | Линейный список с произвольным доступом. Программирование основных операций. Разработка представления линейных списков. | 6.1, 6.2 |
| 15 | Объекты (статические массивы, записи, массивы записей). | 7.1 |
| 16 | Объекты (динамические). | 7.2, 7.3 |