Теория вычислительных процессов 4 курс, 8 семестр Преподаватель: Веретельникова Евгения Леонидовна 1
Структура курса ТВП 1.Доказательство правильности 1.Математическая индукция 2.Доказательство правильности блок-схем 3.Метод индуктивных утверждений 4.Доказательство правильности программ 5.Формализация доказательств правильности 6.Аксиоматический подход к доказательству 7.Структурная индукция для доказательства правильности рекурсивных программ 2.Сети Петри для моделирования систем 1.Основные понятия сетей Петри (СП). 2.Способы задания СП 3.Выполнение СП 4.Моделирование систем сетями Петри 5.Задачи анализа и способы анализа СП 6.Расширенные и ограниченные СП 2
Математическая индукция Математическая индукция представляет собой некоторый общий способ доказательства в математике. Он положен в основу всех приемов доказательства правильности программ для вычислительных машин. Виды математической индукции Простая индукция Модифицированная простая индукция Нисходящая индукция Восходящая индукция Строгая индукция Модифицированная строгая индукция Обобщенная индукция Структурная индукция 3
Простая индукция Принцип простой индукции Пусть S(N) некоторое высказывание о целом числе N и требуется доказать, что S(N) справедливо для всех положительных чисел N. Согласно простой математической индукции, для этого необходимо 1. Доказать, что справедливо высказывание S(1). 2. Доказать, что если для любого положительного числа N справедливо высказывание S(N), то справедливо и высказывание S(N + 1). 4
Простая индукция ПРИМЕР 1. Мы хотим доказать, что для любого положительного числа n сумма первых n положительных целых чисел равна n (n + 1)/2, т. е N=N (N+1)/2 для любого положительного числа N. Используя простую индукцию, неободимо только доказать, что 1. «Сумма» верна для N=1, т.е. 1 = 1 (1 + 1)/2. Это очевидно. 5
Простая индукция 2. Если сумма первых n положительных целых чисел равна n (n + 1)/2, то сумма первых n+1 положительных целых чисел равна (n +1) [(n + 1)+1]/2, т. е. мы предпола- гаем, что формула N = n (n + 1)/2, справедлива. Это гипотеза индукции. На ее основании мы должны попытаться доказать, что справедлива формула N + (n +1) = (n +1) [(n + 1)+1]/2. 6
Простая индукция Докажем это следующим образом: N + (n +1) = ( N )+ (n +1) = [n (n + 1)/2] + (n +1) =[(n 2 + n)/2] + (n +1) = (По гипотезе индукции) [(n 2 + n)/2] + [(2 n + 2)/2] =(n n + 2)/2 = (n + 1) (n + 2)/2 = (n +1) [(n + 1)+1]/2. ЧТД. Поскольку мы доказали справедливость двух утверждений, то по индукции формула n = n (n + 1)/2 считается справедливой для любого положительного числа n 7
Принцип модифицированной простой индукции Иногда необходимо доказать, что высказывание S(N) справедливо для всех целых N N 0. Для этого можно довольно легко модифицировать принцип простой индукции. Чтобы доказать, что высказывание S(N) справедливо для всех целых N, необходимо: 1. Доказать, что справедливо S(N 0 ) 2. Доказать, что если S(N) справедливо для всех целых n N 0, то справедливо и S(N+ 1). 8
Принцип модифицированной простой индукции В частности, если требуется доказать справедливость некоторого высказывания S(N) для любых неотрицательных целых n (т. е. для N 0), то необходимо: 1. Доказать, что справедливо S(0). 2. Доказать, что для всех неотрицательных целых n справедливо S(N+1), если справедливо S(N). 9
Принцип модифицированной простой индукции ПРИМЕР 2. Для любого неотрицательного числа п доказать, что … + 2 N = 2 N+1 – 1. Используя простую индукцию, мы должны 1. Доказать, что 2 0 = – 1 Это очевидно, так как 2 0 = 1 = – 1 = 2 1 – 1= 2 – 1 = Доказать, что если для всех неотрицательных целых n справедлива формула … + 2 N = 2 N+1 – 1, то справедлива и формула … + 2 N + 2 N+1 = 2 (N+1)+1 – 1. 10
Принцип модифицированной простой индукции Высказывание N = 2 N+1 – 1 называется гипотезой индукции. Второе положение доказывается следующим образом: … + 2 N +2 N+1 = ( …+2 N )+2 N+1 = ( 2 N+1 – 1) + 2 N+1 = ( 2 N N+1 ) – 1 = (По гипотезе индукции) (2 2 N+1 ) – 1 = 2 N+2 – 1 = 2 (N+1)+1 – 1. 11
Принцип модифицированной простой индукции Иногда нужно доказать справедливость высказывания S(N) для целых n, удовлетворяющих условию n 0 n M 0. Так как между n 0 и M 0 находится конечное число целых чисел, то справедливость S(N) можно доказать простым перебором всех возможных вариантов. Однако легче, а иногда и необходимо (если, например, мы не знаем конкретных значений n 0 и M 0 ) доказать S(N) по индукции. В этом случае можно воспользоваться одним из двух вариантов индукции: 12
Принцип модифицированной простой индукции Простая нисходящая индукция 1. Доказать, что справедливо S (n 0 ) 2. Доказать, что если справедливо S (n), то для любых целых n 0 n M 0 –1 справедливо и S(N + 1). Простая восходящая индукция 1. Доказать, что справедливо S(M 0 ). 2. Доказать, что если справедливо S(N), то для любых целых n 0 +1 n M 0 справедливо и S(N – 1). Интуитивно понятно, что этого достаточно для доказательства справедливости S(N) при любых N, удовлетворяющих условию n 0 n M 0. 13
Доказательство высказываний, относящихся к программам дня вычислительных машин При доказательстве правильности программы иногда необходимо доказать справедливость некоторого высказывания S в те моменты, когда выполнение программы достигает некоторой определенной точки. Можно попытаться доказать это методом индукции по n – числу «проходов» через данную точку программы. Мы можем и не знать точно, сколько раз проходим через эту точку: это зависит от данных, используемых при выполнении программы. Мы можем проходить через нее и конечное (M 0 ), и бесконечное число раз (если программа не заканчивается из-за ошибки). 14
Доказательство высказываний, относящихся к программам дня вычислительных машин Таким образом, можно попытаться доказать справедливость S(N) для N, удовлетворяющих условию 1 n M 0 или условию 1 n. В любом случае мы можем получить результат, не зная, с каким вариантом мы имеем дело. Мы убеждаемся в справедливости S(N) при каждом проходе через определенную точку, если можем: 1. Доказать, что справедливо S(1), т. е. справедливо высказывание S при первом проходе через точку. 2. Доказать, что если справедливо S(N) (т. е. при N-ом проходе через точку), то справедливо и S(N+1), если мы, конечно, попадем в точку в п+1-й раз. 15
Доказательство высказываний, относящихся к программам дня вычислительных машин Если мы проходим через точку только т 0 раз, то значе- ния N, для которых второе положение, возможно, справе- дливо, это те значения N, при которых мы n 0 n M 0 –1. Если же мы проходим через точку бесконечное число раз, то значения N, для которых может быть справедливо второе положение, это значения, удовлетворяющие условию 1 n. Таким образом, если мы докажем оба положения, то тем самым с помощью простой восходящей или простой индукции мы докажем справедливость высказывания S(N) для всех требуемых значений п вне зависимости от того, какой вариант встречается в действительности. 16
Строгая математическая индукции При доказательствах некоторых высказываний о целых числах иногда требуется более строгая версия принципа индукции. ПРИНЦИП СТРОГОЙ ИНДУКЦИИ Пусть S(n) – некоторое высказывание о целом числе n и требуется доказать, что S(n) справедливо для всех положительных n. Для этого необходимо: 1) доказать, что справедливо S(1); 2) доказать, что если справедливы S(1), S(2), S(3),..., S(n) для всех положительных n, то справедливо и S(n + 1). 17
Строгая математическая индукции Пример 2. Простым числом называется положительное число, делящееся без остатка только на 1 и на само себя. Мы хотим доказать, что каждое положительное число n можно представить в виде произведения одного и более простых чисел. Докажем это с помощью строгой индукции по n: 1) если n = 1, то это число является простым, и его можно представить как «произведение» одного простого числа; 2) предположим, что каждое из чисел 1, 2,..., n может быть записано в виде произведения простых чисел. Необходимо показать, что число n + 1 также можно представить в виде произведения простых чисел. Если n + 1 является простым числом, то очевидно, что его можно записать в виде произведения одного простого числа на 1. Если n + 1 – не простое число, тогда существует некоторое положительное число a, такое, что 1 < a < n + 1, и оно делит n + 1 без остатка. Другими словами,, или n + 1 = a b. Каждое из чисел a и b меньше n. Следовательно, по гипотезе индукции и a, и b можно представить в виде произведения простых чисел. Отсюда очевидно, что и n + 1 можно записать как произведение этих же простых чисел, так как n + 1 = a b. Следует отметить, что в этом примере, по существу, требуется строгая индукция. О числах a и b известно лишь только то, что они меньше n. Поэтому, для того чтобы использовать индукцию, необходимо знать, что каждое из положительных чисел 1, 2,..., n может быть представлено в виде произведения простых чисел. Одного предположения о том, что n можно записать в виде произведения простых чисел, оказывается недостаточно. 18
Строгая математическая индукции Другими словами,, или n + 1 = a b. Каждое из чисел a и b меньше n. Следовательно, по гипотезе индукции и a, и b можно представить в виде произведения простых чисел. Отсюда очевидно, что и n + 1 можно записать как произведение этих же простых чисел, так как n + 1 = a b. Следует отметить, что в этом примере, по существу, требуется строгая индукция. О числах a и b известно лишь только то, что они меньше n. Поэтому, для того чтобы использовать индукцию, необходимо знать, что каждое из положительных чисел 1, 2,..., n может быть представлено в виде произведения простых чисел. Одного предположения о том, что n можно записать в виде произведения простых чисел, оказывается недостаточно. 19
Строгая математическая индукции Пример 3. Рассмотрим последовательность чисел, называемых числами Фибоначчи. В нее входят f 0 =0, f 1 =1, f 2 = 1, f 3 = 2, f 4 = 3, f 5 = 5, f 6 = 8,..., где (n + 1)-е число Фибоначчи определяется как f n + 1 = f n + f n – 1 (для n 1). Пусть = (1 +5 )/2 и требуется доказать, что f n n – 1 для любого неотрицательного числа n. Для доказательства используем метод строгой индукции по n. Так как доказывается высказывание о неотрицательных числах, а принцип индукции сформулирован для положительных, используем очевидную модификацию метода: 1.Для n = 0 необходимо показать, что f 0 0 – 1. Это справедливо, так как f 0 = 0 = –1. Необходимо рассмотреть особый случай, когда n=1. Здесь мы имеем f 1 =1 1= 0 = 1–1. 20
Строгая математическая индукции 2. Предположим, что f m m – 1 справедливо для всех неотрицательных целых чисел m = 0, 1, 2,..., n. Нужно показать, что f n+1 (n + 1) – 1 также справедливо. По гипотезе индукции f n n – 1 и f n–1 (n – 1) – 1. Поэтому f n + 1 = f n + f n – 1 n – 1 + n – 2 = n – 2 ( +1). Обратите внимание, что 2 = + 1. Фактически мы так и выбирали, чтобы выполнялось условие + 1 = 2. Поэтому мы получаем f n + 1 = f n + f n – 1 n – 2 ( +1) = n – 2 2 = n = (n + 1) – 1.ЧТД Замечание 1: необходимо было знать, что и f n, и f n–1 удовлетворяют гипотезе индукции, т.е. необходима СТРОГАЯ индук. Замечание 2: в данном частном случае нам потребовалось доказывать, что f 0 0 и f 1 1 ; мы не можем записать f 1 как f 0 + f –1, так как f –1 не существует. 21
Обобщенная индукции Метод математической индукции можно обобщить и приме- нять не только для доказательства высказываний о множестве положительных целых чисел, но и о более общих множествах некоторых объектов. Для этого сначала дадим определение, связанное с обобщением структуры целых чисел. Определение. Говорят, что бинарное отношение < вполне упорядочивает множество X, или множество вполне упорядо- чено, если отношение < обладает следующими свойствами: 1) если x, y, z принадлежат X, а х < у и у < z, то х < z; 2) для х и у из X справедлива одна и только одна из трех возможностей: либо х < у, либо у < х, либо х = у; 3) если А – любое непустое подмножество X, то в А существует некоторый элемент х, такой, что х у для любого у, принадлежащего А.. Другими словами, любое непустое подмножество X содержит «наименьший элемент». 22
Обобщенная индукции Отметим, что это определение касается обобщения структуры положительных (неотрицательных) целых чисел. Множество положительных целых чисел вполне упорядочено относительно обычного отношения
Обобщенная индукции ПРИНЦИП ОБОБЩЕННОЙ ИНДУКЦИИ Пусть X – вполне упорядоченное относительно < множество, а S(х) – некоторое высказывание, касающееся элемента х из X. Если требуется доказать справедливость S(х) для всех х, принадлежащих X, то необходимо: 1) доказать, что справедливо S(х 0 ), где х 0 – наименьший элемент в X; 2) доказать для всех х в X, удовлетворяющих условию х 0 < х, что если справедливо S (у) для всех у < х, то справедливо и S(х). Отметим, что если X – множество положительных целых чисел, а отношение < имеет обычный смысл, то принцип обобщенной индукции идентичен принципу строгой индукции 24