Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Оборудована электрокаменкой, купелью с гейзером, встречным потоком и гидромассажем, 2 душевых и санузел, просторная и уютная комната отдыха с чайными ...полностью>>
'Конкурс'
1.1. Открытый межклубный конкурс социальной рекламы «Взгляд молодых» (далее-конкурс) проводится в соответствии с планом мероприятий МБУ «ЦДДМ «Совреме...полностью>>
'Документ'
Глубокоуважаемые коллеги! Для нас большая честь пригласить Вас принять участие в работе Международной научно-практической конференции «Физическая куль...полностью>>
'Документ'
Каждый человек в нашей стране имеет обязанности и права. Если первые с раннего возраста разъясняют детям в семье, детских садах и школах, то со вторым...полностью>>

Главная > Рабочая программа

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

РАБОЧАЯ ПРОГРАММА

дисциплины

“Теория вычислительных процессов и структур”

подготовка бакалавров по направлению 552800 “Информатика и вычислительная техника”

специальность 220400 - “Программное обеспечение вычислительной техники и автоматизированных систем”

Факультет Автоматики и вычислительной техники

Кафедра Автоматики

Курс 4

Семестр 7, 8

Лекции 34 часа

Практические занятия 17 часов

Лабораторные занятия 17 часов

Индивидуальная работа 34 часа

Аудиторных 102 часа

Самостоятельная работа 66 часов

Итого 168 часов

РГР 7, 8 семестр

Курсовая работа –

Контрольные работы –

Экзамен 7 семестр,

Зачет 8 семестр

Гос. экзамен Г1 – 9 семестр

Новосибирск

2001

Рабочая программа составлена с учетом требований, изложенных в государственном образовательном стандарте высшего профессионального образования.

Объем учебной работы и контроль изучения дисциплины:

Факультет Автоматики и вычислительной техники

Кафедра Автоматики

Курс 4 Семестр 7, 8

Лекции 34 часа Практические занятия 17 часов

Лабораторные занятия 17 часов Индивидуальная работа 34 часа

Аудиторных 102 часа Самостоятельная работа 66 часов

Итого 168 часов

РГР 7, 8 семестр

Экзамен 7 семестр, Зачет 8 семестр

Гос. экзамен Г1 – 9 семестр

Требования к курсу

Содержание курса соответствует требованиям к обязательному минимуму содержания основной образовательной подготовки бакалавров направления 550200 «Автоматизация и управление» и инженеров специальности 220400 «Программное обеспечение вычислительной техники и автоматизированных систем» и предполагает изучение следующего:

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

I. Цель и задачи изучения дисциплины,
ее место в учебном процессе

1. Цель изучения дисциплины

Данная дисциплина имеет целью:

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

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

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

2. Место дисциплины в учебном процессе

Данная дисциплина входит в цикл общематематических и естественнонаучных специальных дисциплин в соответствии с общеобразовательной программой базового высшего образования по направлению “Информатика и вычислительная техника”. Дисциплина базируется на знании таких дисциплин (на материале, изучаемом в курсах), как “Основы программирования”, “Математическая логика”, “Теория множеств”, “Основы вычислительной техники”, “Информатика и программирование”, “Системное программное обеспечение”, “Численные методы”.

3. Предметы изучения

3.1. Базовые определения и понятия вычислительных процессов и структурного программирования.

3.2. Структура и составные компоненты теории вычислительных процессов.

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

4. Объекты изучения

4.1. Базовые определения и понятия.

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

4.3. Способы организации вычислительных процессов в вычислительных системах.

4.4. Принципы построения и алгоритмы поведения сетей Петри.

5. Результаты изучения

5.1. Представления.

В результате изучения дисциплины у студентов должны быть сформированы представления о:

  • методе математической индукции как способе, положенном в основу доказательства правильности программ;

  • видах вычислительных процессов и их взаимодействии;

  • принципах и методах структурного программирования;

  • сетях Петри как математическом объекте.

5.2. Знания.

После изучения дисциплины студент должен приобрести знания в следующих областях:

  • доказательство правильности программ;

  • теория и практика структурного программирования;

  • вычислительные процессы в вычислительных системах;

  • сведения о сетях Петри, способах их реализации и областях применения.

5.3. Умения и навыки.

После изучения дисциплины студент должен:

  • приобрести навыки в использовании метода индуктивных утверждений для доказательства правильности итеративных программ;

  • уметь использовать принципы и методы структурного программирования для проектирования и верификации программ;

  • ориентироваться в проблемах планирования и диспетчеризации вычислительных процессов;

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

II. Содержание дисциплины

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

1. Математическая индукция как способ доказательства правильности программ

Тема 1. Математическая индукция. Введение: основные направления исследований, связанные с доказательством правильности программ (методы доказательства, конструирование программ и языков, механизация процесса доказательства правильности). Простая индукция: принцип простой индукции, принцип модифицированной простой индукции, доказательство высказываний, относящихся к программам для вычислительных машин. Строгая версия математической индукции: принцип строгой индукции. Обобщенная индукция: принцип обобщенной индукции. – 2 часа.

Тема 2. Доказательство правильности блок-схем программ. Основные принципы доказательства правильности для блок-схем. Дополнительные примеры доказательства правильности блок-схем программ. Метод индуктивных утверждений (основные определения и теоремы, описание метода). Сокращенные доказательства правильности. Формализация доказательства с помощью индуктивных утверждений. – 4 часа.

Тема 3. Доказательство правильности программ, написанных на обычных языках программирования. Примеры доказательства правильности программ. написанных на Фортране. Примеры доказательства правильности программ, написанных на ПЛ/1. Аксиоматический подход к доказательству частичной правильности. Доказательство частичной правильности как часть процесса программирования. – 4 часа.

Тема 4. Доказательство правильности рекурсивных программ. Упрощенный язык программирования для иллюстрации понятия рекурсии. Структурная индукция. Более трудные примеры доказательства правильности программ методом структурной индукции. Структурная индукция для нерекурсивных программ. – 4 часа.

Тема 5. Управляющие структуры и структуры данных. Внешний синтаксис для управляющих структур: последовательные структуры, структуры с ветвлением, циклические структуры. Внешний синтаксис структур данных: структуры поименованных данных (скаляр, массив, запись), структуры непоименованных данных (список, стек, множество, очередь, дерево, граф). Внутренний синтаксис: выражения внутреннего синтаксиса, типы данных. – 2 часа.

2. Организация вычислительных процессов.
Процессы и потоки

Тема 6. Мультипрограммирование. Мультипрограммирование (или многозадачность). Мультипрограммирование в системах пакетной обработки. Мультипрограммирование в системах разделения времени. Мультипрограммирование в системах реального времени. Мультиобработка. – 2 часа.

Тема 7. Планирование процессов и потоков. Понятие “процесс” и “поток”. Создание процессов и потоков. Планирование и диспетчеризация потоков. Состояние потока. Вытесняющие и невытесняющие алгоритмы планирования. Алгоритмы планирования, основанные на квантовании. Алгоритмы планирования, основанные на приоритетах. Смешанные алгоритмы планирования. Планирование в системах реального времени. Моменты перепланирования. – 2 часа.

Тема 8. Мультипрограммирование на основе прерываний. Назначение и типы прерываний. Механизм прерываний. Программные прерывания. Диспетчеризация и приоритизация прерываний в ОС. Функции централизованного диспетчера прерываний на примере Windows NT. Процедуры обработки прерываний и текущий процесс. Системные вызовы. – 2 часа.

Тема 9. Синхронизация процессов и потоков. Цели и средства синхронизации. Необходимость синхронизации и гонки. Критическая секция. Блокирующие переменные. Семафоры. Тупики. Синхронизирующие объекты ОС. Сигналы. – 2 часа.

Тема 10. Обмен данными между процессами и потоками. Конвейеры, именованные конвейеры, очереди сообщений. Способ взаимодействия между процессами в распределенных системах (в отличие от централизованных). Синхронизация. Буферизация в примитивах передачи сообщений. Надежные и ненадежные примитивы. Способы адресации, интерфейсы и протоколы связывания клиента с сервером. – 2 часа.

3. Сети Петри

Тема 11. Сети Петри как инструмент моделирования систем. Моделирование. Природа систем. Принципы построения сетей Петри. Структура сетей Петри. Графы сетей Петри. Маркировка сетей Петри Пространство состояний сетей Петри Алгоритмы поведения сетей Петри. – 4 часа.

Тема 12. Способы реализации сетей Петри. Альтернативные формы определения сетей Петри. сети Петри: события и условия, одновременность и конфликт. Моделирование сетями Петри аппаратного и программного обеспечения ЭВМ. Задачи и методы анализа сетей Петри. Области применения сетей Петри. . – 4 часа.

II. Темы практических занятий – 17 часов

1. Математическая индукция. – 2 часа.

2. Доказательство правильности блок-схем программ. – 4 часа.

3. Доказательство правильности программ, написанных на обычных языках программирования. – 2 часа.

4. Рекурсивные программы. Работа со списками. – 2 часа.

5. Доказательство правильности рекурсивных программ. – 2 часа.

6. Управляющие структуры. Доказательство правильности структурированных программ. – 2 часа.

7. Структуры поименованных и непоименованных данных. – 2 часа.

III. Темы Лабораторных занятий – 17 часов

1. Написание и верификация программ методом математической индукции. – 4 часа.

2. Проектирование, тестирование и верификация программ с использованием методики структурного программирования. – 4 часа.

3. Разработка инвариантов для циклических элементарных программ. Анализ и структурирование схемы программы. – 4 часа.

4. Проектирование сети Петри и исследование алгоритмов ее поведения.
– 4 часа.

5. Заключительное занятие. – 1 час.

IV. Расчетно-графическая работа (7 семестр)

Цель работы: закрепление теоретических знаний и формирование практических навыков по верификации программного обеспечения.

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

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

V. Расчетно-графическая работа (8 семестр)

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

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

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

VI. список литературы

1. Р. Андерсен Доказательство правильности программ. М.: Мир, 1982.

2. Информатика. Теория и практика структурного программирования: Методическая разработка. – Новосибирск, изд-во НГТУ, 1999.

3. Лингер Р., Миллс Х., Уитт Б. Теория и практика структурного программирования. /Пер. с англ., М.: Мир, 1982.

4. Олифер В. Г., Олифер Н.А. Сетевые операционные системы. – СПб.: Питер, 2001.

5. Олифер В. Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. – СПб.: Питер, 1999.

6. Дж. Питерсон Теория сетей Петри и моделирование систем. – М.: Мир, 1984.

7. Котов В.Е. Сети Петри. – М.: Наука, 1984.

8. Майника Э. Алгоритмы оптимизации на сетях и графах. / Под. ред. Е.К. Масловского. – М.: Мир, 1981. – 322 с.

Приложение.

Список вопросов к экзамену (7 семестр).

  1. Основные направления исследований, связанные с доказательством правильности программ.

  2. принцип простой индукции

  3. принцип модифицированной простой индукции

  4. Строгая версия математической индукции: принцип строгой индукции.

  5. Обобщенная индукция: принцип обобщенной индукции

  6. Основные принципы доказательства правильности для блок-схем.

  7. Метод индуктивных утверждений

  8. Сокращенные доказательства правильности.

  9. Формализация доказательства с помощью индуктивных утверждений.

  10. Доказательство правильности программ, написанных на языках программирования.

  11. Аксиоматический подход к доказательству частичной правильности.

  12. Доказательство частичной правильности как часть процесса программирования

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

  14. Упрощенный язык программирования для иллюстрации понятия рекурсии.

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

  16. Структурная индукция для нерекурсивных программ.

  17. Внешний синтаксис для управляющих структур.

  18. Внешний синтаксис структур данных: структуры поименованных данных

  19. структуры непоименованных данных.

  20. Рекурсивные программы: списки. Проверки и функции работы со списками.

  21. Списки. Виды списков. Операции со списками.

  22. Линейные списки. Виды линейных списков. Операции с ними.

  23. Нелинейные списки. Виды нелинейных списков. Операции с ними.

  24. Внутренний синтаксис: выражения внутреннего синтаксиса, типы данных.

  25. Верификация структурированных программ.

  26. Правильность элементарных программ:

  27. Методы доказательства правильности программ:

  28. Инварианты цикла при доказательстве правильности программ

Список вопросов к зачету (8 семестр).

  1. Мультипрограммирование (или многозадачность).

  2. Мультипрограммирование в системах пакетной обработки

  3. Мультипрограммирование в системах разделения времени, в системах реального времени.

  4. Создание процессов и потоков.

  5. Планирование и диспетчеризация потоков. Вытесняющие и невытесняющие алгоритмы планирования.

  6. Алгоритмы планирования, основанные на квантовании.

  7. Алгоритмы планирования, основанные на приоритетах.

  8. Смешанные алгоритмы планирования.

  9. Планирование в системах реального времени. Моменты перепланирования.

  10. Назначение и типы прерываний. Механизм прерываний.

  11. Программные прерывания. Диспетчеризация и приоретизация прерываний в ОС.

  12. Функции централизованного диспетчера прерываний на примере Windows NT.

  13. Процедуры обработки прерываний и текущий процесс. Системные вызовы.

  14. Синхронизация процессов и потоков. Цели и средства синхронизации.

  15. Критическая секция. Блокирующие переменные.

  16. Семафоры. Тупики.

  17. Синхронизирующие объекты ОС. Сигналы

  18. Обмен данными между процессами и потоками.

  19. Конвейеры, именованные конвейеры, очереди сообщений.

  20. Способ взаимодействия между процессами в распределенных системах (в отличие от централизованных).

  21. Синхронизация. Буферизация в примитивах передачи сообщений.

  22. Надежные и ненадежные примитивы.

  23. Способы адресации, интерфейсы и протоколы связывания клиента с сервером.

  24. Принципы построения сетей Петри.

  25. Структура сетей Петри.

  26. Графы сетей Петри.

  27. Маркировка сетей Петри

  28. Алгоритмы поведения сетей Петри

  29. Способы реализации сетей Петри.

  30. Области применения сетей Петри.

  31. Сети Петри как инструмент моделирования систем. Природа систем.

  32. Пространство состояний сетей Петри

  33. Альтернативные формы определения сетей Петри.

  34. сети Петри: события и условия.

  35. сети Петри: одновременность и конфликт.

  36. Моделирование сетями Петри программного обеспечения ЭВМ.

  37. Задачи и методы анализа сетей Петри.



Похожие документы:

  1. Рабочая программа дисциплины “структуры и алгоритмы обработки данных” Для подготовки дипломированных специалистов по направлениям

    Рабочая программа
    ... ТЕХНИКАпо специальности 220400 – “ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ” Для подготовки бакалавров по направленям: 510200 – “ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА552800 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА ...

Другие похожие документы..