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

Министерство образования Российской Федерации Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

РАБОЧАЯ ПРОГРАММА дисциплины “Теория вычислительных процессов” Для подготовки специалистов по направлению 654600 –“Информатика и вычислительная техника” по специальности 220400 -“Программное обеспечение вычислительной техники и автоматизированных систем” и бакалавров по направлению 552800 - «Информатика и вычислительная техника» ”

Санкт-Петербург 2000

Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

“УТВЕРЖДАЮ” Проректор по учебной работе проф. ___________ Ушаков В.Н. “_____”_______________2000 г. РАБОЧАЯ ПРОГРАММА дисциплины “Теория вычислительных процессов” Для подготовки специалистов по направлению 654600 –“Информатика и вычислительная техника” по специальности 220400 -“Программное обеспечение вычислительной техники и автоматизированных систем” и бакалавров по направлению 552800 - «Информатика и вычислительная техника» ” Факультет компьютерных технологий и информатики Кафедра Математического обеспечения и применения ЭВМ Курс – Ш Семестр – 6 Лекции Практические занятия Лабораторные занятия Курсовое проектирование Аудиторные занятия Самостоятельные занятия Всего часов

30 ч. 0 ч. 0 ч. 15 ч.

Экзамен

45 ч. 45 ч. 90 ч.

2000

2

6 семестр

Рабочая программа обсуждена на заседании кафедры Математического обеспечения и применения ЭВМ “ 15 ” ноября 2000 г., протокол № 4. Рабочая программа составлена в соответствии с государственным образовательным стандартом по направлению 654600, специальности 220400 -“Программное обеспечение вычислительной техники и автоматизированных систем”. Рабочая программа согласована с рабочими программами изученных ранее дисциплин: 1)Дискретная математика; 2)Математическая логика; 3)Формальные языки и грамматики;

Рабочая программа одобрена методической комиссией факультета компьютерных технологий и информатики “____”_____________2000г.

3

Цели и задачи дисциплины Основная цель курса заключается в формировании у студентов теоретической базы в области теории асинхронных процессов для дальнейшего изучения специальных дисциплин учебного плана подготовки, связанных с новыми информационными и сетевыми технологиями на основе принципов параллельной и распределённой обработки информации. Требования к уровню освоения дисциплины В результате изучения дисциплины студенты должны: Знать базовые формальные модели логических структур, динамики поведения вычислительных структур и дискретных систем и на их основе усвоить основные положения и результаты ряда взаимосвязанных дисциплин : теории переключательных схем, теории конечных автоматов, теории формальных языков и грамматик, теории параллельных процессов и теоретических основ параллельного программирования, которые далее используются как при изучении специальных дисциплин, так и в инженерной практике; Уметь (владеть или иметь навыки) применять полученные знания в разработках связанных с проектированием как программного обеспечения, так и средств его аппаратной поддержки, читать научные статьи по специальности и пользоваться литературой для самостоятельного решения научно—исследовательских и прикладных задач; Иметь представление (понимать) о современной концепции процесса и методах, методологических подходах и инструментальных средствах, используемых при решении задач анализа, синтеза и организации функционирования вычислительных структур и системного программного обеспечения и вычислительных системах различных классов. Содержание рабочей программы Введение. Краткая характеристика курса в целом, содержание и структура курса. Связь с другими дисциплинами учебного плана. Роль и значение концепции процесса и теории асинхронных процессов в целом для теории и практики разработки и сопровождения различных средств вычислительной техники. Практическое быстродействие и производительность Проблема импорта машинных ресурсов в новых компьютерных и сетевых технологиях. Тема 1. Введение в теорию асинхронных процессов. Параллельная обработка информации и практическое быстродействие средств вычислительной техники. Концепция процесса: основные понятия, определения и соглашения. Элементы теории множеств. Комплекты и кортежи. Отношения и соответствия. Тема 2. Метамодели асинхронных процессов. Система переходов Келлера. Метамодель Варшавского. Информационный базис Карпа –Миллера и неуправляемые вычислительные процессы. Последовательные процессы Хоара. Объектные модели и модельные интерпретации.

4

Тема 3. Сетевая объектная модель: общая характеристика, основные определения и соглашения. Сетевая модельная интерпретация. Синтаксис и семантика объектной модели. Динамика поведения сетевой объектной модели. Основные соглашения выполнения сети. Предметная интерпретация. Особенности применения сетей Петри. Тема 4. Специальная теория сетей: сети Петри. Сети Петри: определение, структура, способы задания. Маркированные сети Петри. Функция маркировки. Начальная и текущая маркировки. Разрешённые переходы, селектор. Срабатывание разрешённых переходов и функция следующего состояния. Выполнение сети. Представление асинхронных процессов в рамках сетевой модели. Двойственность описания асинхронных процессов в терминах сетей Петри. Обобщённая функция следующего состояния. Отношение достижимости на множестве маркировок. Множество достижимых маркировок. Граф достижимости сети Тема 5. Динамические свойства и задачи анализа сетей Петри. Особенности динамики поведения сетей. Структурные ограничения и подклассы сетей Петри. Сигнальные сети и сигнальные графы. Динамические свойства сетей Петри. Устойчивость сетей Петри. Задачи анализа сетей. Достижимость и живость сетей. Задачи подмножества и эквивалентности сетей. Разрешимость задач анализа. Мощность моделирования сетевой модели. Отношение сводимости задач анализа сетей и их эквивалентность. Тема 6. Языки сетей Петри. Формальные языки и иерархия формальных грамматик Хомского. Формальные языки и автоматы. Помеченные сети Петри. Понятие языка сети Петри: Заключительные состояния сети. Классы языков сети Петри. Свойства языков сетей Петри. Языки сетей Петри и классификация формальных языков Хомского. Тема 7. Общая теория сетей: расширенные сетевые модели и сети высокого уровня. Понятие сетей высокого уровня. Мощность моделирования сетей высокого уровня и разрешимость задач их анализа. Проблема существования порождающей простой сети Петри. Общая характеристика сетей высокого уровня: Р/Т-сети, Е-сети, раскрашенные сети, алгебраические сети высокого уровня. Заключение. Теория вычислительных процессов и структур и основные тенденции развития новых информационных и сетевых технологий на базе внедрения в инженерную практику принципов параллельной и распределённой обработки информации. Курсовая работа Цель – формирование практических навыков работы с моделями дискретных структур и формальными методами их представления, в том числе с использованием формализмов многомерной геометрии – n-мерных гиперкубов. В процессе выполнения курсовой работы реализуется процедура минимизации функции алгебры логики с помощью численного алгоритма, базирующегося на использовании единичного гиперкуба в n-мерном пространстве для построения не избыточной оболочки заданной функции, представляющей её минимальную дизъюнктивную форму.

5

Распределение учебных часов по темам и видам занятий Объем учебных часов

№ темы

Название разделов и тем

Лекции

Лабор. Занятия

Практ. занятия

Аудит. занятия

Самост. работа

Всего

Семестр

1 2

Введение Введение в теорию асинхронных процессов. Метамодели асинхронных процессов. Сетевая объектная модель: общая характеристика, основные определения и соглашения. Специальная теория сетей: сети Петри. Динамические свойства и задачи анализа сетей. Языки сетей Петри. Общая теория сетей: расширенные сетевые модели и сети высокого уровня. Заключение Курсовая работа

1 4

-

-

1 4

1 4

2 8

6 6

6

-

-

6

6

12

6

2

-

-

2

2

4

6

8

-

-

8

8

16

6

2

-

-

2

2

4

6

2 4

-

-

2 4

2 4

4 8

6 6

1

-

15 15

1 15 45

1 15 45

2 30 90

6 6 6

3 4

5 6 7 8

9

ИТОГО:

30

6

ЛИТЕРАТУРА Основная № 1 2 3 4 5 6 7

Название, библиографическое описание

К-во экз. в библ. (на каф.)

Автоматное управление асинхронными процессами в ЭВМ и дискретных системах/ Под ред. В.И.Варшавского. -М.: Наука, Гл.ред.ФМЛ, 1986. –400 с. Котов В.Е. Сети Петри. -М.: Наука, Гл.ред.ФМЛ, 1984. –160 с. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера/ 2-е изд. –М.: Энергоатомиздат, 1988. –480 с. Кук Д., Бейз Г. Компьютерная математика/ Пер. с англ. –М.: Наука, Гл.ред.ФМЛ, 1990. –384 с. Минский М. Вычисления и автоматы/ Пер. с англ. –М.: Мир, 1971. –368 с. Питерсон Дж. Теория сетей Петри и моделирование систем/ Пер. с англ. –М.: Мир, 1984. –264 с. Хоар Ч. Взаимодействующие последовательные процессы/ Пер. с англ. –М.: Мир, 1989. –264. Дополнительная

№

Название, библиографическое описание

1

Кнут Д. Искусство программирования для ЭВМ, т.2/ Получисленные алгоритмы/ Пер. с англ. –М.: Мир, 1977. –727 с. Петровский А.Б. Основные понятия мультимножеств. –М.: Едиториал УРСС, 2002. -80 с. Шиханович Ю.А. Введение в современную математику. –М.: Наука, Гл. ред. ФМЛ, 1965. –378 с.

2 3

7

К-во экз. в библ. (на каф.)

Авторы: с к.т.н., доцент

Красюк В.И.

Рецензент д.т.н., профессор

Водяхо А.И.

Зав. кафедрой МО ЭВМ д.т.н., профессор

Лисс А.Р.

Декан факультета КТИ д.т.н., профессор

Герасимов И.В.

Программа согласована: Зав. отделом учебной литературы

Киселёва Т.Г.

Председатель методической комиссии факультета КТИ к.т.н., доцент

Михалков В.А.

Руководитель методического отдела к.т.н., доцент

Марасина Л.А.

8