Скачать 460.59 Kb.
|
Министерство образования Российской Федерации Санкт-Петербургский государственный электротехнический университет “ЛЭТИ” РАБОЧАЯ ПРОГРАММА дисциплины “ П Р О Г Р А М М И Р О В А Н И Е ”Для подготовки дипломированных специалистов по специальностям: 073000 – “ПРИКЛАДНАЯ МАТЕМАТИКА” 220400 – “ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ” Для подготовки бакалавров по направленям: 510200 – “ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА” 552800 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА” Санкт-Петербург 2000 Санкт-Петербургский государственный электротехнический университет “ЛЭТИ” “УТВЕРЖДАЮ” Проректор по учебной работе проф. ___________ Ушаков В.Н. РАБОЧАЯ ПРОГРАММА Дисциплины “ П Р О Г Р А М М И Р О В А Н И Е ”Для подготовки дипломированных специалистов по специальностям: 073000 – “ПРИКЛАДНАЯ МАТЕМАТИКА” 220400 – “ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ” Для подготовки бакалавров по направленям: 510200 – “ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА” 552800 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА” Факультет компьютерных технологий и информатики (ФКТИ) Кафедра математического обеспечения и применения ЭВМ (МО ЭВМ) Курс – 1 Семестры – 1, 2
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. Спецификации программАнализ требований и постановка задачи. Формализация постановки задачи. Особенности постановки задачи для ПЭВМ. Спецификация задачи (программы). Свойства и средства спецификации. Анализ и описание диалога. Сценарий диалога. Пример спецификации диалоговой программы. ЗаключениеОсновные тенденции и направления развития методов и языков программирования на ПЭВМ. Инструментальная поддержка и автоматизация конструирования программ. Перечень лабораторных работ
Перечень аудиторных занятий по курсовому проектированию*
|
Программа дисциплины философия Программа предназначена для студентов гуманитарных (нефилософских) специальностей и соответствует требованиям государственных образовательных... | Программа дисциплины философия Программа предназначена для студентов гуманитарных (нефилософских) специальностей и соответствует требованиям государственных образовательных... | ||
Программа дисциплины философия Программа предназначена для студентов гуманитарных (нефилософских) специальностей и соответствует требованиям государственных образовательных... | Российской Федерации Министерство образования и науки Программа предназначена для студентов гуманитарных (нефилософских) специальностей и соответствует требованиям государственных образовательных... | ||
Рабочая программа дисциплины "Механика композитных материалов" для... В 2011 – 2012 учебном году дворец творчества детей и молодежи «Преображенский» работал над следующими основными задачами | Программа по формированию навыков безопасного поведения на дорогах... Дисциплина «Экономика и управление энергетическими предприятиями» является одной из профилирующих дисциплин в системе подготовки... | ||
Рабочая учебная программа курса гсэ. Р. 01. «История и культура стран изучаемого языка» Направление подготовки дипломированных специалистов 620100 – "Лингвистика и межкультурная коммуникация" | Комплекс (умк) Учебно-методический комплекс дисциплины «Правовые основы гражданской защиты» для студентов специальности 330600 «Защита в чрезвычайных... | ||
Рабочая программа по учебной дисциплине Средства коммутации в системах Рабочая программа составлена с учетом Государственного образовательного стандарта высшего профессионального образования по направлению... | Рабочая программа по учебной дисциплине Средства коммутации в системах Рабочая программа составлена с учетом Государственного образовательного стандарта высшего профессионального образования по направлению... | ||
Рабочая программа по учебной дисциплине Средства коммутации в системах Рабочая программа составлена с учетом Государственного образовательного стандарта высшего профессионального образования по направлению... | Федеральное агентство по образованию московский государственный университет... Рекомендуется для направления подготовки дипломированных специалистов 230200 – Информационные системы | ||
Рабочая программа по учебной дисциплине Системы и сети мобильной связи Рабочая программа составлена с учетом Государственного образовательного стандарта высшего профессионального образования по направлению... | Рабочая программа по учебной дисциплине Системы и сети связи с подвижными Рабочая программа составлена с учетом Государственного образовательного стандарта высшего профессионального образования по направлению... | ||
Рабочая программа по учебной дисциплине Системы и сети мобильной связи Рабочая программа составлена с учетом Государственного образовательного стандарта высшего профессионального образования по направлению... | «концепции современного естествознания. Физические основы» для подготовки... Курс должен способствовать формированию у будущего специалиста научного мышления и расширению его научно-технического кругозора |