История развития теории алгоритмов.

Из личных запасов халявы студента группы ЭВМ-110. Буйняков И.А. 2012г

Основные понятия МЛиТА

Логика-искусство рассуждений; наука о законах и формах решения. Булевы

функции -логич. операции над величинами, принимающими 2 значения: 0 или

1. Равносильные функции. Две функции, как и определяющие их формулы

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

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

булевых функций вместе с операциями отрицание, конъюнкция(*) и

дизъюнкция(+). Предикат-высказывание, выражающее свойство одного или

нескольких объектов. Логич. функции. Отличительная особенность логич.

функции состоит в том, что они принимают значения конечных множеств, т.е.

область значения логич. функции всегда представляет собой конечную

совокупность чисел, символов, понятий, свойств и любых объектов

окружающей природы и техники.

Тавтологией (тождественно истинной пропозициональной формой или

общезначимой формулой) называется пропозициональная форма, которая

принимает значение И при любой совокупности истинностных значений

пропозициональных букв, входящих в нее.

Таблица истинности тавтологии имеет результирующий столбец, состоящий

только из И.

Примером тавтологии является пропозициональная форма (А∨ А), в чем

легко убедиться, составив таблицу истинности. Другие примеры тавтологий:

А⇒ А, (А≡ В)≡ (В≡ А).

Высказыванием называется любое повествовательное предложение, которое

истинно либо ложно.

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

предложения:

Сократ - человек.

2 + 2=4.

5 > 7.

Не являются высказываниями в математической логике предложения:

х > 5 (здесь х∈ (-∞, ∞) и считается переменной).

Закройте книгу!

Данное предложение ложно.

Какое же у меня есть дело на земле?

Математическая логика

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

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

Программы

для ЭВМ

История развития теории алгоритмов.

Теория алгоритмов, как наука, непосредственно связана с предметами

математической логики и теории конечных автоматов. В Древней Греции

Аристотель и его ученик Платон сформулировали основные правила логики,

которые используются до нашего времени для доказательства правильности

и решения логических задач.

Математическая логика – это наука о правилах формального

логического мышления.

Теория автоматов изучает модели конечных автоматов, описывающие

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

устройств.

Возникновение понятия «алгоритм» связано с именем узбекского

математика Маххамада ибн Мусса Аль-Хорезми (IX в.), который

сформулировал правила умножения и деления чисел в десятичной системе

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

как algorismi. В дальнейшем термин алгоритм использовался для

обозначения произвольных процессов, в которых искомые величины

решаемых задач находятся последовательно из исходных данных по

определённым правилам.

На протяжении многих веков учёные всего мира создали много методов и

алгоритмов решения различных задач в математике и физике.

В 1936 году английский ученый Тьюринг разработал модель

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

доказал:

 возможность автоматического решения задач с помощью

алгоритмов, реализуемых в виде программы;

 реальность создания универсальных вычислительных машин.

На основе этой модели («машина Тьюринга») была построена

классическая теория алгоритмов, основу которой составляли формальные

описания следующих понятий:

1 – алгоритм;

2 – алгоритмический процесс;

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

Таким образом, само понятие алгоритма стало объектом

математического изучения. В классической теории алгоритмов изучаются

только вопросы существования или несуществования алгоритмов путем

сведения этих вопросов к исследованию какого-либо одного узкого класса

алгоритмов, что не позволяет охватить многие важные проблемы данной

теории.

Теоретический аспект теории алгоритмов заключается в том, что она

является фундаментов вычислительных наук, средством обоснования

математики, доказательства правильности и разрешимости задач.

До середины XX века использовалось понятие алгорифма,

заимствованное из математики. Позже с возникновением практического

аспекта теории алгоритмов стал использоваться термин алгоритм. ____________Причиной

этому послужило развитие наук, изучающих структуру и принципы работы

ЭВМ. Решение задач на ЭВМ было принято описывать в виде алгоритмов.

Создание компьютеров и языков программирования способствовало

выделению теории алгоритмов как самостоятельной дисциплины. Сегодня

понятие алгоритма вышло за пределы математики и используется в

различных областях, где алгоритмом называют точно сформулированное

правило, являющееся руководством для достижения необходимого

результата. Кроме того, алгоритмы являются первоосновой для

программирования задач на ЭВМ.

Практический аспект теории алгоритмов заключается в классификации

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

оценке сложности алгоритмов, создании методов разработки быстрых

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

алгоритмов решения задач различных классов.