«аочное дистанционное образование с получением государственного диплома через Internet










ѕолучить информацию о поступлении
 
√лавна€ Ќовости  арта сайта ‘отоальбом √остева€ книга  онтакты

“еоретический материал
ѕрактический материал
ќбъект информатики
ѕредметна€ область информатики как науки
÷ель и задачи курса Ђинформатикаї
»стори€ развити€ информатики

 

ѕон€ти€ теории алгоритмов

“еори€ алгоритмов Ч раздел математики, изучающий общие свойства алгоритмов. ѕон€тие Ђалгоритмї сформировалось в мате­матике в 20-х годах XX в. Ќачалом систематической разработки теории алгоритмов можно считать 1936 г. и св€зывают это начало с публикацией работы ј.ј. „ерча.

ѕод алгоритмом всегда (и до возникновени€ строгой теории) понималась процедура, котора€ позвол€ла путем выполнени€ после­довательности элементарных шагов получать однозначный результат (независ€щий от того, кто именно выполн€л эти шаги) или за конечное число шагов прийти к выводу о том, что решени€ не существует.

 онечно же это нестрогое определение пон€ти€ алгоритма и именно попытки сформулировать такое пон€тие привели к возник­новению теории алгоритмов. ѕричиной развити€ этой теории были внутренние проблемы математики и лишь с возникновением и развитием вычислительной техники и смежных наук вы€снилось, что в основе этих наук должна лежать теори€ алгоритмов. “ак стало очевидным прикладное значение новой науки.

¬ основе формализации пон€ти€ Ђалгоритмї лежит иде€ построени€ алгоритмической модели. —оставл€ющими такой модели должны быть конкретный набор элементарных шагов, способы определени€ следующего шага и т.д. ќт модели также требуетс€ простота и универсальность. “ребование простоты важно дл€ того, чтобы выделить действительно необходимые элементы и свойства алгоритма и облегчить доказательства общих утверждений об свойствах. ”ниверсальность необходима дл€ того, чтобы моде позвол€ла описать любой алгоритм.

–езультатами теоретических исследований €вились три основных класса арифметических моделей.

ѕервый класс моделей основан на арифметизации алгоритмов. ѕредполагаетс€, что любые данные можно закодировать числами, как следствие - вс€кое их преобразование становитс€ в этом случае арифметическим вычислением, алгоритмом в таких модел€х ее вычисление значени€ некоторой числовой функции, а его элементї тарные шаги - арифметические операции. ѕоследовательность ша­гов определ€етс€ двум€ способами. ѕервый способ - суперпозици€, т.е. подстановка функции в функцию, а второй - рекурси€, т.е. определение значени€ функции через Ђранееї вычисленные значени€ этой же функции. ‘ункции, которые можно построить из целых чисел и арифметических операций с помощью суперпозиций рекурсивных определений, называютс€ рекурсивными функци€ми. ѕростейшим примером рекурсивной функции €вл€етс€ факториал.

¬торой класс моделей порожден следующей идеей. ƒл€ тог чтобы алгоритм понималс€ однозначно, а его каждый шаг считалс€ элементарным и выполнимым, он должен быть представлен чтобы его могла выполн€ть машина, к которой предъ€вл€ютс€ уже упом€нутые требовани€ простоты и универсальности. ќдной из машин €вилась абстрактна€ машина “ьюринга. ћашина “ьюринга состоит из трех частей ленты, головки и управл€ющего устройства (””). Ћента бесконечна в обе стороны и разбита на €чейки. Ёлементарный шаг машины “ьюринга состоит из следующих действий:

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

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

”стройство управлени€ хранит и выполн€ет команды машины.

“ретий класс моделей алгоритмов очень близок к предыдущему, но не оперирует конкретными машинными механизмами. Ќаиболее известна€ алгоритмическа€ модель этого типа - нормальные алгоритмы ћаркова.

ƒл€ нормального алгоритма задаетс€ алфавит, над которым он работает, конечное множество допустимых подстановок и пор€док их применени€. ≈сли в качестве алфавита вз€ть алфавит русского €зыка, а в качестве множества подстановок то, использу€ правила 1Ч3:

1) проверить возможность подстановок в пор€дке возрастани€ их номеров, и если она возможна (лева€ часть подстановки обнаружена в исходном слове), произвести подстановку (заменив левую часть на правую);

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

3) если ни одна подстановка не применима, то процесс преобразовани€ завершен, можно обнаружить, что по заданному алгоритму исходное слово.

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

ѕо€вление точного пон€ти€ алгоритма позволило сформулировать алгоритмически не разрешимые проблемы, т.е. задачи, дл€; решени€ которых невозможно построить алгоритм. «адача называетс€ алгоритмически неразрешимой, если не существует машины “ьюринга (или рекурсивной функции, или нормального алгоритме ћаркова), котора€ ее решает. Ќапример, неразрешимой оказалась проблема распознавани€ эквивалентности алгоритмов: нельз€ построить алгоритм, который по любым двум алгоритмам (программам) вы€сн€л бы, вычисл€ют они одну и ту же функцию или нет. «нание основных неразрешимостей теории алгоритмов необходимо дл€ специалиста по информатике. ќно предостережет его от увлечени€ глобальными прожектами всеобщей алгоритмизации точно так как знание основных законов физики предостерегает от попыток создани€ вечного двигател€.



 
     
   
 


ѕриглашаем прин€ть участие в круглом столе!
подробнее   >>>
 

»нститут ћенеджмента, Ёкономики и »нноваций начинает набор на курсы повышени€ квалификации!
подробнее   >>>
 

”важемые студенты јЌќ ¬ѕќ »ћЁи»!
подробнее   >>>
 

Ќачинаетс€ набор на курсы повышени€ квалификации!
подробнее   >>>
 

ѕриглашаем прин€ть участие в конференци€х!
подробнее   >>>
 


все новости...

 


–ассылки Subscribe.Ru
—овременное образование
ѕодписатьс€ письмом