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

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

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

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

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

Свойства:

1.однозначность – четкое предписание что и как делать в каждой конкретной ситуации. Будучи понятным, алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно 2.универсальность – применяемость данного алгоритма к решению любой задачи данного типа 3.результативность – отсутствие зацикливаний. Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определенный результат. Вывод о том, что решения не существует - тоже результат. 4. массовость. Наиболее распространены алгоритмы, обеспечивающие решение не одной конкретной задачи, а некоторого класса задач данного типа. 5.дискретность – алгоритм должен быть разбит на отдельные достаточно простые действия. 7.понятность. Используемые на практике алгоритмы составляются с ориентацией на определенного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие - не может.

Способы записи:

1.словесная – ориентирована на исполнителя человека. Команды записываются на обычном языке. «+» – понятность. « - » - неоднозначность, избыточность, отсутствие наглядности связей.

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

Блок-схема - это ориентированный граф, указывающий порядок исполнения команд алгоритма; вершины такого графа могут быть одного из трех типов

На рис. изображены «функциональная» (a) вершина (имеющая один вход и один выход); «предикатная» (б) вершина, имеющая один вход и два выхода (в этом случае функция Р передает управление по одной из ветвей в зависимости от значения Р (Т, т.е. true, означает «истина», F, т.е. false - «ложь»); «объединяющая» (в) вершина (вершина «слияния»), обеспечивающая передачу управления от одного из двух входов к выходу.

Из данных элементарных блок-схем можно построить четыре блок-схемы (рис. 2), имеющих особое значение для практики алгоритмизации.

На рис. изображены следующие блок-схемы: а - композиция, или следование; б - альтернатива, или развилка, в и г - блок-схемы, каждую из которых называют итерацией, или циклом (с предусловием (в), с постусловием (г)). S1 и S2 представляют собой в общем случае некоторые серии команд для соответствующего исполнителя, В - это условие, в зависимости от истинности (Т) или ложности (F) которого управление передаётся по одной из двух ветвей. Можно доказать, что для составления любого алгоритма достаточно представленных выше четырех блок-схем, если пользоваться их последовательностями и/или суперпозициями.

На практике при составлении блок-схем оказывается удобным использовать и другие графические знаки

3.псевдокоды – занимают промежуточное место между естественным и формальным языком.

Достаточно распространенным способом представления алгоритма является его запись на алгоритмическом языке, представляющем в общем случае систему обозначений и правил для единообразной и точной записи алгоритмов и исполнения их. Основу этого словаря составляют слова, употребляемые для записи команд, входящих в систему команд исполнителя того или иного алгоритма. Такие команды называют простыми командами. В алгоритмическом языке используют слова, смысл и способ употребления которых задан раз и навсегда. Эти слова называют служебными. Использование служебных слов делает запись алгоритма более наглядной, а форму представления различных алгоритмов - единообразной. Используют некоторые служебные слова, которые подчеркиваются. АЛГ – название алгоритма; НАЧ; …; КОН; ДЛЯ i ОТ 1 ДО 100 ВЫП; ЕСЛИ ТО ИНАЧЕ; Нц Кц 4.языки программирования.На практике основной исполнитель алгоритма – ЭВМ, поэтому запись алгоритма должна быть абсолютно точна, т.е. язык должен быть формализован. Его наз языком программирования, а запись алгоритма на таком языке – программой.

По синтаксису можно разделить на классы:

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

процедурно – ориентированные – имеется возможность описания прог как совокупности процедур подпрограмм.

проблемно – ориентированные – решают определенный класс задач (Prolog).

Классификация алгоритмов:

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

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

двумя альтернативами.Выполняется проверка, а затем выбирается один из путей. Эта структура называется также «ЕСЛИ - ТО - ИНАЧЕ», или «развилка». Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.

3.циклические – для многократно повторяемых действий используют специальную конструкцию – цикл. Команды цикла содержат условия для определения количества повторов. Существует три типа циклов:

счетчик (с параметром) – когда заранее определено количество повторов.

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

с постусловием – условие проверяется после действий в теле цикла, и если это условие выполняется, то происходит выход из цикла.

Формализация алгоритма, т.е. строгое его описание. Подходы к формализации понятия «алгоритм»:1) теория конечных и бесконечных автоматов; 2) теория вычислимых (рекурсивных) ф-й; 3) -исчисление Черча. Все эти подходы оказались эквивалентными. Главная цель формализации-подойти к решению проблемы алорит-ой разрешимости различ.мат.задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи.Рассмотрим формализацию в теории автоматов на примере машин Поста и Тьюринга.

Машина Поста. Абстрактные машины Поста и Тьюринга были предложены не зависимо друг от друга в 1936г.америк.мат-ом Эмилем Постом и англ.мат-ом Алланом Тьюрингом. Эти машины универсал.исполнители,полностью детерминированные, позвол.вводить нач.данные и после вып-я программ читать рез-т.

Машина Поста предст-ет собой беск.ленту, раздел.на одинак.клетки, каждая из кот.м.б.либо пустой либо заполненной меткой «V», и головки, кот. Может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если ее там ранее не было, стирать если была, проверять наличие в клетки метки. Команда машины Поста n K m, n порядковый номер команды, K действие, вып-е головкой, m номер след команды.  6 команд машины Поста: 1)Движение головки на 1 клетку вправо n  m, 2) влево n  m,3) нанесение метки, над кот.нах-ся головка n М m, 4) стирание n С m, 5) проверка наличия метки в клетке, над кот.нах-ся головка, если метка отсутствует, управление передается команде м1, иначе м2,6) остановка машины n Стоп n . Программой для машины Поста будем называть непустой список команд, такой что:1)на n месте команда с номером n,2) номер m каждой команды совпадает с номером к-либо команды из списка.

Рассмотрим представление чисел на ленте машины Поста. Число к представляется на ленте идущими подряд к+1 метками (одна метка означает число 0). Между двумя числами делается интервал как минимум из одной пустой секции на ленте. Н-р: запись чисел 2 и 3 на ленте:

v

v

v

v

v

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

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

Машина Тьюринга.

МТ есть мат.машина, а не физич..Это такой же мат.обьект как ф-я, производная,группа. И так же как др.мат.понятия МТ моделирует некие реал.процессы. МТ удобно представлять в виде автомат.раб.устройства. Она состоит из ленты, разбитой на ячейки, потенциально беск.в обе стороны. В каждую ячейку м.б.вписан только 1 символ из конечного мн-во символов – алфовит МТ А={a₀,a₁,…,a_T}. Имеется упр.головка МТ способная передвигаться по ленте вправо и влево, в результате работы 1 такта на 1 ячейку.В каждый дискрет.момент времени устройство, находясь в нек.состоянии обозревает содержимое одной ячейки ленты, протягиваемой через устройство и делает 1 шаг, заключ.в том,что устр-во переходит в новое состояние, изменяет содержимое обозреваемой ячейки и переходит к обозреванию след.ячейки. Шаг МТ осущ-ся на основе предписанной команды. Совокупность всех команд предст-ет программу МТ. МТ располагает конеч.числом знаков, символов, букв, образ.внеш.алфавит - А={_a0,_a1,…,_aT}. В каждую ячейку обозреваемой ленты в каждый дискрет.момент времени может быть записан 1 символ из А. Удобно считать, что среди букв внеш.алфавита имеется «пустая буква», и она записана в пуст.ячейку ленты. В каждый момент времени МТ способна находится в одном состоянии из конечного числа внут.состояний, совокупность кот.наз-ся алфавитом внут.состояний-q₀,q₁,…,q_s. Среди состояний выд-ся 2 – начальное _q1, заключительное – состояние остановки _q0. Работа МТ опред-ся программой. Программа состоит из команд, каждая команда представляет выражение одного из след видов: 1)q_ia_jq_sa_t, 2) _qi_aj_qs_atП , 3) _qi_aj_qs_at Л.

Команда 1:находясь в состоянии _qi и обозревая ячейку с символом _aj и напечатать в данной ячейке символ _at . Команда 2(3): находясь в состоянии _qi и обозревая ячейку с символом _aj и напечатать в данной ячейке символ a_t и сдвинуться на 1 ячейку вправо(влево). Под к-конфигурацией понимается изображение ленты с информацией сложившейся на ней к началу к-такта с указанием того, какая ячейка обозревается в этот такт и в каком состоянии нах-ся машина. Будем говорить, что непустое слово L в алфавите А воспринимается машиной в стандарт.положении, если это слово записано в послед.ячейках ленты, все другие ячейки пусты и машина обозревает крайнюю справа ячейку из тех, в которых записано слово L. Стандартное положение назовенм начальным , если МТ воспринимает слово в стандартном положении нах-ся в нач.состоянии _q1 .

Пример: Дана МТ с внеш.алфавитом А={_a0,1}, внут.алфавитом – Q={_q0,_q1} и программой в виде системы команд: 1)q₁a₀q₀1, 2) q₁1q₁1 П. Определить в какое слово МТ переработает слово 1_a0111, если обозревается ячейка 4 слева.

	1	a0	1	1	a0	a0	1
	1	a0	1	1	a0	a0	1
	1	a0	1	1	1	a0	1