Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

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

Лекция



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

Ранее были сформулированы основные требования к алгоритмам. Однако понятия, использованные в этих формулировках (такие, как ясность, четкость, элементарность), сами нуждаются в уточнении. Алгоритмы в интуитивном смысле не являются математическими объектами, к ним неприменимы формальные методы исследования и доказательства. Поэтому в XX веке были предприняты попытки формализации понятия алгоритма. Формализа­ция понятия алгоритма необходима по разным причинам. Например, сравнение двух алгоритмов по эффективности, проверка их эквивалентности и т. д. возможны только на основе их формального представления.

Впервые необходимость формального понятия алгоритма возникла в связи с проблемой алгоритмической неразрешимости некоторых задач. Долгое время математики верили в возможность того, что все строго поставленные математические задачи могут быть алгоритмически решены, нужно только найти алгоритм их решения. Вера в универсальность алгоритмических методов была подорвана работой Курта Геделя (1931 год), в которой было показано, что некоторые математические проблемы не могут быть решены с помощью алгоритмов из некоторого класса. Этот класс алгоритмов определяется некоторой формальной конкретизацией понятия алгоритма. Встал вопрос: являются ли алгоритмически неразрешимыми эти проблемы только в рамках использованной Геделем модели алгоритма или же для решения этих проблем вообще нельзя придумать никакого алгоритма ни в каком смысле? Общность результата Геделя зависит от того, совпадает ли использованный им класс алгоритмов с классом всех алгоритмов в интуитивном смысле. Об этом говорит сайт https://intellect.icu . Поэтому поиск и анализ различных уточнений и формализации алгоритма и соотношение этих формализаций с интуитивным понятием алгоритма является практически важным.

К настоящему времени предложен ряд формальных моделей алгоритма. Курт Гедель определил алгоритм как последовательность правил построения сложных математических функций из более простых, Алонзо Черч использовал формализм, называемый λ-исчислением, Алан Тьюринг предложил гипотетическое автоматическое устройство, которое сейчас называется машиной Тьюринга, и определил алгоритм как программу для этой машины, А. А. Марков определил нормальный алгоритм как конечный набор правил подстановок цепочек символов и т. д.

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

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

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

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

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

Из статьи мы узнали кратко, но содержательно про формализация понятия алгоритма
создано: 2018-05-21
обновлено: 2021-03-13
132265



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Теория конечных автоматов

Термины: Теория конечных автоматов