Словесная форма записи алгоритмов

Раздел 4. Алгоритмизация И ПРОГРАММИРОВАНИЕ

Лекция 11. Главные ПОНЯТИЯ теории АЛГОРИТМов

1. Метод и его характеристики

2. Классы моделей алгоритмов

3. Понятие исполнителя метода

4. Структурный подход к разработке метода

5. Формы записи метода

литература:

[1], стр. 187 – 212.

Метод и его характеристики

Понятие метода

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

Задачка – неувязка, подлежащая решению.

Заглавие "метод Словесная форма записи алгоритмов" вышло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. Он определил правила записи натуральных чисел при помощи арабских цифр и правила действий над ними "столбиком". В XII веке эта книжка была переведена на латынь и получила обширное распространение в Европе Словесная форма записи алгоритмов.

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

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

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

Характеристики алгоритмов

К главным свойствам алгоритмов относятся последующие характеристики:

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

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

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

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

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

2. КЛАССЫ МОДЕЛЕЙ АЛГОРИТМОВ

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

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

Последовательность шагов определяется несколькими методами. 1-ый Словесная форма записи алгоритмов метод – суперпозиция, т.е. подстановка функции в функцию, а 2-ой – рекурсия, т.е. определение значения функции через «ранее» вычисленные значения этой же функции.

Функции, которые можно выстроить из целых чисел и арифметических операции при помощи суперпозиций и рекурсивных определений, именуются рекурсивными функциями. Пример рекурсивной функции – факториал функции.

2-ой класс моделей Словесная форма записи алгоритмов порожден последующей мыслью – однозначность метода и его техническое выполнение ЭВМ. Одной из таких машин явилась абстрактная машина Тьюринга. Она состоит из 3-х частей: ленты, головки и управляющего устройства. Лента нескончаема и разбита на ячейки. В каждой ячейке может быть записан только один знак (рис. 11.1).


Рис. 11.1. Машина Тьюринга

Отсутствие знака в Словесная форма записи алгоритмов ячейке обозначается особым «пустым» эмблемой « ». Головка всегда размещается над некой ячейкой ленты. Она может читать и писать знаки, стирать их и передвигаться повдоль ленты. Число вероятных знаков естественно, и образует алфавит машины А=íа1, …, аmý. Головка в каждый такт работы машины находится в одном из состояний. Огромное количество таких состояний Словесная форма записи алгоритмов естественно Q=íq1, …, qný и посреди их выделяют изначальное q и конечное q состояние.

Простый шаг машины Тьюринга состоит из последующих действий:

- головка считывает знак, записанный в ячейке, над которой она находится;

- считанный знак ак и текущее состояние головки qj совершенно точно определяют новое состояние qi, новый Словесная форма записи алгоритмов записываемый знак а1 и перемещение головки dp (которое может иметь значение на ячейку на лево, на ячейку на право, остаться на месте).

Устройство управления хранит и делает команды машины вида qj ak ® qi a1 dp.

Полное состояние машины Тьюринга именуется конфигурацией и содержит в себе состояние головки, ленты (слово, записанное на Словесная форма записи алгоритмов ней) и положение головки на ленте.

3-ий класс моделей алгоритмов очень близок к предшествующему, но не оперирует определенными машинными механизмами. К примеру, обычные методы Маркова.

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

1) Я®У

2) Л®У

3) С®М

4) В®Б

5) Р®Т

6) Т®Р!

7) О®Х

8) Н®А,

то используя правила:

1) проверить возможность подстановок в порядке возрастания их номеров, и если она вероятна (левая часть подстановки найдена в начальном слове), провести подстановку (заменив левую часть на правую Словесная форма записи алгоритмов);

2) если в примененной подстановке имеется знак «!», то преобразования прекращаются, а если нет, то текущее состояние становится начальным и весь процесс начинается поновой;

3) если ни одна подстановка не применима, то процесс преобразования завершен;

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

«слон Словесная форма записи алгоритмов» ® «суон» ® «муон» ® «мухн» ® «муха».

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

Возникновение четкого понятия метода позволило сконструировать алгоритмически неразрешимые препядствия, т.е. задачки, для решения которых нереально выстроить метод.

Задачка именуется алгоритмически неразрешимой , если не существует Словесная форма записи алгоритмов машины Тьюринга (либо рекурсивной функции, либо обычного метода Маркова), которая ее решает.

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

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

3. ПОНЯТИЕ ИСПОЛНИТЕЛЯ Метода

Исполнитель метода – это некая абстрактная либо настоящая (техно, био либо биотехническая) система, способная делать деяния, предписываемые методом, т.е. это субъект либо объект, реализующий метод.

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

Исполнитель не вникает в суть, а только исполняет метод, получая нужный итог, т.е. исполнитель действует формально – формальный исполнитель.

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

Каждый метод создается в расчете на определенного исполнителя. Деяния, которые может совершать исполнитель – допустимые деяния. Их совокупа – система команд исполнителя. Метод должен содержать только те деяния, которые допустимы для его формального исполнителя. Объекты, над которыми Словесная форма записи алгоритмов исполнитель может совершать деяния составляют среду формального исполнителя. (К примеру, в информатике универсальный формальный исполнитель – ЭВМ; среда исполнителя – числовые, символьные, логические величины и т.п.)

4. СТРУКТУРНЫЙ ПОДХОД К РАЗРАБОТКЕ Метода

Для того, чтоб метод выполнил свое назначение, его нужно строить по определенным правилам. В этом смысле необходимо гласить не о свойствах метода, а Словесная форма записи алгоритмов о правилах построения метода, либо о требованиях, предъявляемых к построению метода.

1-ое правило – при построении метода, сначала, нужно задать огромное количество объектов, с которыми будет работать метод. Формализованное (закодированное) представление этих объектов носит заглавие данных. Метод приступает к работе с неким набором данных, которые именуются входными, и в итоге собственной Словесная форма записи алгоритмов работы выдает данные, которые именуются выходными. Таким макаром, метод конвертирует входные данные в выходные.

Это правило позволяет сходу отделить методы от “способов” и “методов”. Пока мы не имеем формализованных входных данных, мы не можем выстроить метод.

2-ое правило – для работы метода требуется память. В памяти располагаются Словесная форма записи алгоритмов входные данные, с которыми метод начинает работать, промежные данные и выходные данные, которые являются результатом работы метода. Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит заглавие переменной. В теории алгоритмов размеры памяти не ограничиваются, т. е. считается, что мы можем предоставить методу хоть какой нужный для Словесная форма записи алгоритмов работы объем памяти.

Третье правило – дискретность. Метод строится из отдельных шагов (действий, операций, команд). Огромное количество шагов, из которых составлен метод, должно быть естественно.

4-ое правило – детерменированность. После каждого шага нужно указывать, какой шаг производится последующим, или давать команду остановки.

5-ое правило – сходимость (результативность). Метод должен завершать работу после конечного Словесная форма записи алгоритмов числа шагов. При всем этом нужно указать, что считать результатом работы метода.

Итак, метод – неопределяемое понятие теории алгоритмов. Метод каждому определенному набору входных данных ставит в соответствие некий набор выходных данных, т. е. вычисляет (реализует) функцию. При рассмотрении определенных вопросов в теории алгоритмов всегда имеется в виду Словесная форма записи алгоритмов какая-то определенная модель метода.

Формы записи метода

Метод, как последовательность шагов либо инструкций, может быть представлен в разных формах.

На практике более всераспространены последующие формы представления алгоритмов:

· словесная (запись на естественном языке);

· псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного Словесная форма записи алгоритмов языка, принятые математические обозначения и др.);

· графическая (изображения из графических знаков);

· программная (тексты на языках программирования).

Словесная форма записи алгоритмов

Словесный метод записи алгоритмов представляет собой описание поочередных шагов обработки данных. Метод задается в случайном изложении на естественном языке.

К примеру. Записать метод нахождения большего общего делителя (НОД) 2-ух Словесная форма записи алгоритмов натуральных чисел (метод Эвклида).

Метод может быть последующим:

· задать два числа;

· если числа равны, то взять хоть какое из их в качестве ответа и тормознуть, в неприятном случае продолжить выполнение метода;

· найти большее из чисел;

· поменять большее из чисел разностью большего и наименьшего из чисел;

· повторить метод Словесная форма записи алгоритмов с шага 2.

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

Словесный метод не получил широкого распространения из-за последующих недочетов:

· строго не формализуем;

· мучается многословностью записей Словесная форма записи алгоритмов;

· допускает неоднозначность толкования отдельных предписаний.

Псевдокод

Псевдокод представляет собой систему обозначений и правил, созданную для единообразной записи алгоритмов.

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

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

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

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


slozhnie-rechevie-zhanri-v-diskurse-yazikovoj-lichnosti-o-a-kazakova-dialektnaya-yazikovaya-lichnost-v-zhanrovom-aspekte.html
slozhnie-suzhdeniya-i-ih-istinnost.html
slozhnie-zaimstvovannie-imena-i-familii.html