Фундаментальные алгоритмы/Понятие алгоритма

Что такое алгоритм и зачем он нужен

Многое в нашей жизни подчинено правилам и инструкциям. Часть из них для нас весьма очевидна, что выполняется неосознанно. Алгоритм и все что с ним связано развивался из потребностей математики. Сейчас мы рассмотрим какие задачи математики тесно связаны с алгоритмикой. Надеюсь, что читатель или учится в школе или учился, а потому помнит вычисление корней квадратного уравнения. Для упрощения изложения мы будем рассматривать только нахождение корней, выраженных лишь действительными числами(на всякий случай напомню что это например: -1,0,1,2 и т.д.,а так же числа как: 0.5,2.5 и т.д.).

Итак мы вычисляем корни уравнения вида $ax^{2}+bx+c=0$ , где $a\neq 0$ .(1)

Опишем алгоритм словесно:
Алгоритм решения квадратного уравнения

Шаг 1:взять коэффициенты a,b,c из (1 )

Шаг 2: вычислить дискриминант(D) выражения(1) по формуле: $D=b^{2}-4ac$

Шаг 3:Если D>0 то: $x_{1,2}={\frac {-b\pm {\sqrt {D}}}{2a}};$
Если D=0 то: $x={\frac {-b}{2a}};$
Если D<0 то: действительных корней нет

Вот он алгоритм и никакой мистики. Но мы рассмотрим еще один:преобразование неправильной дроби.

Из математики нам известно,что правильная дробь эта та где числитель меньше знаменателя, а неправильная там где наоборот. Если это записать математически то получится: $x={\frac {a}{b}};$ ,где $a<b;$ Так вот наш алгоритм должен преобразовать неправильную дробь в правильную. Опишем его как всегда словесно:(при этом под словом записать понимается записать результат на бумагу. Условимся так же что числитель обозначим буквой "a",а буквой "b" знаменатель)
Алгоритм преобразования правильной дроби в неправильную

Шаг 1: Проверить что a>b, если нет то дробь правильная, останавливаемся иначе переход к шагу 2

Шаг 2:Разделить a на b.

Шаг 3:записать как целую часть частное от деление.

Шаг 4:Если остаток от деления неравен 0, то:
Записать как числитель новой дроби остаток от деления a на b. Записать знаменателем новой дроби знаменатель исходной дроби(b ).
иначе:завершить преобразование
шаг 5:Завершить выполнение

Вот и еще один алгоритм мы с вами увидели.Ну и наконец пример еще одного: Довольно часто возникает задача проверки числа на четность. Четное число делится на 2 без остатка. Напишем алгоритм, который решает поставленную задачу:
Алгоритм проверки на четность

Шаг 1: взять число
Шаг 2: Проверить что число больше нуля
Шаг 3: Если число равно 0 прекратить выполнение
Шаг 4:Разделить число на 2
шаг 5: Если остаток равен 0, то числа четные, иначе нет.

Мы с вами рассмотрели 3 алгоритма теперь пора уже собственно ответить на вопрос, а что это?

Определим алгоритм как последовательность четких инструкций приводящих к выполнению поставленной задачи. Однако этого недостаточно у него есть еще 5 свойств, которые позволяют алгоритм назвать алгоритмом:

Конечность Это означает что алгоритм должен приводить к решению поставленной задачи за некий конечный промежуток времени Обратите внимание что все наши алгоритмы обязательно завершатся
Однозначность. Все инструкции в этих алгоритмах трактуются однозначно и как я надеюсь разночтений возникать не должно. Если же вам что то неизвестно из употребленных понятий, то можно найти их общепринятые определение
Вход Любой алгоритм должен иметь входные данные, то есть те данные к которым он будет применен.
Выход Любой алгоритм должен выдавать какие то данные как результат
Универсальность Алгоритм должен работать для любых данных, которые соответствуют типу алгоритма. Например: наш алгоритм решения квадратного уравнения должен решать свою задачу при любых параметрах, относящихся к множеству действительных чисел. Говоря проще: если разработчик заявил что это численный алгоритм работает со всеми натуральными числами, то он должен работать с любыми числами от $-\infty$ до $+\infty .$ ,хоть с 0, хоть с 1000000 . В то же время глупо ждать от численного алгоритма корректной работы с символами
Эффективность Люди разрабатывают алгоритмы для решения конкретных задач и конечно же хотят найти наиболее оптимальные методы ее решения.Поэтому алгоритм можно оценить с точки зрения его эффективности а как мы еще поговорим в этой главе.

Итак мы уяснили для себя что такое алгоритм. Теперь рассмотрим пару примеров вобщем то внешне похожих на алгоритмы.

"Алгоритм" изучения науки об алгоритмах:

Найти хорошую книгу по алгоритмам
Внимательно ее читать и делать все упражнения
Не лениться

Читателю предоставляется возможность ответить на вопрос почему это вовсе не алгоритм самостоятельно И еще один:

"Алгоритм" медитации:

Найти тихое уединенное место
Удобно расположиться
Закрыть глаза
Избавиться от мыслей
Находится в таком состоянии сколько сможете и захотите

Аналогично предлагается читателю показать, что это псевдоалгоритм.

Представление алгоритмов для ЭВМ

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

Однозначностью каждого своего элемента
Строгой стандартизованностью

Такие формы записи называют языками программирования. Их великое множество: C,Pascal,C++,Perl,Python,ASP,PHP,Prolog,Рефал,Lisp,assembler и такой экзотичный Forth Но на самом деле языков крайне много, несколько тысяч. Так как языки программирования, несмотря на их жесткую формализованность, все же являются выражением предпочтений их автора, его взгляда на предметную область, то всегда будут появляться новые. Мы же рассмотрим более частный вопрос, но для нас более важный: как мы будем представлять алгоритмы. У нас есть выбор: использовать какой либо существующий язык программирования, пвседокод или придумывать свой. Третий путь отбросим сразу автор этого курса отбросил, т.к. явно не Дональд Кнут:) Псевдокод меня то же неслишком устраивает, все ж хочется чтобы можно было "пощупать" результаты наших размышлений. Итак остается для нас путь под номером 1. Какой же язык мы выберем? У нас их будет аж три: python,C,Pascal. Но не пугайтесь вам дастотачно будет знать и одного: для быстрой иллюстрации моих утверждений в наиболее приближенной к обычным записям форме будет применяться python. Тем более он не требует никаких вещей типа компиляции линкования и т.д. Он сразу начнет все выполнять, так как интерпретируемый.Ну а окончательная реализация будет представлена на двух языках программирования для удобства всех читателей: на С и Pascal. Что ж этот вопрос мы с вами уяснили и переходим к следующему пункту: основные алгоритмические структуры.

Быстрый старт в Python

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

Вполне возможно что читатель уже с ними хорошо знаком и все же позволю себе их вам напомнить.

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

Python:

if a>b:
 print "A great then b "
else:
 print "A less then b "

Pascal:

if a>b then
 writeln("A greate then B")
else
writeln( "A less then B")

C:

if (a>b)
 printf( "A great then b ");
else
 printf ("A less then b ");

Как видим идея этого оператора в том, чтобы выбрать на основе проверки некоего условия путь работы программы/алгоритма. Такого рода проверка называется логическим вычислением. Оно подчиняется законам булевой алгебры, которые мы рассмотрим чуть позже. Результатом такого вычисления может быть либо: истина(true) либо ложь(false) Этот оператор использует результат логических вычислений, если условие соблюдено, то выбирается та ветка которая идет сразу после if (то есть будет выведено "A great then b "), а если нет, то "A less then b ". Кстати не верьте мне на слово, а запустите Python и введите следующий скрипт(так называются программы на любом интерпритируемом языке): Python:

a=7
b=6
if a>b:
 print "A great then b "
else:
 print "A less then b "

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

Оператор множественного выбора

Этот оператор позволяет реализовать нам выбор развития хода программы не из двух вариантов, а из многих.

a=11
if a==10:
 print "A= ",a
elif a==11:
  print "A(second branch) =  ",a
elif a==12:
 print "A(thrid branch)= ",a

Выполните этот скрипт с различными значениями переменной a и посмотрите результат.

В С оператор множественного выбора выглядит так:

int a;
switch(a)
  {
   case 10:
      {
       printf("A(first branch) =%d",a);
       break;
      }
   case 12:
      {
       printf("A(second branch) =%d",b);
       break;
      } 
    default:
       {
          printf("A(default branch) = %d",c);
        }

  }

Циклы:

Цикл-- это конструкция языка/алгоритма, которая позволяет выполнить заданные действия многократно

Циклы с условием:

Python:

a=1
while a<=11:
 print a 
 a=a+1

Pascal:

a:=1;
while a<=11 do 
begin
writeln( a);
a:=a+1;
end;

C:

a=1;
while (a<=11){ 
writeln( a);
a=a+1;
}

Логика выполнения этой конструкции такова: Сначала проверяется на истинность условие после слова while(в нашем случае что переменная a должна быть или меньше, или равна 11) Если условие истинно, то переходим к выполнение цикла, то есть то что после слова while. Печатаем значение переменной a. После выполнения тела цикла, то есть того что мы печатали после cлова while, программа снова проверит условие в случае истинности снова будет выполнен цикл, а если оно ложно то нет и будет выполнена следующая инструкция после тела цикла. Теперь давайте подумаем зачем написано a=a+1? Возможно вы уже догадались, а может и нет, если нет, то: цикл проверяет условие на истинность. От того что мы печатаем значение переменной само ее значение никак не изменится, а значит условие всегда будет истинным и цикл не остановится никогда. Вы вынуждены будете отключить саму программу для прекращения цикла.То есть вот схема выполнения:

Проверить условие цикла
Если истинно:

Выполнить тело цикла изменить значение переменной, используемой для проверки условия

вернутся к шагу 1

Иначе:

  Выйти из цикла

Цикл со счетчиком:

Очень часто перед нами возникает задача выполнения цикла известное число раз и для удобства записи был придуман цикл for. Алгоритм его выполнения:

присвоить начальное значение переменной, по которой производится проверка условия(счетчику)
Выполнить действия в теле цикла
Уменьшить или увеличить значение счетчика. Все зависит от условий применения цикла

Язык python немного иначе трактует цикл for. В нем for служит для прохода программы по элементам структур данных типа массив, список и т.д. Python:

a=[] #сформируем список
for i in a:#переменной i последовательно присваиваются все элементы списка 
 print  a

Pascal:

for a:=1 to 12 do
begin
writeln('Iteration#',a);
writeln("go to the next iteration");
end;

С:

for (int i=0;i<=12;i++)
{
printf('Iteration#%d',a);
printf("go to the next iteration");
}

Слово итерация в данном случае обозначает выполнение тела цикла.Важный момент: любой цикл for может быть заменен while циклом, но не наоборот. Если у вас есть сомнения какой из циклов применять, то запомните простое правило: если неизвестно заранее сколько раз будет выполнен цикл, то применяйте while цикл, а если заранее известно сколько раз выполнится цикл то for.На этом закончим обзор основных алгоритмических структур.

Примеры записи алгоритмов

Давайте запишем те самые алгоритмы в словесной форме, в форму понятную для ЭВМ. Итак:

Программа вычисления корней квадратного уравнения:

# -*- coding: utf-8 -*-
from  math import * #сообщаем python где найти функцию извлечения корня   
a=input("Введите коэффициент а")#запрос к пользователю о вводе значения коэфф. a
b=input("Введите коэффициент b")#запрос к пользователю о вводе значения коэфф. b
c=input("Введите коэффициент c")#запрос к пользователю о вводе значения коэфф. c
d=b**2-4*a*c #вычислим дискрминант 
if d>0: #если дискриминант больше нуля...
    x=(-b+sqrt(d))/2*a
    x1=(-b-sqrt(d))/2*a
    print "Первый корень=",x,"Второй=",x1
elif d==0: #равен 0
    x=-b/2*a
    print "x:",x
elif d<0:#меньше 0
 print "Это уравнение не имеет действительных корней"

Алгоритм преобразования неправильной дроби:

# -*- coding: utf-8 -*-

a=input("Введите числитель")
b=input("Введите знаменатель")
if a<b:
    print "Вы ввели правильную дробь"
    print a,'/',b
elif a%b==0: print a/b
elif a>b: print a/b ,a%b,'/',b

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

# -*- coding: utf-8 -*-

a=input("Введите число")
if a%2==0:
    print "Вы ввели четное число"
else:
      print "Вы ввели нечетное число"

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

-*- coding: utf-8 -*- Но к алгоритмам она не имеет никакого отношения, она нужна затем чтобы Python нормально воспринял кириллические буквы, что обеспечивает кодировка UTF-8

Некоторые важные теоретические вопросы

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

Тезис Чёрча-Тьюринга

С одной стороны наука об алгоритмах очень точная наука и опирается на довольно точный математический аппарат, но с другой само понятие алгоритма не слишком математично. Вот как раз и поговорим о том как же его пытались определить.Одним из определений алгоритма является т.н. Тезис Чёчра-Тьюринга. Тезис Чёрча-Тьюринга:Любой алгоритм в интуитивном понятии может быть выполнен машиной Тьюринга. И здесь у вас может возникнуть вопрос: что такое машина Тьюринга?Ее описание мы дадим в отдельном пункте, а пока определимся так: это абстрактная ЭВМ с основными элементами характерными для обычного компьютера. Так вот машина Тьюринга как понятие позволила делать обобщенный анализ алгоритмов. При таком анализе мы можем сосредоточится на самих алгоритмах и оперировать их чистыми свойствами, а не тем как ведет себя некий алгоритм на данной машине,с ее аппаратными особенностями. Более того фактически тезис Чёчра-Тьюринга кроме того ввел следующий постулат: любой алгоритм который может быть выполнен на физическом устройстве можно выполнить и на машине Тьюринга, а от себя мы продолжим утверждение: а значит он может быть проанализирован. Этот же тезис позволил поставить проблему алгоритмической неразрешимости многих вопрос не только информатики, но даже алгебры и других математических дисциплин.Кстати основная проблема алгоритмической неразрешимости заключается в том, что для некоторого класса задач не может быть найдено алгоритма, обладающего свойством универсальности или как его еще называют: массовости.Одним из примеров такой проблемы является проблема останова алгоритма. Она формулируется так: требуется найти универсальный алгоритм, который бы отвечал на вопрос: остановится ли заданный алгоритм выполняемый на произвольной машине Тьюринга. Было доказано что это алгоритмически не разрешимая задача. Предлагаю вам, уважаемый читатель, самостоятельно доказать алгоритмическую не разрешимость этой проблемы. Если же у вас не получилось или вам интересно, то приведу свое доказательство: Итак допустим мы имеем некий алгоритм. С нас спрашивают найти некий метод доказательства конечности или бесконечности выполнения произвольного алгоритма.

Фактически нас просят разработать еще один алгоритм. Однако перед нами сразу возникнет дилемма: как доказать конечность выполнения самого проверяющего алгоритма? Ведь это алгоритм и он сам должен обладать свойствами: конечности, универсальности и т.д. Ни то ни другое мы не можем получить, т.к. фактически мы пытаемся один алгоритм всего лишь противопоставить другому, но при этом не имеем возможности ответить на вопрос о конечности выполнения обоих.А значит он как минимум не удовлетворяет одному из свойств обязательных для алгоритма.
Какой важный вывод мы должны сделать из всего описанного? Не все задачи имеют алгоритмическое решение!

Теперь рассмотрим для полноты картины различные модели вычислений

Модели вычислений

Здесь мы рассмотрим различные виды абстрактных вычислительных машин, которые сыграли важную роль в развитии теории алгоритмов. Здесь требуются некоторые пояснения: сама теория алгоритмов родилась среди математиков и хотя люди ее развивавшие понимали что вычислительная техника это очень перспективно и будет прикладной областью теории, но самой вычислительной техники, которая была бы способна выполнять произвольные алгоритмы не было. Например Черч и Тьюринг писали работы по проблемам вычислимости еще в 30-ые годы, а первые модели компьютеров, которые могли бы выполнять алгоритмы появились лишь в 40-ые и 50-ые годы. Однако их появление не решает проблемы. Даже сейчас когда стандартизация аппаратных частей компьютеров позволяет пользоваться аппаратурой разных производителей и т.д. мы можем столкнутся с тем что, например, на одном компьютере процессор мощнеее ем у другого и т.д. Тогда встает вопрос: а что мы измерим при анализе быстродействия алгоритма:скорость машины на примере алгоритма или все же скорость алгоритма. Но даже если каким-то волшебным образом мы учтем вклад аппаратной части машины и отделим его от алгоритмического, то увидим иную проблему: это НАША конфигурация машины, а программы выполняются на совершенно разных системах: от тостеров и до суперкомпьютеров, считающих модели Большого взрыва. Это что ж нам так тестировать на всех возможных моделях аппаратуры?

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

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

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

Вот ее описание из соотв. статьи Википедии:

В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано. Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные. Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма. Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

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

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <q_i, a_j> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Пример машины Тьюринга:

Приведём пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:

Набор правил Набор правил

q₀*→q₀R q₄a→q₄aR

q₀1→q₀R q₄=→q₄=R

q₀×→q₁×R q₄1→q₄1R

q₁1→q₂aR q₄*→q₅1R

q₂1→q₂1L q₅*→q₂*L

q₂a→q₂aL q₆a→q₆1R

q₂=→q₂=L q₆×→q₇×R

q₂×→q₃×L q₇a→q₇aR

q₃1 → q₄aR q₇1→q₂aR

q₃a→q₃aL q₇=→q₈=L

q₃*→q₆*R q₈a→q₈1L

q₄×→q₄×R q₈×→q₉H

Умножим с помощью МТ 3 на 2 в единичной системе:
Протокол|center
В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).

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

Машина Поста

Машина Тьюринга не являлся единственной моделью вычислительного устройства, которая применялась и применяется в теории алгоритмов.Упрощенную модель абстрактной вычислительной машины предложил математик и логик Эмиль Пост. Опять же процитируем Викистатью:

МП состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или уничтожить символ в том месте, где она стоит. Работа МП определяется программой, состоящей из конечного числа строк. Всего команд шесть:

N. → J сдвиг вправо
N. ← J сдвиг влево
N. 1 J запись метки
N. 0 J удаление метки
N. ? J₁, J₀ если в ячейке нет метки, то перейти к j₁ строке программы, иначе перейти к j₂ строке программы.
N. Stop остановка

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

работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

работа может закончиться командой Stop;

работа никогда не закончится.

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