Теория алгоритмов

Негосударственное образовательное учреждение высшего  профессионального образования 

Московский психолого-социальный университет

 

Факультет информационных технологий

Кафедра информационных технологий

 Дисциплина основы  бизнеса

 

Реферат на тему:

 

«Теория Алгоритмов»

 

 

 

Выполнил:

Агаев Ренат Игоревич

Студент 3 курса, гр. 210 ЗИТ

 

Оценка:________________

                                                               Преподаватель

_______________/_____________/

                                                                                           (Подпись)                  (ФИО)  

                                                                                 «______»_____________201___г. 

 

 

 

 

 

 

Сдано «____»_______________ 201___г.

Методист____________________ ______________

                                   (ФИО)                                     Подпись 

 

 

 

 

 

 

 

 

Москва 2013г.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теория  алгоритмов

 

      Теория алгоритмов - наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т.п. Первым дошедшим до нас алгоритмом в его интуитивном понимании – конечной последовательности элементарных действий, решающих поставлен-ную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида). Отметим, что в течение длительного времени, вплоть до начала XX века само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм Евклида». Для описания пошагового решения других математических задач использовалось слово «метод». Начальной точкой отсчета современной теории алгоритмов можно считать работу немецкого математика Курта Гёделя (1931 год - теорема о неполноте символических логик), в которой было показано, что некоторые математические проблемы не могут быть решены алгоритмами из некоторого класса. Общность результата Геделя связана с тем, совпадает ли использованный им класс алгоритмов с классом всех (в интуитивном смысле) алгоритмов. Эта работа дала толчок к поиску и анализу различных формализаций алгоритма. Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годы Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Черча были эквивалентными формализмами алгоритма. Сформулированные ими тезисы (Поста и Черча-Тьюринга) постулировали эквивалентность предложенных ими формальных систем и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство алгоритмически неразрешимых проблем. В 1950-е годы существенный вклад в теорию алгоритмов внесли работы Холмогорова и Маркова. К 1960-70-ым годам оформились следующие направления в теории алгоритмов: Классическая теория алгоритмов (формулировка задач в терминах формальных языков, понятие задачи разрешения, введение сложностных классов, формулировка в 1965 году Эдмондсом проблемы P=NP, открытие класса NP-полных задач и его исследование); Теория асимптотического анализа алгоритмов (понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический анализ трудоемкости или времени выполнения), в развитие которой внесли существенный вклад Кнут, Ахо, Хопкрофт, Ульман, Карп; Теория практического анализа вычислительных алгоритмов (получение явных функции трудоёмкости, интервальный анализ функций, практические критерии качества алгоритмов, методика выбора рациональных алгоритмов), основополагающей работой в этом направлении, очевидно, следует считать фундаментальный труд Д. Кнута «Искусство программирования для ЭВМ».

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цели и задачи теории алгоритмов

 

      Обобщая результаты  различных разделов теории алгоритмов  можно выделить следующие цели  и соотнесенные с ними задачи, решаемые в теории алгоритмов:

формализация понятия «алгоритм» и исследование формальных алгоритмических  систем;

формальное доказательство алгоритмической  неразрешимости ряда задач;

классификация задач, определение  и исследование сложностных классов;

асимптотический анализ сложности  алгоритмов;

исследование и анализ рекурсивных  алгоритмов;

получение явных функций трудоемкости в целях сравнительного анализа  алгоритмов;

разработка критериев сравнительной  оценки качества алгоритмов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

рациональный выбор из известного множества алгоритмов решения данной задачи с учетом особенностей их применения (например, при ограничениях на размерность  исходных данных или объема дополнительной памяти);

получение временных оценок решения  сложных задач;

получение достоверных оценок невозможности  решения некоторой задачи за определенное время, что важно для криптографических  методов;

разработку и совершенствование  эффективных алгоритмов решения  задач в области обработки  информации на основе практического  анализа.

 

 

 

 

 

 

 

 

 

 

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

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

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

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

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

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

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

алгоритм должен быть единым для  всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

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

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

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

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