Министерство образования Российской Федерации Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”
...
6 downloads
190 Views
286KB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
Министерство образования Российской Федерации Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”
РАБОЧАЯ ПРОГРАММА дисциплины “ПРОГРАММИРОВАНИЕ” Для подготовки дипломированных специалистов по специальностям: 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
Освоение работы с оболочкой (системой программирования) Турбо 2.1, 1.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
Процедуры и функции. Модификация программ из лабораторных ра- 2.4 бот 3 и 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
Тексты, разбитые на страницы. Программа, использующая подпро- 4.9 граммы лабораторной работы №11.
13
Динамическая память. Линейный список с произвольным доступом.
14
Объекты (статические массивы, записи, массивы записей – представ- 4.10, 7.1 ление). Реализация, тестирование модуля.
15
Объекты (статические). Программа, использующая модуль лаборатор- 4.10, 7.1 ной работы № 14.
16
Объекты (динамические). Линейный однонаправленный список (Л1- 4.10, 6.2, 7.3 список). Ссылочная реализация в связанной памяти и на базе вектора. Реализация, тестирование модуля. Программа, использующая модуль.
6.1, 6.2
Перечень аудиторных занятий по курсовому проектированию* №
Наименование темы занятия
Номер темы программы
1 семестр Основные сведения об интегрированной среде Турбо Паскаль (ТП). 2.1-2.3 Требования и порядок выполнения лабораторных работ. Типы целый и bool в ТП. Тип Real в ТП. 2 Программирование цикла While-do (разбор примера к лаб.раб.3). 2.2, 2.3, 3.1 3 Рекуррентное вычисление суммы ряда, вещественные типы. Вывод 2.2, 2.3, 3.1, результатов в файл. 4.1 4 Процедуры и функции. Разбор примеров модификации программ для 2.4 лаб.раб.5. Параметр-функция. 5 Примеры на индуктивные функции. Индуктивные функции на после- 4.1, 4.2 довательностях с элементами типа Char. 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 *Примечание. Для подготовки к выполнению индивидуальных заданий по курсовой работе, имеющейся в учебном плане, требуется тщательная подготовка и проработка как всех тем лабораторных работ, так и общих (для всех студентов) вопросов, связанных с содержанием и технологией выполнения курсовой работы. Для этих целей используются аудиторные часы, отведенные в учебном плане под курсовую работу. Фактически их использование в виде массовых аудиторных («практических») занятий обеспечивает содержательную и технологическую базу (вплоть до фрагментов прототипов) для выполнения индивидуальных заданий по курсовой работе. Далее индивидуальные задания выполняются в режиме самостоятельной работы (в основном с использованием ПЭВМ) и поддерживаются индивидуальными консультациями. 1
Цели и содержание курсового проекта (работы) и его ориентировочная трудоемкость 1 семестр Цель: Законченное поэтапное решение содержательной задачи (постановка задачи, спецификация, выбор структур данных и разработка алгоритма, программная реализация, тестирование).
Основные элементы языка программирования: - основные управляющие структуры; - процедуры и функции; - файлы (для входных и выходных данных); - массивы. Типы заданий содержательно ориентированы на обработку векторов и матриц, реализацию действий с полиномами (представляемыми массивами коэффицинтов), действия с наборами простых геометрических объектов (точек, прямых, окружностей, плоскостей и т.п.). Основные требования к программе: - явное описание типов; - систематическое использование процедур и функций как средства абстракции; - основной способ передачи данных между подпрограммами – через параметры; - наличие комментариев для ключевых фрагментов программы (пост- и предутверждения, инварианы циклов, заголовочные комментарии процедур и функций (внешние спецификации); - систематическое использование файлов для ввода исходных данных и вывода результатов. Ориентировочная трудоемкость 16 часов самостоятельной работы и консультаций с преподавателем. 2 семестр Цель: Полное решение содержательной задачи (содержательная и формальная постановка задачи, спецификация, включая описание диалога , выбор метода решения и структур данных, разработка алгоритма, программная реализация, тестирование и отладка, документирование). Основные элементы языка программирования(дополнительно к требованиям 1 семестра): - рекурсия; - записи, строки, тексты; - динамическая память; - модули; - объекты; - представления и реализация линейных списков; Типы заданий содержательно ориентированы на обработку текстов (простые редакторы текстов, анализаторы текстов, форматирование текстов и т.п.), действия с «длинными» целыми и рациональными числами, действия с полиномами, операции с множествами. Используются преимущественно реализации перечисленных структурированных объектов обработки в виде различного рода линейных списков. Ориентировочная трудоемкость 15 часов самостоятельной работы и консультаций с преподавателем.
Расчет учебных часов по видам занятий № темы
Название разделов (частей) и тем
Введение Часть 1. Тема 1.1.
Основные задачи разработки, верификации и анализа программ Этапы и проблемы решения задач на ПЭВМ Верификация и анализ алгоритмов и программ
Часть 2.
Введение в программирование на языке Паскаль
Тема 2.1.
Общие сведения о языке Паскаль и системе программирования Простые стандартные (предописанные) типы данных
Тема 2.3. Тема 2.4. Часть 3. Тема 3.1. Тема 3.2. Тема 3.3. Тема 3.4. Часть 4. Тема 4.1. Тема 4.2.
Лаборататорные занятия
0.5
Тема 1.2.
Тема 2.2.
Лекции
Основные управляющие структуры и их реализация в языке Паскаль Процедуры и функции Основы конструирования корректных программ Итерация как базисная схема обработки данных Основные правила аналитической верификации программ Правила вывода для структурных операторов языка Паскаль Проектирование цикла с помощью инварианта Обработка структурированных типов данных Последовательность как способ организации данных и файловый тип в языке Паскаль Индуктивные функции на пространстве последовательностей
Аудиторные занятия (в том числе по к/р)*
Самосто ятельная
Всего
Семестр
0.5
1
Работа
0.5
1 1.5
1.5
1
2.5
1
4
4
3
7
1 1
1
2
2
3
2
5
1
2+(1)
2
5
1
2
2
4+(2)
3
9
1
2
2
4+(1)
2
7
1 1
2
2
4+(1)
2
7
1
2
2
2
4
1
4
4+(2)
3
9
1
2
2
2
4
1 1
1
1
2+(1)
2
5
1
4
2
6+(2)
4
12
1
1
1
2
1
Тема 4.3.
Перечисляемый и диапазонный типы в языке Паскаль
1
Тема 4.4.
Массивовый тип в языке Паскаль
2
1
3+(2)
2
7
1
Тема 4.5.
Верификация программ работе с массивами
5
1
6+(2)
3
11
1
при
Тема 4.6.
Процедуры и программирование действий с массивами
2
Тема 4.7.
Линейный и бинарный поиск
Часть 5.** Тема 5.1.
Рекурсия в программировании Рекурсивные определения и алгоритмы Программирование рекурсивных алгоритмов Курсовое проектирование, 1
Тема 5.2.
3
5+(2)
3
10
1
4
4
2
6
1
2
2
2
4
1
4
4
3
7
1
(16)
16
16
1
Семестр 2 Часть 4. (Продолжение) Тема 4.8.
Обработка структурированных типов данных (Продолжение) Сложные типы данных
2
2
4+(1)
3
8
2
Тема 4.9.
Строки
3
2
5+(1)
3
9
2
Тема 4.10.
Модули в языке Турбо Паскаль.
2
1
3
2
5
2
Часть 5.** Тема 5.1.
Рекурсия в программировании Рекурсивные определения и (1) 1 2 2 алгоритмы Тема 5.2. Программирование рекурсив2 2+(1) 2 5 2 ных алгоритмов Часть 6. Динамические структуры дан2 ных Тема 6.1. Ссылочный тип в языке Пас3 3+(2) 3 8 2 каль и рекурсивные типы данных Тема 6.2. Программирование линейных 3 2 5+(2) 5 12 2 списков Часть 7. Элементы объектно2 ориентированного программирования в языке Турбо Паскаль Тема 7.1. Объекты в языке Турбо Пас4 2 6+(2) 5 13 2 каль Тема 7.2. Наследование 4 2 6+(1) 4 11 2 Тема 7.3. Полиморфизм и динамические 4 2 6+(2) 4 12 2 объекты. Часть 8. Технология конструирования 2 программ Тема 7.1. Жизненный цикл и этапы кон2 2+(1) 1 4 2 струирования программ Тема 7.2. Спецификации программ 2 2+(1) 1 4 2 Заключение 1 1 1 2 2 Курсовое проектирование, 2 (15) 15 15 2 48 16 80 60 140 ИТОГО за 1 семестр: 30 15 60 50 110 ИТОГО за 2 семестр: 78 31 140 110 250 ИТОГО: * Примечание 1: В графе аудиторные занятия указаны отдельно (в круглых скобках) часы, используемые для подготовки к выполнению задания по курсовой работе (см. также примечание к пункту “Перечень аудиторных занятий по курсовому проектированию”). ** Примечание 2 к части 5: − лекции по темам 5.1 и 5.2 читаются в 1-ом семестре (лекционные часы и часть самостоятельной работы учитываются в балансе 1-го семестра); − лабораторные занятия и аудиторные занятия под курсовую работу по темам 5.1 и 5.2 проводятся во 2-ом семестре и эти часы учитываются в балансе 2-го семестра.
ЛИТЕРАТУРА Основная Л
Лр
Кп (р)
К-во экз. в библ. (на кафедре)
№
Название, библиографическое описание
1.
Ивановский С.А. Разработка корректных программ: Учеб.пособие /ГЭТУ.-С.-Пб., 1996.
1
1
1
76
2.
Алексеев А.Ю., Ивановский С.А., Куликов Д.В. Динамические структуры данных. Практикум по программированию/ ГЭТУ. СПб., 1997.
2
2
2
48
3.*
Алагич С., Арбиб М. Проектирование корректных структурированных программ.- М.: Радио и связь, 1984.
1,2
4.
Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов - М.: Наука. Гл.ред.физ.-мат.лит., 1988.
1
1
1
7
5.*
Йенсен К., Вирт Н. Паскаль: руководство для пользователя.- М.: Финансы и статистика, 1989.
1,2
1,2
1,2
210
6.*
Йенсен К., Вирт Н. Паскаль: руководство для пользователя.- М.: Компьютер, 1993.- 256 с.
1,2
1,2
1,2
8
7.
Введение в язык паскаль./Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Учеб. Пособие.- М.: Наука. Гл.ред.физ.-мат.лит., 1988.
1,2
1,2
8.
Ивановский С.А., Прокофьев Ю.Б., Смольянинов А.В. Сборник задач по структурному программированию: Учеб. пособие/Под ред.В.И.Тимохина.- Л.: ЛЭТИ, 1987.
1,2
1,2
1250
9.
Пильщиков В.Н. Сборник упражнений по языку Паскаль: Учеб. пособие для вузов.- М.: Наука. Гл.ред.физ.-мат.лит., 1989.
1,2
1,2
83
37
87
* Примечание. Книги, указанные в пп.3, 5, 6, являются переводами с английского (по этой причине формально не являются учебными пособиями), имеют учебный характер, написаны авторитетными специалистами в данной области и соответствуют по содержанию общей направленности данной дисциплины.
Дополнительная № 10.
Название, библиографическое описание
К-во экз. в библ. (на кафедре)
16.
Абрамов С.А. Математические построения и программирование.-М.: Нет Наука. Гл.ред.физ.-мат.лит., 1978. Андерсон Р. Доказательство правильности программ.- М.: Мир, 1982. 50 Арсак Ж. Программирование игр и головоломок.- М.: Наука, 1990. Нет Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2-х ч.-М.: Мир, Ч.1 – 85 1990. Ч.2 - 85 Бейбер Р.Л. Программное обеспечение без ошибок.- М.: Джон Уайли Нет энд Санз, Радио и связь, 1996. Бентли Д. Жемчужины творчества программистов.- М.: Радио и связь, 21 1990. Вирт Н. Алгоритмы и структуры данных.- М.: Мир, 1989. 218
17.
Вирт Н. Систематическое программирование. Введение.- М.: Мир, 1977.
6
Грис Д. Наука программирования.- М.: Мир, 1984. Дейкстра Э. Дисциплина программирования.- М.: Мир, 1978. Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль.- М.: Финансы и статистика, 1991. 21. Джонстон Г. Учитесь программировать.- М.: Финансы и статистика, 1989. 22. Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ: Учеб. пособие для вузов.- М.: Наука. Гл.ред.физ.-мат.лит., 1986. 23. Морс С.П., Алберт Д.Д. Архитектура микропроцессора 80286: Пер с англ.,М.: Радио и связь, 1990.- 304 с.
15 17 46
11. 12. 13. 14. 15.
18. 19. 20.
1 нет 36
По Турбо Паскалю №
Название, библиографическое описание
24.
Фаронов В.В. Программирование на персональных ЭВМ в среде ТурбоПаскаль. - М.: Изд-во МГТУ, 1991. Фаронов В.В. Турбо Паскаль (в 3-х книгах). Книга 1. Основы Турбо Паскаля. - М.: Учебно-инженерный центр "МВТУ-ФЕСТО ДИДАКТИК", 1992. Фаронов В.В. Турбо Паскаль (в 3-х книгах). Книга 3. Библиотека Turbo Vision. - М.: Учебно-инженерный центр "МВТУ-ФЕСТО ДИДАКТИК", 1993. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие.М.: "Нолидж", 1997. Зуев Е.А. Язык программирования Turbo Pascal 6.0.- М.:Унитех, 1992. Зуев Е.А. Язык программирования Turbo Pascal 6.0,7.0.- М.: Веста, Радио и связь, 1993.
25. 26. 27. 28. 30.
К-во экз. в библ. (на кафедре)
Нет 26 Нет Нет Нет 12
Авторы: к.т.н., доцент к.т.н., доцент
С.А.Ивановский В.П.Самойленко
Рецензент к.т.н., доцент каф.ВМ-1
Г.М.Коновалов
Зав. кафедрой Математического обеспечения и применения ЭВМ (разработчик программы и держатель учебного плана) Д.т.н., профессор
А.Р.Лисс
Декан факультета Компьютерных технологий и информатики (обеспечивающего дисциплину) Д.т.н., профессор
И.В.Герасимов
Зав. отделом учебной литературы
О.Н.Смирнова
Председатель методической комиссии факультета Компьютерных технологий и информатики (обеспечивающего дисциплину) к.т.н., доцент
Л.А.Чугунов
Руководитель методического отдела, к.т.н., доцент
Л.А.Марасина