Существуют следующие способы описания (представления) алгоритмов:
словесное описание;
описание алгоритма с помощью математических формул;
графическое описание алгоритма в виде блок-схемы;
диаграмма оформления: Насси-Шнейдерман
1)Словесное описание алгоритма представляет собой описание структуры алгоритма на естественном языке. Например, к приборам бытовой техники, как правило, прилагается инструкция по эксплуатации, т.е. словесное описание алгоритма, в соответствии с которым данный прибор должен использоваться.
Графическое описание алгоритма в виде блок-схемы – это описание структуры алгоритма с помощью геометрических фигур с линиями связи.
2) Блок схема алгоритма – это графическое представление метода решения задачи, в котором используются специальные символы для отображения операций.
Символы, из которых состоит блок-схема алгоритма, определяет ГОСТ 19.701-90. Этот ГОСТ соответствует международному стандарту оформления алгоритмов, поэтому блок-схемы алгоритмов, оформленные согласно ГОСТ 19.701-90, в разных странах понимаются однозначно.
Рассмотрим простейший пример. Пусть необходимо описать алгоритм вывода на экран монитора наибольшего значения из двух чисел.
Рисунок 1 - Пример описания алгоритма в виде блок-схемы
Описание этого же алгоритма на псевдокоде:
Начало
Ввод чисел: Z, X
Если Z > X то Вывод Z
Иначе вывод Х
Конец
3)Диаграмма Насси — Шнейдермана — это графический способ представления структурированных алгоритмов и программ, разработанный в 1972 году американскими аспирантами Беном Шнейдерманом и Айзеком Насси.
Диаграммы Насси — Шнейдермана получили широкое распространение в некоторых странах, особенно в Германии, где для них даже был разработан официальный стандарт Немецким институтом по стандартизации: DIN 66261.
Диаграммы Насси — Шнейдермана имеют ряд преимуществ перед блок-схемами при разработке структурированных алгоритмов и программ:
Запись является более компактной.
Изобразив алгоритм или программу в виде диаграммы Насси — Шнейдермана, можно быть гарантировано уверенным в том, что принципы структурного программирования соблюдены.
Диаграммы Насси — Шнейдермана удобнее использовать для пошаговой детализации задачи, так как они тоже строятся по принципу пошаговой детализации — изначально диаграмма представляет собой один прямоугольник, затем в нём рисуется некоторая структура управления, в которой имеется несколько прямоугольников, и далее с каждым прямоугольником может быть проделана та же операция.
Каждый из перечисленных способов изображения алгоритмов имеет и достоинства и недостатки. Например, словесный способ отличается многословностью и отсутствием наглядности, но дает возможность лучше описать отдельные операции. Графический способ более наглядный, но часто возникает необходимость описать некоторые операции в словесной форме. Поэтому при разработке сложных алгоритмов лучше использовать комбинированный способ.
Проблема постановки задачи
Постановка задачи – предполагает подробное описание самой задачи, описание входной и выходной информации, формулируется конечная цель, которую необходимо достигнуть при решении задачи. Постановка задачи иногда связана с построением математической модели изучаемого процесса и часто представляет собой довольно сложный этап в решении задачи.
Как правильно сформулировать задачу?
для того, чтобы сформулировать проблему в терминах системного анализа, ужно:
Шаг №1. Дать значения параметров в текущем состоянии.
Шаг №2. Определить значения параметров в желаемом состоянии.
(Допустим, возьмем такую проблему, как повышение продаж.
На языке системного анализа она будет сформулирована так:
«Есть Бизнес с чистой прибылью 1 млн. руб. в мес.
Хотим, чтобы этот бизнес приносил в месяц 1,5 млн. руб. чистой прибыли».)
Универсальный алгоритм решения задач.
Смысл в том, что, если «непонятно, как решать проблему на уровне высокой системы», нам нужно:
Декомпозировать нашу систему, то есть разделить ее на подсистемы.
Далее для каждой подсистемы описать ее текущее состояние (то есть определить параметры).
Далее для каждой подсистемы определить желаемое состояние (то есть опять задать параметры).
Если на уровне подсистем мы не понимаем - как решать задачу, то нужно опять каждую подсистему декомпозировать и формулировать проблему на уровне более маленьких и простых систем.
И делать это нужно до тех пор, пока нам не станет очевидно - как решать проблему на уровне маленькой подсистемы…
(В нашем примере: Далее наша задача систему под названием «Бизнес» декомпозировать на подсистемы, замерить их параметры, сказать, какие параметры должны быть во втором состоянии, и в каждой из этих подсистем довести параметры до второго состояния - тогда бизнес будет приносить по 1,5 млн. руб. в мес.)
Выводы:
Чтобы решить проблему нужно:
Описать два состояния системы (текущее и желаемое).
Если не понятно как решать задачу на уровне высокой системы, то нужно систему разделить на подсистемы и сформулировать проблему для каждой из подсистем.
Декомпозировать нужно до тех пор, пока не будет понятно, что конкретно нужно сделать.
2. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ.
Выбор средств и методов для записи алгоритма зависит прежде всего от назначения ( природы ) самого алгоритма, а также от того, кто (что ) будет исполнителем алгоритма.
Алгоритмы записываются в виде : - словесных правил;
- псевдокода;
- блок схем;
- программ и т.д.;
2.1. СЛОВЕСНОЕ ОПИСАНИЕ АЛГОРИТМА.
Это, по существу, обычный язык, но с тщательным отбором слов и фраз, не допускающих лишних слов, двусмысленностей и повторений. Дополняется язык обычными математическими обозначениями и некоторыми специальными соглашениями.
Алгоритм описывается в виде последовательности шагов. На каждом шаге определяется состав выполняемых действий и направление дальнейших вычислений. При этом, если на текущем шаге не указывается какой шаг должен выполняться следующим, то осуществляется переход к следующему шагу.
ПРИМЕР : Найти наибольшего из трёх заданных чисел a, b, c.
• 1. Сравнить a и b. Если a>b,то в качестве максимума t принять a, иначе (a<=b) в качестве максимума принять b (t=b).
• 2. Сравнить t и c. Если t>c, то перейти к шагу 3. Иначе (t<c) принять в качестве максимума c (t=c).
• 3. Принять t в качестве результата.
НЕДОСТАТКИ СЛОВЕСНОГО СПОСОБА :
- отсутствие наглядности;
- недостаточная точность.
ДОСТОИНСТВА : С его помощью можно описать любые алгоритмы, в том числе и вычислительные.
СПЕЦИАЛЬНЫЕ СОГЛАШЕНИЯ ДЛЯ СЛОВЕСНОЙ ЗАПИСИ АЛГОРИТМОВ:
• 1. Знак присваивания, слева от которого записывают ту переменную, которой присваивается значение, записанное справа от знака присваивания. Например, х:=х+1
• 2. Для задания значения исходных данных используют указания: ВВЕСТИ
• 3. Для запоминая промежуточных результата используют вспомогательные переменные.
• 4. Для указания начала и конца алгоритма используют указания: НАЧАЛО и КОНЕЦ.
• 5. Все шаги нумеруют.
Пример алгоритма построения треугольника по трём сторонам:
• 1. Начало.
• 2. На произвольной прямой выбрать точку А. Раствором циркуля, равным а, отложить отрезок АВ=а.
• 3. Из точки А провести окружность радиуса в.
• 4. Из точки В провести окружность радиуса с.
• 5. Конец.
2.2. ГРАФИЧЕСКИЙ СПОСОБ ОПИСАНИЯ АЛГОРИТМА.
Является достаточно наглядным и простым способом описания алгоритма.
Графический способ описания алгоритма - это способ представления алгоритма с помощью общепринятых графических фигур, называемых блок-схемами, каждая из которых описывает один или несколько шагов алгоритма.
Внутри блока записывается описание команд или условий.
Для указания последовательности выполнения блоков используют линии связи ( линии соединения ).
Последовательность блоков и линий образуют блок-схему алгоритма .
2.3. ОПИСАНИЕ АЛГОРИТМОВ С ПОМОЩЬЮ ПРОГРАММ.
Алгоритм, записанный на языке программирования называется программой.
Словесная и графическая форма записи алгоритма предназначены для человека. Алгоритм, предназначенный для исполнителя на компьютере записывается на языке программирования (языке, понятном ЭВМ). Сейчас известно несколько сот языков программирования. Наиболее популярные: Бейсик, Си, Паскаль, Пролог, ПЛ, Ада и т.д.
Пример программы на языке программирования Паскаль:
PROGRAM RR;
VAR A,B,C, max: INTEGER;
BEGIN
WRITE(‘ ВВЕДИТЕ A, B, C');
READLN(A,B,C);
IF A>B THEN max:=A
ELSE max:=B;
IF C>max THEN max:=C;
WRITELN(max);
END.
Словесно - формульный;
1) структурный или блок - схемный;
2) с помощью графов - схем;
3) с помощью сетей Петри.
При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.
Пример: необходимо найти значение следующего выражения: у = 2а – (х+6).
Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:
1. Ввести значения а и х.
2. Сложить х и 6.
3. Умножить a на 2.
4. Вычесть из 2а сумму (х+6).
5. Вывести у как результат вычисления выражения.
При блок - схемном описании алгоритм изображается геометрическими фигурами (блоками), связанными по управлению линиями (направлениями потока) со стрелками. В блоках записывается последовательность действий.
Преимущества:
- наглядность: каждая операция вычислительного процесса изображается отдельной геометрической фигурой.
- графическое изображение алгоритма наглядно показывает разветвления путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и Другие детали.
Структурные схемы алгоритмов
- Последовательность двух или более операций;
- выбор направления;
- повторение.
Любой вычислительный процесс может быть представлен как комбинация этих элементарных алгоритмических структур.
Универсальные модели алгоритмов. Машина Тьюринга. Примеры реализации.
Машина Тьюринга: небесконечна, достаточна; машинка ездит влево/вправо, совершает только 7 действий. 7действий: сдвинуться на ячейку влево, вправо, оставаться на месте, записывать символ в ячейку, стереть символ из ячейки, переход к след команде, остановка.
Элементы: 1-лента(набор ячеек с символами, достаточных для вып-я любой операции); 2-считыватель(голова-машинка, кот-я вып-ет 7 действий); 3-таблица(правила поведения записаны в таблице); 4-правило (1 высказывание). Правило: -состояние, -символ, -смещение(сдвиг). Машина Тьюринга – мысленный эксперимент (т.е. ее не сущ-ет), в котором показывается работа автомата, демонстрирующего работу алгоритма. Машина Тьюринга в которой для каждого состояния есть только 1 действие, то она наз-ся детерминированной, а если больше 1 действия, то недетерминированной. Машина Тьюринга использует элементарные операции для последовательного выполнения любого сложного алгоритма. Это значит, что любую уже решенную задачу можно представить в виде переборов вариантов и такие задачи наз-ся тьюринг-полными. Тезис Тьринга Чёрча: любую решенную задачу можно представить в виде тьюринг-полного набова действий (все что решено вычисл-ся перебором,а все что нельзя представить перебором это либо еще не решено, либо не имеет решения впринципи). Суть тезиса: где композиция в разложени большой сложной решенной задачи на огромное кол-во элементарных операций, символизирующих собой 1 такт работы процессора.
3. Универсальные модели алгоритмов. Нормальные алгоритмы Маркова. Примеры реализации.
Норма́льный алгори́тм Ма́ркова (НАМ) — один из стандартных способов формального определения понятия алгоритма. Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.
Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. НАМ является Тьюринг-полным языком, что делает его по выразительной силе эквивалентным машине Тьюринга и, следовательно, современным языкам программирования.
Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.
Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида L\to D, где L и D — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида L→t D, где L и D — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы → и → не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).
Примером схемы нормального алгоритма в пятибуквенном алфавите |*abc может служить схема
|b → ba|
ab → ba
b →
*| → b*
* → c
|c → c
ac → c|
c → .
Процесс применения нормального алгоритма к произвольному слову V в алфавите этого алгоритма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V' — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V', то работа алгорифма считается завершённой, и результатом этой работы считается слово V'. Иначе среди формул подстановки, левая часть которых входит в V', выбирается самая первая. Если эта формула подстановки имеет вид L → D, то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего работа алгорифма считается завершённой с результатом RDS. Если же эта формула подстановки имеет вид L → D, то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего слово RDS считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.
Например, в ходе процесса применения алгорифма с указанной выше схемой к слову |*|| последовательно возникают слова |b*|, ba|*|, a|*|, a|b*, aba|*, baa|*, aa|*, aa|c, aac, ac| и c||, после чего алгорифм завершает работу с результатом ||. Другие примеры смотрите ниже.
Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».
Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.
Элементарный исполнитель является Тьюринг-полным, который выполняет любую решенную задачу методом замены символов,в конкретном слове в рамках конкретного алфавита.
Устройство машины Маркова:
1) Алфавит ((набор символов)
2) Символы (symboe)
3) Слова (words)
4) Вхождение Apperarance (появление символов в слове)
5) Правило (rule)
6) Образец (pattern)
Принцип работы:
Считыватель слева на право просматривает слово и выполняет правила для первого найденного сочетания символов.
Алгоритм завершается, когда ни одно правило не выполняется (больше нет сочетаний).
Пример 1
Использование алгоритма Маркова для преобразований над строками.
Алфавит:
