Лекция: Определение алгоритма , его свойства

Лейбниц различает два рода истин:

1. истины необходимые, или вечные.
2. истины фактические, или случайные.

Первые имеют содержание, очевидное для каждого ума; они вызывают согласие тотчас же, как только их поймут; противоположного им нельзя мыслить. Таковы истины логики и математики. Другие истины — фактические, или случайные — не имеют такого содержания; противоположное им не заключает логического противоречия. Они выражают действительные отношения вещей между собою, которые мы узнаем, исследуя природу и жизнь, но необходимость которых мы не постигаем и которые поэтому кажутся нам случайными. Познание конкретной действительности частных вещей относится именно к этому последнему разряду истин. Положим, сегодня идет дождь; мы убеждены, что причина этого явления лежит в каких-нибудь предшествующих феноменах природы; эти феномены, в свою очередь, имели причину в предшествующих обстоятельствах, и т. д. без конца. Но почему от века было предопределено, чтобы дождь шёл сегодня, а не завтра и не вчера — этого мы не знаем; это просто дано как факт. Между тем, необходимые истины выражают лишь самые общие отношения и самые общие законы вещей; из них нет исключений, но именно ввиду этой их всеобщности из них нельзя вывести живых явлений вселенной в их индивидуальности. С точки зрения необходимых истин можно представить себе бесчисленное множество самых разнообразных и одинаково бесконечных миров, и ни один из них не будет иметь преимущества перед другими, если только законы логики и математики не будут нарушены. Итак, конкретный строй и конкретное содержание мира, в котором мы живем, не есть геометрическое следствие из необходимых истин, как думал Спиноза. Тем не менее и это конкретное содержание жизни должно иметь свое достаточное основание, ибо закону достаточного основания подчиняется все. Если источником мира является разум, то и все индивидуальное, что содержится и возникает в нём, не может быть случайным само в себе. Оно также имеет свою необходимость, но его необходимость — не та, которая выражается во всеобщих отношениях и формах вещей и которую ведают логика, метафизика и математика. Необходимость общих законов — логическая, необходимость фактического содержания жизни — нравственная. Творческий разум создал мир таким, каков он есть, а не другим, потому что он лучше всех других возможных миров осуществлял цель творения. Если бы был возможен мир лучше существующего, Божественное всеведение знало бы о нём, Божественная благость его желала бы, Божественное всемогущество его создало бы. И, напротив, существование дурного мира противоречило бы этим необходимым свойствам Божества. Однако, безусловный оптимизм Л. сталкивался с весьма важным затруднением: почему существует зло во вселенной? Откуда оно явилось в совершеннейшем из миров? Л. подробно рассматривает этот вопрос в своей «Теодицее». Зло в мире с необходимостью вытекает из самого его существования. В каждой монаде лежит присущая ей ограниченность; без этого она обладала бы совсем абсолютною природою и не отличалась бы от Бога. Отсюда метафизическое зло, с которым связана возможность зла физического, то есть страдания разумных существ в тесном значении этого слова. Зло физическое имеет некоторые высшие основания своего бытия в природе. Жизнь есть воспитание существ для верховных целей, руководимое самим Богом: с этой точки зрения, страдание может быть рассматриваемо как наказание или воспитательное средство. Физическое зло допускается в мир, потому что через него мы достигаем благ, которые иначе были бы закрыты для нас. Вспомним, напр., об одушевленных порывах патриотизма, самоотвержении, равнодушия к смерти, вызываемых в народах войною. Обыкновенно зло служит к тому, чтобы доставить нам большее добро или отвратить ещё большее зло. Вообще жизнь гораздо сноснее и богаче радостями, чем полагают её хулители: при оценке жизни следует принимать в расчет блага беспрепятственной деятельности, здоровья и всего того, что хотя и не вызывает в нас прямо ощутимых удовольствий, но лишение чего нам все-таки показалось бы огромным несчастием. Третий вид зла есть зло нравственное (то есть зло в собственном смысле — грех). Его Божество не могло изъять из мира, не уничтожив самой основы нравственного бытия — свободы. Сущность духа состоит в самоопределении и самодеятельности; без них он был бы призрачным и слепым орудием чуждых ему сил, и его существование не имело бы никакой нравственной цены. Но где свобода, там возможность извращенной деятельности, то есть греха. Впрочем, Л. далеко не был сторонником свободы безразличия. В взгляде на человеческую волю его следует скорее причислить к детерминистам. Пользуясь своим учением о бессознательных представлениях, он решительно утверждает, что наша воля никогда не бывает в состоянии абсолютного равновесия; во всех своих действиях и решениях она всегда подчиняется сильнейшему из своих мотивов. Если бы кто видел нас насквозь, он мог бы предвидеть все наши поступки. Тем не менее мотивы только склоняют нашу волю, но не понуждают её: кроме того, характер их действия на нас зависит от стремлений и склонностей господствующих в нашей душе. Самые мотивы не навязываются нам извне, а развиваются из наших собственных недр в силу побуждений нашей внутренней природы. Поэтому мы с полным правом считаем свободу за коренной признак духа. Л. настаивает на отрицательной природе зла: зло, страдание — только неполнота, несовершенство, недостаточность бытия, а не какая-нибудь положительная сила во вселенной. Этим соображением он старается смягчить свое предположение о том, что мир не может существовать без зла. Далее он восстает против распространенного взгляда, будто наше человеческое благо составляет исключительную задачу мироздания: цель Божественного творчества — во всеобщей гармонии всех вещей и в благе всех разумных тварей, в какие бы формы они ни облекались, а таких форм — бесконечное множество. Таким образом Л. указывает для творения мотив чисто нравственный: творческая деятельность Божества осуществляет высший нравственный идеал творчества — благой миропорядок. С этим учением Л. тесно связано его воззрение на совпадение двух царств: царства природы и царства благодати, то есть законов физических и законов нравственных. Гармония между этими двумя царствами состоит в том, что из естественного хода вещей постоянно вытекает благо духовных существ. Исходя из этой идеи, Л. думает примирить религию с естествознанием. Человек от природы обладает познанием двух центральных истин — бытия Бога и бессмертия души. Таким образом, основа религии заранее существует в душе человека. Откровение только помогает раскрытию идей, семена которых вложены в нас при самом нашем рождении. Между истинною верою и разумом нет и не может быть противоречия. Христианство, как совершеннейшее выражение естественной религии, не дает ничего противоразумного, хотя в нём существуют истины сверхразумные, то есть такие, которых наш ограниченный ум не может понять с полной отчетливостью. В откровении можно указать догматы непостижимые, но нет догматов бессмысленных. Не в догматических формулах и не в богослужебных церемониях заключается, однако, истинная сущность христианства; то, в чём формулы различных исповеданий согласны между собою, важнее их отличий друг от друга. Главные элементы религии — в просвещении и добродетели. Истинным христианином является тот, чья душа полна ясным и светлым спокойствием, любовью к Богу и мировой гармонии и верою в красоту будущей жизни. Соответственно этому, этический идеал полагается Л. в любви, побеждающей темные внушения нашего эгоизма и заставляющей чужое благо ощущать, как свое. Задача человеческой деятельности — в совершенствовании, а совершенствование невозможно без просвещения духа. И чем он просвещеннее, тем с большею любовью претворяет он благо других духов в свое собственное. Добродетель носит в себе залог блаженства и счастья: во-первых, для отдельного человека, потому что через неё он получает истинное совершенство; во-вторых, для его ближних, потому что плод просвещения и понимания есть любовь. В философии права Л. старается сблизить учение о праве с чисто этическими началами. Различая естественное и положительное право, он ищет основу первого в требованиях справедливости. Право коренится в нравственной силе любви, ставящей чужое стремление к счастью наравне с своим собственным. Отрицательно она выражается в боязни нарушить чужое благо, положительно — отчасти в стремлении к благу общественному, отчасти в усилиях распределять жизненные блага сообразно с степенью достоинства и заслуг отдельных лиц.

Определение алгоритма, его свойства

Программирование по определению Н. Вирта — это искусство конструирования. Программы представляют собой конкретные формулировки абстрактных алгоритмов, основанные на конкретных представлениях и структурах данных. Точного определения алгоритма не существует. Обычно под алгоритмомпонимают набор правил, определяющих процесс преобразования исходных данных задачи в искомый результат. Одним из известных алгоритмов является алгоритм Евклида, вычисляющий наибольший общий делитель (НОД) двух целых положительных чисел. Выполним детальный пошаговый разбор этого алгоритма. Будем рассматривать обобщенную постановку задачи, обозначив исходные числа как M и N. В алгоритме M и Nпеременные, каждая из них является областью памяти, в которой хранятся определенные значения. Значения переменных могут изменяться по ходу вычислений. Обращение к переменной происходит по ее имени. Результат алгоритма — значение переменной Nod, где будет храниться общий делитель для M и N.

Шаг1. Обеспечить M >= N. Если M < N, осуществить обмен M <-> N;

Шаг2. Разделить M на N и найти остаток R. (R — вспомогательная переменная ). Очевидно 0 <= R < N;

Шаг3. Если R = 0, то Nod = N, конец алгоритма.В противном случае заменить M на N, N на R и вернуться к шагу 2.

Пусть M = 56, N = 36. Тогда последовательность выполнения шагов алгоритма можно представить следующим образом:

Алгоритм не только задает последовательность выполнения операций при решении конкретной задачи. Он должен обладать следующими свойствами:

— определенность — однозначная определенность результатов выполнения каждого шага алгоритма;

— конечность — однозначная определенность результатов выполнения каждого шага алгоритма за конечное время;

— результативность — получение конечного результата за конечное время;

— массовость — возможность использования алгоритма для некоторого класса исходных данных;

— правильность — получение правильных результатов решения поставленной задачи. Говорят, что алгоритм содержит ошибки, если можно указать такие исходные данные или условия, при которых выполнение алгоритма либо не завершается вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся неправильными.

Кроме переменных в алгоритмах используются массивы переменных — наиболее широко известная структура данных. Массив — область памяти, где могут размещаться совокупности данных определенного типа (целого, вещественного и т.д.). Все компоненты массива имеют одинаковый тип и являются одинаково доступными. Для обращения к отдельной компоненте используется имя массива с индексом, определяющим ее местоположение в массиве. Таким образом, массив характеризуется фиксированным именем, фиксированным типом и фиксированной размерностью. Например, последовательность чисел -1, 25, 13, 18, 8 можно рассматривать как массив целого типа с именем Vector, который содержит 5 элементов. К любому элементу этого массива можно обратиться следующим образом:

Vector[1], где I может принимать значения в диапазоне от 1 до 5. Vector[2] = 25;

Разработка алгоритма решения задачи — наиболее ответственный этап в программировании. Игнорирование этого этапа является причиной многочисленных ошибок при проектировании программ. На этапе разработки алгоритма устанавливается необходимая логическая последовательность вычислений с учетом выбранного метода решения. При разработке алгоритма необходимо стремиться к максимальной простоте и наглядности. Это требование относится как к содержательной стороне, так и к форме записи алгоритма. Существует несколько способов записи алгоритмов, отличающихся друг от друга наглядностью, компактностью, степенью формализации и другими показателями. Наиболее распространенными являются:

— графический способ (схемы алгоритмов, диаграммы Насси — Шнейдермана );

— словесный способ ( специальный язык проектирования программ — псевдокод и программа).

Следуя принципам структурного программирования, задачу необходимо представить как набор последовательных шагов (действий), избегая непоследовательных переходов. Этому требованию в полной мере отвечают диаграммы Насси — Шнейдермана и псевдокод.

Рассмотрим алгоритм нахождения минимального значения Min среди трех заданных величин: A, B, C. Запись этого алгоритма в виде диаграммы Насси — Шнейдермана представлена на Рис.1.

Рис.1. Поиск минимального значения из трех заданных величин

Несомненным достоинством любого графического способа представления является наглядность. Однако, в случае сложных алгоритмов с большим числом ветвлений и циклов подготовка и чтение таких диаграмм существенно затруднены. Именно по этой причине наибольшее распространение получило представление алгоритмов на псевдокоде в виде последовательности действий. На Рис.2 представлен общий вид описания алгоритма на псевдокоде.

Алгоритм < название >

Начало< последовательность действий >

Конец

Рис.2. Общий вид описания алгоритма на псевдокоде

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

Определяющей особенностью вычислительного процесса является возможность расчленить его на отдельные, дискретные, действия, чего нельзя сказать о процессе непрерывном. В дискретном процессе Галчонок не может задать свой сакраментальный вопрос, пока постукивание продолжается. Собственно говоря, «тук-тук» и не обладает, с точки зрения алгоритма, протяженностью во времени. Это событие мгновенно, в противном случае мы бы расчленили его на k отдельных «туков», а порядковые номера шагов, начиная с третьего, увеличились бы на k-1.

Таким образом, второй особенностью является последовательность действий процесса, оформленных как предписания алгоритма. Здесь вновь имеет место важное ограничение: так называемые параллельные алгоритмы остаются за рамками обсуждения.

Предписаний должно быть конечное число; в приведенном алгоритме их семь. Каждое из них в отдельности должно быть точным и не допускать неопределенного толкования. Скажем, вопрос «кто там?» адресован вполне определенному источнику стука, располагающемуся за пределами дома около двери.

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

Вообще говоря, не столь существенно, проводится ли процесс, согласно алгоритму, именно компьютером. Содержание предписаний таково, что их может осуществить человек, а иногда даже, как видим, почти обыкновенные галки. Разница, если иметь ввиду собственно достижение результата, только в требуемом для исполнения алгоритма времени. Следовательно, нужно отличать теоретическую «мгновенность» шага алгоритма от реального времени осуществления его вычислительным устройством. И даже компьютеру может оказаться не по силам алгоритм, состоящий из конечного, но столь большого числа шагов, что окончания работы «заказчику» практически не дождаться.

Естественно, процесс должен преследовать конкретную цель, без чего постановка задачи с алгоритмическим содержанием смысла не имеет. Так, бесцельный процесс «переливания из пустого в порожнее» отнести к разряду алгоритмических мы не рискнем.

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

Однако провести анализ алгоритма разработчику следует, чтобы оценить, сколь велико оказывается число шагов. Мораль ордена иезуитов — «цель оправдывает средства» — здесь не действует.

Как пишет Кнут, «программист может многому научиться, прочитав хорошую поваренную книгу». Вероятно, он имел ввиду, что такое чтение стало бы неплохой тренировкой в поиске ошибок и неточностей, связанных, в том числе, с разницей в бытовом и «компьютерном» представлениях об алгоритме. Что ж, проведем, следуя рекомендации, небольшую тренировку.

Беру с полки одну из подходящих случаю книг — попались «Мясные и грибные блюда» (1984). Открываю наугад: стр.45. Рецепт, если вы не являетесь вегетарианцем, выглядит заманчиво: «жаркое из говядины (ростбиф)». Нетрудно догадаться, что на выходе кулинарного процесса ожидается готовый к употреблению ростбиф, что и составляет сформулированную в названии рецепта цель.

Представить алгоритм без выходных данных затруднительно: зачем он тогда нужен? И все же рискнем. Вспомним миф о Сизифе: целью процесса было не закатывание камня на вершину горы, а наказание нечестивца. Прояви Зевс чуть больше гуманности, и пожизненное наказание можно было бы заменить фиксированным числом шагов алгоритма. При необходимости задержки основного вычислительного процесса можно добавить внутрь него как отдельный шаг вызов процедуры, которая выполняет заданное число каких-нибудь операций с невостребованным итогом. Этот подпроцесс не формирует выходных данных. Впрочем, вы можете и не согласиться с предлагаемой трактовкой, интерпретируя как выходное значение сам факт завершения подпроцесса, поскольку в том и состояла цель его запуска.

Что же касается входной информации, то она действительно требуется не всякому алгоритму. В нашем рецепте входные данные присутствуют — это перечисленные ингредиенты: 1 кг говядины (филе или спинная часть), 50 г жира, соль, перец, 30 г сливочного масла, хрен, вода. В сумке Печкина их тоже можно отыскать (не продукты, а входные данные!) — это письмо, которое почтальон собирается вручить адресату. А вот в задании «нарисовать квадрат произвольного размера, пользуясь циркулем и линейкой» оговорен лишь конечный результат, а на входе — ничего.

Кроме входных и выходных данных, как правило, алгоритм предусматривает временное формирование промежуточных данных, которые вновь поступят на обработку. Исходные 50 г жира, когда повар растопит их на сковороде, переходят, согласно законам физики и кулинарии, в промежуточное состояние.

В том же рецепте примерно на полстраницы приводится описание технологического процесса, цитировать которое здесь не станем из опасения, что читатель забудет, исходя слюной, основной предмет обсуждения. Остановимся только на некоторых неточных инструкциях, которые несут неполную информацию. Вот одна из них: «филе жарят 20-25 минут». Так 20 или 25? Без должного поварского опыта, который никак не отражен в описании, остается определенный риск завершить «алгоритмическую обработку» несъедобным результатом.

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

В противоположность детерминированному, в алгоритме стохастическом заложена некоторая неопределенность в выборе очередной инструкции. Таков был случайный выбор рецепта жаркого: при повторении манипуляции с поваренной книгой я, скорее всего, открою ее на другой странице. Но это не значит, что вычислительному устройству угрожает положение буриданова осла и оно может перейти в состояние летаргической паузы. Напротив, выбор конкретной инструкции непременно происходит, только — на основе вероятностного механизма. При этом разработчик алгоритма планирует, что, независимо от выбранного продолжения, конечный результат будет удовлетворять условиям поставленной задачи. Так, нашему мясному полуфабрикату не повредят ни 20 минут прожаривания, ни 25 минут, ни любое промежуточное значение, и в итоге заказчик получит именно ростбиф.

Нередко, перечисляя непременные свойства алгоритма, к их числу относят "массовость", имея ввиду возможность его применения «для решения однотипных задач». Универсальность этого требования вызывает сомнения, поскольку «штучное» предназначение некоторых алгоритмов представляется достаточно разумным. Например, рассказав друзьям анекдот, станете ли вы пересказывать его в той же аудитории? Удастся ли вам в другой компании повторить процесс без малейших отклонений? А как здесь иначе интерпретировать «однотипность», я не знаю.

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

Наконец, читателям-скептикам, которые сомневаются в правомерности последних примеров для опровержения свойства «массовости», предлагаю выполнить алгоритмическое

Структурные диаграммы — могут использоваться в качестве структурных блок-схем, для показа межмодульных связей, для отображения структур данных, программ и систем обработки данных. Существуют различные структурные диаграммы: диаграммы Насси — Шнейдермана, диаграммы Варнье, Джексона, МЭСИД и др.

Рассмотрим пример использования диаграмм МЭСИД.

Задан одномерный массив из положительных и отрицательных чисел. Требуется определить частное от деления суммы положительных элементов на сумму отрицательных элементов этого массива. Справа от диаграммы приводятся соответствующие операторы языка Паскаль.

Языки программирования — изобразительные средства для непосредственной реализации программы на ЭВМ. Программа – алгоритм, записанный в форме, воспринимаемой ЭВМ.

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

Транслятор с Паскаля – компилирующего типа. Текст на исходном языке переводится в текст на машинном языке и получается так называемый объектный модуль. Затем объектный модуль должен быть обработан программой Редактором межпрограммных связей и только после этого программа будет готова к выполнению.