Л.С. Корухова, М.Р. Шура-Бура - Введение в алгоритрмы, страница 2

При обработке информации, особенно когда речь идетоб автоматизации обработки, всегда появляются различные уровни понимания4обрабатываемой информации, представленной в той или иной форме. С интерпретациейсвязано понятие исполнителя, способного по-своему понять заданную форму.Компьютер предъявляет особые требования к форме задаваемой информации, вчастности, к форме той части информации, которая определяет процесс обработки. Всвязи с этим возникают три уровня общения с ЭВМ:1. Обращение за услугой2. Обучение компьютера и проверка ее "умения"3. Создание компьютераДля реализации второго и третьего уровней нужны специалисты особойквалификации.

Эту квалификацию вы должны получить, обучаясь на факультете.Цель настоящего курса - заложить основы вашего умения учить машины и участвоватьв их создании.2. ПРОЦЕССЫ ОБРАБОТКИ ИНФОРМАЦИИ И АЛГОРИТМЫДетализируя представление о задаче обработки информации<ИСХОДНАЯ информация > ==> < ИСКОМАЯ информация >,мы приходим к понятию процесса обработки:I 1 ==> I 2 ==> ...==> I n-1 ==> I n ,где I 1 - ИСХОДНАЯ информация, I n - искомая информация, а I j, j = 2, 3, ..., n-1 получаемая в процессе обработки информация, которую можно назвать промежуточной.Конечно, здесь точнее было бы говорить о пошаговом изменении формы информациии получении ИСКОМОЙ информации, так сказать, в "явном" виде, который можноинтерпретировать как требуемый результат обработки. Переход от I j к I j+1(получение I j+1из I j ) можно назвать шагами процесса обработки.

Легко понять, что обработкаинформации I 1 ==> I n может быть реализована различными процессами. До тех пор, покамы никак не ограничиваем того, что мы называем шагами процесса, мы малопродвигаемся в понимании последнего. Интуитивно хотелось бы, чтобы переходы I j==>I j+1 были проще обработки I 1 ==>I n. Естественно желать, чтобы шаги былидостаточно просты и, более того, чтобы каждый из них, в свою очередь, сводился кпоследовательности промежуточных щагов перехода (подшагов), принадлежащих заранеечетко определенной совокупности. С другой стороны, поскольку, как было замеченовыше, процесс не определяется однозначно задачей получения I n из I1, появляется нужда вего описании.

Заманчиво пользоваться таким описанием, которое не содержит в явномвиде перечень всех шагов процесса, но дает возможность определить очередной шаг I j==> I j+1, коль скоро выполнены все предыдущие. Математика давно и широко пользуетсяпроцессами такого рода, получившими название алгоритмов .Классическим примером математического алгоритма является алгоритм Евклиданахождения наибольшего общего делителя (НОД) двух натуральных чисел. Этот алгоритмможно описать следующим образом.2.1.

АЛГОРИТМ ЕВКЛИДАПусть даны два натуральных числа N 1 >= N 25Выполняем :1) Делим нацело N 1 на N 2, получая остаток N 3, удовлетворяющий неравенствам 0 <=N3<N22) Если N 3= 0, то N 2 есть искомый НОД, иначе делим N 2 нацело на N 3, получаяостаток N 4>= 0, с которым поступаем так же, как с N 3, и т.д.Таким образом получаем убывающую последовательностьN 1 > N 2 > N 3>...> N k > N k+1= 0 ,где N k есть наибольший общий делитель чисел N 1 и N 2 .2.2. СВОЙСТВА АЛГОРИТМОВВ математике, пользуясь понятием алгоритма, долгое время удовлетворялись лишьинтуитивным уровнем определения самого понятия алгоритма. Считалось, что алгоритм это процесс обработки исходных данных, который описан конечным числом правил.

Приэтом каждое правило точно определяет некоторое достаточно простое действие (шагалгоритма). После выполнения каждого шага точно определено "что делать дальше", т.е.получен ли окончательный результат или же оказывается известным, какое из правилопределяет следующий шаг процесса. Результат достигается конечным числом шагов иливообще не достигается.Очевиден интуитивный уровень приведенного определения, содержащего такиепонятия, как " исходные данные ", " точно ", " достаточно просто ", " действие " и "конечный результат ".Особого внимания заслуживает понятие " исходных данных ". Предполагается, чтоалгоритм предназначен для работы с различными исходными данными и, более того,совокупность различных " исходных данных ", вообще говоря, потенциально бесконечна.Так, например, для алгоритма Евклида " исходными данными " является любая паранатуральных чисел.В литературе указанные свойства алгоритмов часто формулируются следующимитерминами :1) Однозначность ( детерминированность )2) Результативность (конечность)3) Простота и понятность4) МассовостьДо тех пор, пока математики ограничивались лишь поисками и построением(описанием) алгоритмов, интуитивный уровень определения алгоритма оказывалсядостаточным.

Однако ситуация изменилась, как только математика столкнулась сзадачами, для решения которых никак не удавалось ни найти алгоритмы, ни подтвердитьвозникшие предположения, что таких алгоритмов попросту не существует. Строгому жеобоснованию таких предположений препятствовало отсутствие формального понятияалгоритма. Одной из таких задач оказался вопрос о разрешимости алгебраическихуравнений в целых числах - проблема, включенная в начале ХХ века в число наиболееважных и трудных задач, стоящих перед математикой - так называемых проблемГильберта.Было предложено несколько способов определения понятия алгоритма, основанных наразличных подходах.

Замечательно, что все эти определения оказались, по существу,эквивалентными.6Обратим внимание на то, что в требуемом описании алгоритма, вообще говоря, несодержится указаний на общее число шагов процесса. Более того, описанный процессможет и вовсе не завершиться или, как говорят, зациклится.Требовать в определении алгоритма завершения процесса нецелесообразно. Этотребование, во-первых, существенно обеднит понятие алгоритма и, во-вторых, вообщеговоря, оно не проверяемо.

Как это будет видно из дальнейших рассмотрений, можносчитать, что алгоритм неприменим на тех исходных данных, при которых онзацикливается, и применим на тех, при которых процесс заканчивается.3. АЛГОРИТМЫ И ОТОБРАЖЕНИЯДля формального определения алгоритма нам потребуются некоторые широкоиспользуемые в математике понятия и обозначения.Прежде всего, мы будем иметь дело с понятием множества, как совокупностиобъектов, называемых элементами этого множества.

Будем считать, что существуетособое " пустое " множество ∅, в котором нет ни одного элемента. Через a ∈ А будемобозначать, что объект a является элементом множества А. c ∉ А будет означать, чтообъект c не является элементом А. Формула А = { a i } означает, что А являетсямножеством объектов a i в предположении, что i принадлежит опреде леннойсовокупности значений. В этом определении мы не накладываем никаких ограничений нахарактер объектов. Не предполагается и какая-то их однородность или "похожесть".В качестве объекта, входящего в множество, может выступать и любое множество.

ЗаписьА = { a , b , c } означает, что множество А состоит из элементов a , b , c .Множество В будем называть подмножеством множества А, если каждый элементмножества В является элементом множества А. В ⊂ А (А ⊃ В) означает, что В подмножество множества А. Заметим, что пустое множество является подмножествомлюбого множества. Если В⊂ А и существует элемент a ∈ А и a ∉ В, то В называетсясобственным подмножеством множества А.Объединением множеств А и С называется множество, состоящее из всех объектов(элементов), входящих по крайней мере в одно из множеств А или С.

Объединение(сумма) двух множеств А и С обозначается А ∪ C. Множество, состоящее из всехэлементов, входящих как в множество А, так и в множество С, называется пересечениеммножеств А и С и обозначается А ∩ С.Множество С, состоящее из всех тех элементов множества А, которые не входят вмножество В, обозначается А \ В (вычитание множеств).

С = А \ В означает, что, еслиc ∈ С, то c ∈ А и c ∉ В.Говорят, что задано отображение F множества А в множество С, если каждому a ∈ Апоставлено в соответствие c ∈ С. Иногда пишут c = F( a ) и говорят, что c являетсяобразом элемента a (с - значение отображения F на а ) и что a - прообраз с. Наличиеотображения F изображают диаграммойFАСИногда мы будем опускать в этой диаграмме обозначение отображения и писатьпросто :АСЕсли при таком отображении F каждый элемент из С оказывается образом некоторогоэлемента из А, то F называется отображением множества А на множество С.Если В ⊂ А иGАС7то говорят, что G является частичным отображением множества А в С или что G частичная функция. Считается, что на А \ В отображение G не определено.Отображение F множества А на множество С называется взаимно-однозначным , еслииз a ∈ А, b ∈ A и a ≠ b следует, что F( a ) ≠ F( b ).Вводя понятие отображения (функции), мы не накладываем никаких ограничений наспособы задания отображения.

В ряде случаев нас может интересовать лишь фактсуществования соответствующего отображения и вытекающие из этого факта следствия.Нет сомнения, однако, что отображения (функции), для которых при заданном a мыможем найти F( a ), представляют особый и несомненный интерес. Отображения такогорода тесно связаны с понятием алгоритмов.Пусть даны два множества А и В. Декартовым произведением множеств А и Вназывается множество С всех пар ( a , b ), где a - любой элемент из А, b - любой элементиз В.С=А×Вc ∈ С тогда и только тогда, когда c = ( a , b ), где a ∈ А и b ∈ В.Понятие декартова произведения естественно распространяется на произведениелюбого конечного числа множеств.