birmaga.ru
добавить свой файл

1
Билет № 4


Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое исполнение алгоритма. Способы описания алгоритмов. Основные алгоритмиче­ские структуры и их реализация на языке программиро­вания. Оценка эффективности алгоритмов.

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

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

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

Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году Аланом Тью­рингом, Алоизом Чёрчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча были эквивалентными формализмами алгоритма. Сформулированные ими тезисы (Поста и Чёрча-Тьюринга) постулировали эквивалентность предложенных ими форма­льных систем и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство алгоритмически неразрешимых проблем.

Формализация понятия алгоритма.

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


Определение 1.

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

Несмотря на усилия исследователей, отсутствует одно ис­черпывающе строгое определение понятия «алгоритм», в теории алгоритмов были введены различные формальные определения алгоритма, и удивительным научным результа­том является доказательство эквивалентности этих форма­льных определений в смысле их равномощности.

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

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

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

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


  • Дискретность.
    Алгоритм состоит из последовательных команд, только выполнив одну команду, исполнитель может приступить к выполнению следующей. То есть структура алгоритма является дискретной (прерыв­ной).

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

  • Точность (определенность).

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


  • Понятность.
    Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм не рассчитан на при­нятие самостоятельных решений исполнителем, не пре­дусмотренных составителем алгоритма.

  • Универсальность (массовость).
    Алгоритм должен быть единым для всех допустимых исходных данных. Разра­ботка алгоритма — процесс творческий, но требующий значительных затрат времени и умственных усилий, поэтому желательно, чтобы он обеспечивал решение за­дач данного типа. Это" свойство не является обязатель­ным; не менее важными являются алгоритмы уникаль­ные, разработанные для решения одной задачи.


Алгоритм предполагает наличие исполнителя — челове­ка или технического устройства (автомат, робот, компью­тер), со строго определенным набором возможных команд. Совокупность команд, которые могут быть выполнены ис­полнителем, называются системой команд исполнителя (СКИ). Исполнитель может исполнять команды из СКИ и ничего более.
Автоматическое исполнение алгоритма

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

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

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


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

Представим этим способом алгоритм нахождения наи­большего общего делителя двух чисел м и n (алгоритм Ев­клида).

НОД (М - n, n) при м > n,
НОД (М, N) = \m при м = N,

НОД (n - М, М) при м < n.

Словесное описание алгоритма Евклида:


  1. Если м > n, то перейти к п. 4, иначе перейти к п. 2. .

  2. Если м < n, то перейти к п. 5, иначе перейти к п. 3.

  3. Считать, что НОД(М, n) = м. Конец.

  1. Из м вычесть N и впредь считать, что эта разность яв­ляется значением м. Возвратиться к п. 1.

  2. Из N вычесть м и впредь считать, что эта разность яв­ляется значением N. Возвратиться к п. 1.

В алгоритме Евклида заметим интересный прием: изме­няя значение величины, мы сохраняем за ней ее исходное имя.

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

начало нц пока M?tN если M>N


то M:=M-N иначе N:=N-M все

кц

Z :=М конец

Всё чаще словесное описание и запись на алгоритмиче­ском языке сводят к одному способу — словесному.

Описание в графической форме в виде блок-схемы.

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

Основные блоки, используемые при графической форме записи алгоритмов:



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

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

Алгоритм может быть реализован в виде комбинации трех базовых алгоритмических конструкций: линейной, разветвленной, циклической.

Алгоритм линейной структуры — алгоритм, в котором предписываемые действия выполняются последовательно: Оператор 1 — Оператор2 — ... — Операторе. Такой порядок выполнения действий называется естественным.

Алгоритм разветвленной структуры — алгоритм, в кото­ром предусмотрено разветвление выполняемой последователь­ности действий в зависимости от результата проверки како­го-то условия. Условие — это некоторое логическое выраже­ние. Если условие (логическое выражение) принимает значение «истина», то выполняется Оператор 1, в противном случае — значение «ложь» — выполняется Оператор2. Опера-тор1 и Оператор2 могут представлять группу операторов, а так­же могут быть условными операторами. В случае отсутствия Оператора2 получаем конструкцию с неполным ветвлением.