Алгоритм, свойства алгоритма, его исполнители. Способы описания алгоритмов

 

 

 

 

Компьютерная  лингвистика

Контрольная работа на тему:

«Алгоритм, свойства алгоритма, его исполнители.

Способы описания алгоритмов»

 

 

 

 

                                                                        

 

 

 

 

 

 

 

 

 

 

1. Понятие алгоритма
2. Свойства алгоритмов
3. Автоматическое исполнение алгоритма
4. Способы описания алгоритмов
5. Заключение

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Понятие алгоритма

      Исторический обзор.  Первым дошедшим до нас алгоритмом  в его интуитивном понимании  — конечной последовательности  элементарных действии, решающих  поставленную задачу, — считается  предложенный Евклидом в III веке  до нашей эры алгоритм нахождения  наибольшего общего де­лителя  двух чисел (алгоритм Евклида). Вплоть до начала XX века само  слово «алгоритм» употреблялось  в устойчивом сочетании «алгоритм  Евклида». Для описания пошагового  решения других математических  задач использовалось слово «метод».

     Слово «алгоритм», «algorithm» происходит от имени выдающегося ученого IX века Мухаммеда ибн Муса ал-Хорезми (в переводе с арабского Мухаммед, сын Мусы из Хорезма). По латинскому переводу его труда (XII век) Западная Европа познакомилась с десятичной позиционной системой счисления и правилами (algorismi) выполнения в ней арифметических действий.

      Формализация понятия  алгоритма. Во всех сферах своей  деятельности, в частности, в сфере  обработки информации, человек сталкивается  с различными методами решения  задач. Они определяют порядок  выполнения действий для получения  желаемого результата — мы  можем трактовать это как первоначальное  или интуитивное определение  алгоритма. Исполнителем алгоритма может быть человек, группа людей, робот, станок, компьютер, язык программирования и т.д. Важнейшим свойством, характеризующим любого из этих исполнителей, является то, что исполнитель умеет выполнять некоторые команды. Так, исполнитель-человек умеет выполнять такие команды как «встать», «сесть», «включить компьютер» и т.д., а исполнитель-язык программирования Бейсик - команды PRINT, END, LIST и другие аналогичные. Вся совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя (СКИ). Одно из принципиальных обстоятельств состоит в том, что исполнитель не вникает в смысл того, что он делает, но получает необходимый результат. В таком случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции.

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

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

 

Алгоритмы являются объектом систематического исследования пограничной между  математикой и информатикой научной  дисциплины, примыкающей к математической логике - теории алгоритмов.

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

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

    Варианты словесного  определения алгоритма, принадлежащие  российским ученым-математикам А.  Н. Колмогорову и А. А. Маркову:

    Определение 2 (Колмогоров). Алгоритм — это всякая система  вычислений, выполняемых по строго  определенным правилам, которая  после какого-либо числа шагов  заведомо приводит к решению  поставленной задачи.

    Определение 3 (Марков). Алгоритм  — это точное предписание,  определяющее вычислительный процесс,  идущий от варьируемых исходных  данных к искомому результату.

Свойства алгоритмов

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

1. Одно из первых требований, которое предъявляется к алгоритму,  состоит в том, что описываемый  процесс должен быть разбит  на последовательность отдельных  шагов. Возникающая в результате  такого разбиения запись представляет  собой упорядоченную совокупность  четко разделенных друг от  друга предписаний (директив, команд, операторов), образующих прерывную  (или, как говорят, дискретную) структуру алгоритма. Только выполнив  требования одного предписания,  можно приступить к выполнению  следующего. Дискретная структура  алгоритмической записи может.  Например, подчеркиваться сквозной  нумерацией отдельных команд  алгоритма, хотя это требование  не является обязательным. Рассмотренное  свойство алгоритмов называют  дискретностью. 

2. Используемые на практике алгоритмы  составляются с ориентацией на  определенного исполнителя. Чтобы  составить для него алгоритм, нужно знать, какие команды  этот исполнитель может понять  и исполнить, а какие - не  может. Мы знаем, что у каждого  исполнителя имеется своя система  команд. Очевидно, составляя запись  алгоритма для определенного  исполнителя, можно использовать  лишь те команды, которые имеются  в его СКИ. Это свойство алгоритмов  будем называть понятностью. 

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

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

Отмеченное свойства алгоритмов называют определенностью или детерминированностью.

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

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

Автоматическое исполнение алгоритма

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

    Примером исполнителя,  автоматически выполняющего различные  алгоритмы, является компьютер.  Рассмотрим запись на жесткий  диск компьютера телевизионной  передачи с помощью ТВ-тюнера. Указав в расписании время  начала и окончания записи, поставив  «флажок» возле позиции «Выключить компьютер после записи», пользователь может быть уверен, что передача будет записана и компьютер будет выключен. Всю заданную работу выполнит компьютер по разработанному ранее алгоритму, не внося никаких изменений (другая передача, другое время, невыключение компьютера).

Способы описания алгоритмов

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

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

Алгоритм, записанный на алгоритмическом  языке, должен иметь название. Название желательно выбирать так, чтобы было ясно, решение какой задачи описывает  данный алгоритм. Для выделения названия алгоритма перед ним записывают служебное слово АЛГ (АЛГоритм). За названием алгоритма (обычно с новой строки) записывают его команды. Для указания начала и конца алгоритма его команды заключают в пару служебных слов НАЧ (НАЧало) и КОН (КОНец). Команды записывают последовательно. При построении новых алгоритмов могут использоваться алгоритмы, составленные ранее. Алгоритмы, целиком используемые в составе других алгоритмов, называют вспомогательными алгоритмами. Вспомогательным может оказаться любой алгоритм из числа ранее составленных. Не исключается также, что вспомогательным в определенной ситуации может оказаться алгоритм, сам содержащий ссылку на вспомогательные алгоритмы.

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

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

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