Раздел: Элементарные алгоритмы
Основы теории элементарных алгоритмов
В учебном пособии впервые достаточно полно рассматриваются основы теории элементарных алгоритмов (элементарных по Кальмару функций), изученных современной теорией алгоритмов и успешно используемых в математических исследованиях. Излагаются также, способы получения границ оптимизации (в том числе и полиномиального вида) для алгоритмов установления разрешимости синтаксически ограниченных уравнений дискретного характера.
Учебное пособие предназначено для студентов математических факультетов вузов и аспирантов. Оно будет также полезно...
Математический фундамент
Автор стремился к объективному изложению современных тенденций в применении математического фундамента, полезного при использовании ЭВМ и служащего красной нитью при планировании создания будущих программных комплексов. От такого математического фундамента можно ожидать троякой пользы: во-первых, помощи исполнительного помощника, умеющего детализировать конкретные намерения; во-вторых, хитроумного помощника, предлагающего иногда весьма неожиданные решения неотложных проблем, и, наконец, в-третьих, умудренного опытом седого провидца,...
Элементарные по Кальмару алгоритмы
Эта работа не столько о конкретных алгоритмах, сколько о том общем, что есть в алгоритмах, которые заведомо находятся в практическом фундаменте науки. Настоящая статьяотражает значительную работу по существенному увеличению прозрачности фундаментальной теории элементарных по Кальмару алгоритмов. При этом пришлось исключить не только значительное количество устаревших результатов, но и некоторые блестящие теоремы, созерцание которых способно нарушить начальное гармоничное представление об основах теории элементарных по Кальмару...
Алгоритмы в математике
Алгоритмы в математике использовались давно, но математически точное понятие алгоритма было предложено только в тридцатые годы нашего столетия. Тогда стало ясно, что некоторые дискретные задачи математики нельзя решать посредством алгоритмов. Последовавшее бурное развитие теории алгоритмов обеспечило появление большого числа разнообразных задач из различных областей математики, для каждой из этих задач была доказана невозможность их решения посредством алгоритма. Среди таких задач проблемы равенства в полугруппах и группах с конечным...
Доказательство алгоритмической неразрешимости
Параллельно с доказательствами алгоритмической неразрешимости многих естественно формулируемых математических массовых проблем возник вопрос об оптимизации алгоритмов, решающих математические массовые проблемы, естественно формулируемые в математической логике, алгебре, теории чисел, дискретной математике, математической кибернетике и метатеории программирования. Первоначально речь могла идти о примитивной рекурсивности алгоритма, затем об элементарности алгоритма по Кальмару.
Доказательство принадлежности некоторого алгоритма...
Классическая теория алгоритмов
Классическая теория алгоритмов выделилась в математической логике в основном благодаря доставляемым ею средствам доказательства неразрешимости многих проблем общематематического характера. Значительным дополнительным стимулом для ее развития послужили исследования в области конструктивной математики, предпринятые, в частности, А. А. Марковым, Г. С. Цейтиным, Н. А. Шаниным и другими математиками, включая автора. Среди традиционных определений математического понятия алгоритма имеется большое разнообразие.
Фундаментом теории алгоритмов...
Теории алгоритмов
Деление теории алгоритмов на классическую и прикладную отражает две точки зрения на понятие алгоритма: чисто математическую и математико-прагматическую. Результаты классической теории являются фундаментом прикладной теории алгоритмов. В настоящее время происходит взаимное обогащение этих двух подходов, выражающееся, в частности, в стремлении математических логиков к углубленному взаимному пониманию с программистами.
Отсутствие методологической основы изучения возможных границ оптимизации конкретных алгоритмов порождает различные...
Оценки сложности задач
Оценки сложности тех или иных задач, встречающихся в практической деятельности, позволяют разумно и экономно осуществлять их решение.
Особый интерес представляют те задачи, которые могут решаться на ЭВМ.
Разделение алгоритмов на те, которые могут многократно пропускаться на ЭВМ с разнообразными достаточно длинными исходными данными, и на те, которые не могут быть так использованы, является весьма актуальным при создании программ на основе математического описания алгоритмов.
Это разделение может быть проведено в нескольких направлениях....
Иерархия класса
Наконец, имеется еще одно направление — изучение иерархии класса элементарных по Кальмару алгоритмов— класса, содержащего все практически вычислимые на ЭВМ алгоритмы. Это направление позволяет уточнить современный математический язык, обеспечивая его эффективность, например, при установлении разрешимости уравнений типов рассматриваемых во втором разделе книги. По сути дела речь идет о синтаксически ограниченных вычислениях.
Первый раздел книги носит в значительной степени вводный характер. Изложенный материал представлен в существенна...
Алгоритмы, вычислимые на эвм, и элементарные алгоритмы
1. Преемственность исследований по теории элементарных рекурсивных алгоритмов. Интенсивное развитие общих представлений о потенциальной вычислимости в основном завершено. Эти представления приобрели во многих отношениях законченный вид и дали толчок двум направлениям в математических исследованиях. Во-первых, значительная масса исследований сконцентрировалась вокруг тем, связанных с различными ограничениями на абстрактные вычисления в рамках алгоритмической теории сложности вычислений. Частично это объясняется широким распространением...
Оценка величины необходимой памяти
В настоящее время задачи, для которых принципиально возможен алгоритм, их решающий, классифицируют по его сложности. Классификация осуществляется в основном с помощью оценки числа необходимых шагов или оценки величины необходимой памяти. Рассматриваются и другие оценки сложности алгоритмов.
Прежде всего отметим, что в качестве нижней оценки времени и памяти ЭВМ итерированная экспонента характеризует задачу как абсолютно нереальную для вычисления ее на ЭВМ для ряда значении параметров.
Еще изобретатель шахмат продемонстрировал, что...
Предикаты
Все элементарные по Кальмару предикаты, т. е. алгоритмы вида минимум (Н(Х), 1), где Н — элементарный алгоритм, и только они представимы при некотором К в виде () таким образом, что для такого Р формула () эквивалентна формуле. При получении последнего результата использовались некоторые конструкции Ю. В. Матиясевича, предложенные им при решении десятой проблемы Гильберта для установления алгоритмической неразрешимости проблемы существования решений в целых числах у многочленов со многими переменными.
При всяком К существует натуральное число...