рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Определение алгоритма, его свойства - раздел Математика, 1.1. Определение Алгоритма , Его Свойства Программи...

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

Программирование по определению Н. Вирта - это искусство конструирования. Программы представляют собой конкретные формулировки абстрактных алгоритмов, основанные на конкретных представлениях и структурах данных. Точного определения алгоритма не существует. Обычно под алгоритмомпонимают набор правил, определяющих процесс преобразования исходных данных задачи в искомый результат. Одним из известных алгоритмов является алгоритм Евклида, вычисляющий наибольший общий делитель (НОД) двух целых положительных чисел. Выполним детальный пошаговый разбор этого алгоритма. Будем рассматривать обобщенную постановку задачи, обозначив исходные числа как 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. Общий вид описания алгоритма на псевдокоде

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

Алгоритмы

 

Главная     Основные алгоритмические структуры    

 

Алгоритм - это точное предписание исполнителю совеpшить определенную последовательность действий для достижения поставленной цели за конечное число шагов. Свойства алгоритмов
  • результативность
  • дискретность
  • правильность
  • массовость
  • конечность
Способы описания алгоритмов
словесный графический
  • на естественном языке инструкция
  • на алгоритмическом языке Program Zadacha; var a,b,c:integer; begin writeln('Введите a,b');
  • формульно-словесный решение задачи по химии, физике, геометрии
  • псевдокоды
  • диаграммы Насси-Шнейдермана.
  • блок-схемы

 

 

 

Алгоритм #1.
  1. Почтальон Печкин стучит в дверь - "тук-тук".
  2. Если Галчонок слышит стук, то переход к шагу 3, иначе - к шагу 1. {Если птица глуховата или ее нет дома, то Печкину не позавидуешь.}
  3. Галчонок: "Кто там?"
  4. Если Печкин слышит вопрос "кто там?" {а если глуховат сам почтальон, то дела его опять-таки плачевны}, то переход к шагу 5, иначе - к шагу 1.
  5. Печкин: "Это я, почтальон Печкин. Откройте дверь. Я принес письмо для вашего Мальчика".
  6. Если Галчонок открывает дверь {надеемся, героической птице это по силам, а то вновь бедный Печкин в безвыходном положении, поскольку процесс не завершится}, то переход к шагу 7, иначе - переход к шагу 1.
  7. Почтальон Печкин вручает конверт с письмом.
{Комментарии в скобках, здесь и выше, призваны продемонстрировать, даже на столь простом примере, как много подводных камней ждет программиста при отладке программы, если алгоритм недостаточно продуман.}

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

Рис. 1.

 

Рис. 2.

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

– Конец работы –

Используемые теги: определение, алгоритма, Свойства0.051

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Определение алгоритма, его свойства

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Алгоритм и требования к алгоритму свойства алгоритма
Object Inspector Options goEditing True... StringGrid FexedCols Rows n... Var I J integer Begin...

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

Тип ячейки определяет строение и свойства кристалла в целом, а свойства каждого из этих кристаллов определяет свойства всего кристалла в целом
Кристаллическое строение металлов... Металлы Ме являются поликристаллическими веществами т е они состоят из... Кристаллическое состояние твердое состояние вещества...

Понятие и её свойства алгоритма. Способы записи алгоритмов.
Способы записи алгоритмов... Оформить записать алгоритмы можно несколькими способами... Словесный способ записи алгоритмов основан на использовании средств обычного языка но с жестко ограниченным...

МЕТОДЫ ОПРЕДЕЛЕНИЯ СВОЙСТВ ГОРНЫХ ПОРОД
На сайте allrefs.net читайте: "МЕТОДЫ ОПРЕДЕЛЕНИЯ СВОЙСТВ ГОРНЫХ ПОРОД"

Лекции по курсу: Биохимия Тема: ПЕПТИДЫ, БЕЛКИ: ИХ СТРОЕНИЕ, СВОЙСТВА, ЗНАЧЕНИЕ В ОРГАНИЗМЕ, МЕТОДЫ ИССЛЕДОВАНИЯ.ФИЗИКО-ХИМИЧЕСКИЕ СВОЙСТВА БЕЛКОВ. 10
Федеральное агентство по образованию... Государственное образовательное учреждение высшего профессионального...

Использование гидролиза для определения химических свойств белка, ренгеноструктурный анализ, электронная микроскопия
Образование АТФ в процессе метаболизма идет двумя путями окислительного и субстратного фосфорилирования дых цепь ЦТК гликолиз Возникновение... Свойства белков их биологическая роль Методы очистки и разделения Свойства белков кислото основные и...

АЛГОРИТМЫ ВЫПОЛНЕНИЯ ПРАКТИЧЕСКИХ НАВЫКОВ, НЕОБХОДИМЫХ ДЛЯ ОКАЗАНИЯ ПЕРВОЙ ВРАЧЕБНОЙ ПОМОЩИ ПРИ НЕОТЛОЖНЫХ АЛГОРИТМЫ ВЫПОЛНЕНИЯ ПРАКТИЧЕСКИХ НАВЫКОВ, СОСТОЯНИЯХ И ЗАБОЛЕВАНИЯХ
АЛГОРИТМЫ ВЫПОЛНЕНИЯ ПРАКТИЧЕСКИХ НАВЫКОВ НЕОБХОДИМЫХ ДЛЯ ОКАЗАНИЯ ПЕРВОЙ ВРАЧЕБНОЙ ПОМОЩИ ПРИ СОСТОЯНИЯХ И ЗАБОЛЕВАНИЯХ...

МЕТОДЫ ОПРЕДЕЛЕНИЯ МЕХАНИЧЕСКИХ СВОЙСТВ ПРИ КРАТКОВРЕМЕННЫХ СТАТИЧЕСКИХ НАГРУЗКАХ
МЕТОДЫ ОПРЕДЕЛЕНИЯ МЕХАНИЧЕСКИХ СВОЙСТВ ПРИ КРАТКОВРЕМЕННЫХ СТАТИЧЕСКИХ НАГРУЗКАХ... ИСПЫТАНИЯ НА РАСТЯЖЕНИЕ Испытания на растяжение производятся на...

Важнейшие соединения бора, алюминия иах физико-химические свойства. КО и ОВ свойства. Борная кислота. Кристаллогидрат тетраборатанатрия /бура
Содержание темы и учебно целевые вопросы... Общая характеристика р элементов Неметаллы амфотерные элементы Изменение... Элементы III А группы и IV А группы Общая характеристика групп...

0.031
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам