Лекция 1 по теории вычислительных процессов. Лекция 1 Вычислительные процессы Направления исследований теоретического программирования
 Скачать 0.57 Mb.
|
Теория вычислительных процессовЛекция 1 Вычислительные процессы Направления исследований теоретического программированияМатематические основы программирования. Теория схем программ. Семантическая теория программ. Теоретические модели вычислительных процессов. Прикладные задачи теоретического программирования. Вычислительный процессВП - последовательность сменяющих друг друга состояний некоторой информационной среды. Модель ВП – описание последовательной смены состояний определенной среды. теоретическая компьютерная программа математическая схема (алгоритм) Виды и методы организации вычислительных процессов
Методы организации управления ВП: последовательное управление (ПУ) последовательно-параллельное управление (ППУ) асинхронное управление (АУ) Виды ВП: Опорные сведенияТеория отношений и функций Теория графов Математика и математический анализ Алгоритмизация Отношения и функцииПодмножество n-ой степени множества называется n-местным отношением на этом множестве. СВОЙСТВА ОТНОШЕНИЙ рефлексивность антирефлексивность симметричность антисимметричность транзитивность полнота (линейность) ПОРЯДОК антисимметричность транзитивность ЭКВИВАЛЕНТНОСТЬ рефлексивность симметричность транзитивность Функциональное соответствие, при котором каждому прообразу соответствует единственный образ, называется функцией. f: AB или f(A)=B. ГрафыСовокупность двух множеств: множества точек (вершин) V и множества линий (ребер)Е VxV. Е={(vi,vj)| vi,vj V}. ХАРАКТЕРИСТИКИ ГРАФА Ориентированность Связность Полнота Однодольность(двудольность) Цикличность Степени вершин Пропускная способность Вычислимость и разрешимостьТезис Тьюринга: функция F является (частично) вычислимой, если существует машина Тьюринга Т такая, что FT = F. Пусть V – алфавит, М V – множество слов в V. FM - Характеристическая функция FM(а) = 1, если а М, и FM(а) = 0, в остальных случаях. Множество М называется разрешимым, если его характеристическая функция вычислима. Теорема (Тьюринг). Проблема остановки машины Тьюринга неразрешима. Схемы программначало конец ввод действие вывод начало конец Ввод А В=А*2 Вывод В начало конец Ввод А В=copy(А,2,1) Вывод В начало конец задача решение ответ Модели вычислительного процессаПрограмма, написанная на языке программирования Сигнальный граф Асинхронный процесс Сетевой график Блок-схема (потоковая диаграмма) Сеть Петри Конечный автомат Асинхронный процессАП= S={“события, организующие процесс”} FSxS I ={“инициаторы”}; I S R={“результанты”}; R S Описание множеств списками АП= S={s1, s2, s3, s4, s5, s6}; F={(s1,s3); (s1,s4); (s2,s1); (s3,s5); (s5,s1); (s4,s6)} ИЛИ Таблица функции следования
Матрица смежности орграфа
Диаграмма орграфа s1 s2 s3 s4 s7 s8 s6 s5 Правила назначения инициаторов и результантовНазначение инициаторов: 1) (iI) [sS: iFs]. 2) (iI) [(sS\I): sFi]. Назначение результантов: 1) (rR) [sS: sFr]. 2) (rR) [(sS\R): rFs]. Эффективный процесс Определение: АП называется эффективным, если 1. из его инициаторов все траектории ведут в результанты 2. каждая из траекторий, приводящих к результанту, начинается в некотором инициаторе 3. процесс не содержит ориентированных циклов вне множества R результантов. Эффективность АП оставляет место недетерминизма, т.е. возможно, что из одного инициатора процесс попадает в разные результанты. Пример эффективного асинхронного процессаЕсли I={s1, s5}, R={s4}, то не выполняется свойство 1; если I={s7}, R={s1,s2, s3, s4, s5, s6}, то не выполняется свойство 2; если I={s7, s8}, R={s4}, то не выполняется свойство 3; если I={s7, s8}, R={s1, s2, s3, s4, s5, s6}, то асинхронный процесс эффективный. s1 s2 s3 s4 s7 s8 s6 s5 Управляемый процесс Определение: Если в эффективном АП каждая допустимая последовательность классов ведёт из начального класса в один и только один заключительный класс, то такой процесс называется управляемым. В управляемом процессе вводится ограничение на степень недетерминизма: для каждого инициатора, все траектории, из него исходящие ведут в один заключительный класс. Простой процесс Определение: Эффективный АП называется простым, если он удовлетворяет условиям:
rR s F r sR Репозиция процессаРепозицией АП Р={S, F, I, R} называется эффективный асинхронный процесс P`={S`,F`,I`,R`}, где S`=I U R U Sд, I`R, R`I. Если I`=R, R`=I, то репозиция называется полной, иначе частичной. s1 s2 s3 s4 s7 s8 s6 s5 s6 s7 s1 s2 s4 s8 |