Доказательная алгоритмика. Глава1

Доказательная алгоритмика

(здесь будет предисловие)

Глава1

Итак, пусть перед нами поставлена задача1: найти минимальное число (следующая задача, кстати, будет упорядочить числа. И это уже другая задача, по выходу. Хотя по входу одинаковая) из 2-х чисел (банальная задача).
Решение элементарное (ввод и вывод (для программы) опущен):
1)сравниваем 2 числа: если ч1<ч2, то выводим ‘ч1’,
Иначе – выводим ‘ч2’.
Но ведь может быть ни то и ни другое (а на самом деле есть и то и другое: если нет ни минимального, ни максимального (числа), то оба числа – и то и это. Нет, неверно, не морочьте мозги: если равны, то результат сравнения – пуст.)
Отсюда доработка: если ни то, ни иначе … эээ, нет.
Если иначе, то это может быть как ч1>ч2 (и это действительно иначе) или как ч1=ч2 (и это –(действительно) просмотренное, ибо ни то и не другое. (А26-))

If a1<a2 then write(‘a1’)
Else write(‘a2’)

Рис1. Алгоритм для задачи1 (без учёта замечаний)

Теперь задача2: найти (=вывести) минимальное число из 3-х чисел.
Вот тут уже заминка. Допустим, 1-ое с 2-ым сравнил (и, допустим, 1-ое получилось меньше), что дальше делать? Понятное дело: 1-ое нужно сравнивать с 3-ьим. И, если 3-ье – меньше 1-го, то вывести 3-ье число, иначе – 1-ое.
А 2-ое когда будет меньше? Этот результат – противоположен  результату 1-го шага.(то есть 2-ое получилось меньше) Но после этого – еще нельзя делать вывод о том, что 2-ое число – минимальное, не так ли? Ибо его еще надо сравнивать с 3-ьим (и результаты (очевидно) могут быть разными): если 3-ье – меньше 2-го, то выводим 3-ье, иначе – 2-ое.
В итоге – получается вот такой сложный алгоритм

(Алгоритм написан на псевдокоде.
Псевдокод – это язык программирования, совмещающий в себе базовые возможности всех языков программирования и к тому же с максимально упрощенным синтаксисом.
Псевдокод необходим потому, что мы различаем понятия «программа» и «алгоритм». А именно, алгоритм – это то общее, что существует для всего множества в точности идентичных по функционалу программ, написанных на разных языках програмирования.
(Следовательно, алгоритм – это первооснова любой программы. А поэтому: утром - алгоритм, а вечером - программа.)
Таким образом, алгоритм должен писаться на некотором (как бы не реальном) обобщенном и лишенном всех надстроек конкретных языков программирования языке.):

If a1<a2 then
If a1<a3 then write(‘a1’)
Else then write(‘a3’)
Else
If a2<a3 then write(‘a2’)
Else write(‘a3’)

Рис2. Алгоритм для задачи2

Вроде бы должно работать! Но проверим (протестируем) всё-таки этот алгоритм на компьютере. Введем такие числа: a1=3, a2=5, a3=2. Работает! И верно! Т.к. выведено ‘a3’
Попробуем теперь числа: a1=3, a2=5, a3=3. Выведено ‘a3’ А как же ‘a1’? Т.к. a1=a3, то и a1 является минимальным числом. А алгоритм это не сообщил. В чём же дело? Легко догадаться: этот алгоритм не предусмотрен для (корректной) обработки таких случаев, когда есть хотя бы одна пара равных чисел.
(а всё почему? Потому что автор алгоритма не удосужился (корректно) обработать все возможные ситуации (то есть составляющие, как говорят математики, полную систему событий) в условных управляющих структурах. Возьмите это на заметку, будущие программисты.)
Это означает, что в таких случаях алгоритм выдает неверный (с точки зрения предъявленных к нему требований о его функции) результат.

Почему же появился такой алгоритм? А потому, что программист неявно упростил себе задачу: он решил (почему-то), что все сравниваемые числа – разные. (хотя в условии задачи такого не сказано.) Вот и получил алгоритм, верно работающий только в частном случае. И такие ситуации – самый частый источник ошибок в алгоритмах. Ибо так работает подсознание человека, неявно экономит усилия по решению задачи. А убеждение в том, что такой ход событий неизбежен, консервирует нынешнюю ситуацию. А именно, ситуацию, состоящую в том, что алгоритмы создаются приблизительно правильные, отчего их потом надо тестировать. И, если ошибка найдена, исправлять её. Но путь от обнаружения некорректной работы алгоритма до обнаружения соответствующей этим некорректностям ошибки (или ошибках) в алгоритме (которую реально можно исправить) – часто бывает довольно долгим.

Чего не скажешь о нашем случае. Причину некорретности работы алгоритма мы нашли (кстати, в алгоритме для задачи1 – та же ошибка) и поэтому можем исправить его. А именно, так:

If a1<a2 then
If a1<a3 then write(‘a1’)
ElseIf a1 >a3 then write(‘a3’)
else write(‘a1 and a3’)
Else If a1>a2 then 
If a2<a3 then write(‘a2’)
ElseIf a2>a3 write(‘a3’)
else write(‘a2 and a3’)
else
If a1<a3 then write(‘a1 and a2’)
elseIf a1>a3 then write(‘a3’)
else write(‘a1 and a2 and a3’)

Рис3. Доработанный алгоритм для задачи2

Доработаем теперь и алгоритм для задачи1 (это нам пригодится для дальнейшего)

If a1<a2 then write(‘a1’)
ElseIf a1>a2 then write(‘a2’)
Else write(‘a1 and a2’)

Рис4. Доработанный алгоритм для задачи1

А теперь зададимся вопросом: можем ли мы сейчас гарантировать, что эти алгоритмы – (полностью) свободны от ошибок и поэтому в точности соответствуют предъявляемым к ним требованиям в части функциональности? Если кто-то считает, что да, то пусть ответит, каковы основания такого утверждения? То, что лично я уверен в правильности алгоритма? Но ведь, не так ли, такая ситуация «личной уверенности» уже была и она была развенчана. Так откуда же уверенность, что это не произойдёт во 2-ой раз?

Итак, даже если ошибка в алгоритме обнаружена и исправлена, ни один программист (в глубине души) не даст гарантии, что больше в алгоритме ошибок нет. Как вариант, программист будет клясться-божиться, что алгоритм идеален … пока какой-нибудь тестировщик не обнаружит новую ошибку. (Причём, как правило, обнаружит случайно. Поскольку исчерпывающей теории тестирования алгоритмов на сегодня не существует. То есть такой, которая для любого алгоритма позволила бы создать исчерпывающую систему текстов.)
А всё потому, что алгоритмы на сегодняшний день разрабатываются гипотетически-экспериментально. Это означает, что любой алгоритм на сегодняшний день – фактически представляет из себя гипотезу.(не 100%-ную, конечно, но в некоторой части. И процент этой части – это и есть процент ошибок в алгоритме) Которая потом проверяется экспериментально, проверяется и проверяется. Но нельзя ли кардинально поменять ситуацию? То есть разрабатывать алгоритмы теоретически-доказательно? Что означает, что из-под нашего пера сразу будет выходить алгоритм без ошибок.

Это, конечно, звучит фантастически! (Но только не для меня, который в своё время читал книги по теме Доказательство программ. Которые теперь, правда, усилиями большинства российских программистов, помещены в мусорную корзину истории.)

Но попробуем это сделать на примере самого простого (банального) алгоритма (для задачи1) Как доказать полученный для неё алгоритм? Давайте посмотрим для этого на функцию этого алгоритма.
(к слову сказать, у алгоритма может быть много функций, причём самого верхнего уровня. (именно таковы алгоритмы большинства современных программ. И для выбора функций у них существует меню.) Но мы сейчас работаем пока с простейшим, монофункциональным алгоритмом.)
Какова она, его функция? Даны значения 2-х переменных, требуется вывести идентификатор переменной (переменных), значение которой (или которых) минимально.

Отсюда вывод: если значение (и идентификатор) такой переменной найдено, то оно должно быть меньше (или равно) значению другой переменной. Поэтому предположив, что минимальное значение имеет переменная a(k), мы подтвердим эту гипотезу, если реальное сравнение значений даст результат a(k)<a(not k) или a(k)= a(not k). Но, если верно a(k)= a(not k), то та же самая гипотеза (автоматически, то есть без реального сравнения) подтвердится и в отношении a(not k). (т.к. равенство значений переменных даёт истинность любого утверждения о них для обоих переменных: a= b=> R(a) and R(b) Где R – некоторое отношение.)
На этих соображениях и основан алгоритм, а построен – путём поочередного применения гипотезы к исходным переменным.
(а также (вполне математической) теоремы a=b => b=a. Что даёт объединение (обработки) случаев a(1)=a(2) и a(2)=a(1), в разделе Else. Что, вообще-то, относится к уже следующему этапу в создании алгоритма – оптимизации алгоритма. (а вовсе не  к первичной разработке) Но я, как прожженый волк программирования, (одним махом) сделал это объединение. И даже не почувствовал это, сначала. Пока не стал разбираться.)
Следовательно, алгоритм (для задачи1) доказан.
(Пояснение к обозначениям:
a(k) – это некоторая переменная,  a(not k) – это другая (по отношению к 1-ой) переменная.)

Но, для проверки нашего метода доказательства, попробуем доказать некорретный алгоритм:

If a1<a2 then write(‘a1’)
Else write(‘a2’)

Как понятно из предыдущего, алгоритм является доказанным, если только он собирается из осуществлений проверок всех чисел на соответствие условию
a(k)<a(not k) или a(k)= a(not k). То есть, если число действительно минимально, то оно должно быть меньше или равно по сравнению со всеми остальными числами. В данном же алгоритме осуществлена только проверка
a(k)<a(not k) (для признания числа минимальным) Поэтому алгоритм будет выдавать неправильную информацию в случае, если выполняется a(k)= a(not k), а именно ‘a2’ вместо ‘a1 and a2’. Вывод: алгоритм неверен. Вывод2: метод доказательства алгоритмов работает.

Докажем теперь алгоритм для задачи2.
Формулировка этой задачи отличается от задачи1 только одним: количеством переменных, вместо 2 - 3. Казалось бы несущественное отличие, что наводит на мысль: а не доказать ли нам алгоритм для задачи2 – по аналогии с предыдущим доказательством?
Да оно, собственно, оно уже готово, остаётся только чуть-чуть подработать. А именно, в понимании смысла обозначения a(not k). Оно, конечно, уже объяснено выше, но в данном случае есть тонкость: понимать смысл обозначения a(k)<a(not k) следует как сравнение со всеми другими элементами множества a(not k)(т.к. их теперь стало много), и причём с положительным результатом (для всех)
А что получится, если (положительный результат) не для всех?
Тогда вот так нужно изменить условие сравнения: a(k)<a(not k) or a(k)=a(not k) И тогда всё будет получаться правильно.
Плюс к тому во 2-ом случае все удовлетворяющие условию переменные – сразу (без сравнения) записываются в список (потенциально) минимальных.(по отношению к (потенциальной) a(k))
Что и отображено в алгоритме для задачи 2.

вперёд http://www.proza.ru/2015/07/17/1295