First page of the формулы archive.

Тьюринга и алгоритмически неразрешимые проблемы

Posted by admin on 16 Август 2010 with No Comments
in Лекции по алгебре
as , , , ,

Алан Тьюринг высказал предположение (известное как Тезис Чёрча — Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.

В течение первого десятилетия истории теории алгоритмов неразрешимые массовые проблемы были обнаружены лишь внутри самой этой теории (сюда относится описанная выше проблема применимости), а также внутри математической логики (проблема выводимости в классическом исчислении предикатов). Поэтому считалось, что теория алгоритмов представляет собой обочину математики, не имеющую значения для таких её классических разделов, как алгебра или анализ. Положение изменилось после того, как А. А. Марков и Э. Л. Пост в 1947 году установили алгоритмическую неразрешимость известной в алгебре проблемы равенства для конечнопорождённых и конечноопределённых полугрупп (т. н. проблемы Туэ). Впоследствии была установлена алгоритмическая неразрешимость и многих других «чисто математических» массовых проблем. Одним из наиболее известных результатов в этой области является доказанная Ю. В. Матиясевичем алгоритмическая неразрешимость десятой проблемы Гильберта.

Исторический очерк

Posted by admin on 23 Июль 2010 with No Comments
in Лекции по алгебре
as , , , ,

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

Впервые, насколько можно судить по дошедшим до нас древним сочинениям, развитая алгебраическая система появляется в «Арифметике» Диофанта (IV век). Вряд ли можно сомневаться, что у него были предшественники, как они имелись у Евклида, Архимеда и других, однако мы ничего не знаем ни о людях, ни о трудах, на которые мог опираться этот замечательный алгебраист. Да и последователей у него не было до XV века. Впрочем, в Европе с переводом «Арифметики» познакомились только в XVI веке, и методы Диофанта оказали огромное влияние на Виета и Ферма.

Основная проблематика «Арифметики» — нахождение рациональных решений неопределённых уравнений (многочленов произвольной степени) с рациональными коэффициентами. У Диофанта используется буквенная символика, правда, по-прежнему только для неизвестных. Во введении к «Арифметике» Диофант принимает следующие обозначения: неизвестную он называет «числом» и обозначает буквой ?, квадрат неизвестной — символом ?? и т. д. Особые символы обозначали отрицательные степени, знак равенства и даже, похоже, отрицательные числа (есть даже правило знаков: минус на минус даёт плюс). Всё прочее выражается словесно. Сформулированы многие привычные нам правила алгебры: смена знака при переносе в другую часть уравнения, сокращение общих членов и др.

Индийские математики средневековья тоже далеко продвинулись в алгебре; их символика богаче, чем у Диофанта, хотя несколько громоздка (засорена словами).

В Европе, в книгах «Арифметика» и «О данных числах» Иордана Неморария (XIII век) усматриваются зачатки символической алгебры, до поры до времени не отделившейся от геометрии. У него, а также у Фибоначчи уже встречаются выражения вроде «a лошадей за f дней съедают e мер овса». Однако в общую концепцию изложения символизм у них ещё не включён.

Крупнейший алгебраист XV века Лука Пачоли вводит свой аналог алгебраической символики, ещё не слишком общий и не слишком удобный.

Концептуальную реформу и коренные улучшения алгебраического языка ввёл в конце XVI века Франсуа Виет, адвокат по профессии, математик по склонности души. Он чётко представлял себе конечную цель — разработку «нового исчисления», своего рода обобщённой арифметики. Виет обозначал буквами все коэффициенты (кстати, именно Виет придумал этот термин). Все задачи решаются в общем виде, и только потом приводится числовые примеры. Виет свободно применяет алгебраические преобразования, замену переменных и другие алгебраические приёмы.

Система Виета вызвала всеобщее восхищение. Она позволила описать законы арифметики и алгоритмы с немыслимыми ранее общностью и компактностью, облегчила и углубила исследование общих числовых законов. Однако символика Виета была непохожа на современную, местами громоздка, и учёные разных стран приступили к её совершенствованию.

Англичанин Томас Хэрриот в своём посмертно изданном (1631) труде уже очень близок к современной символике: он обозначает переменные строчными буквами, а не заглавными, как у Виета, использует знак равенства, а также придуманные им символы сравнения «>» и «<». Практически современный вид алгебраической символике придал Рене Декарт (середина XVII века, трактат «Геометрия»). Итогом и завершением этого процесса стала «Универсальная арифметика» Ньютона. Некоторые оставшиеся тонкости уточнил Эйлер.

Теория графов

Posted by admin on 23 Июль 2010 with No Comments
in Лекции по алгебре
as , , , ,

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V?V. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, […]

Возникновение теории алгоритмов

Posted by admin on 23 Июль 2010 with No Comments
in Лекции по алгебре
as , , , ,

Развитие теории алгоритмов начинается с доказательства К. Гёделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 г. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем (в частности, проблемы выводимости в исчислении предикатов) вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были […]

Современное состояние теории алгоритмов

Posted by admin on 23 Июль 2010 with No Comments
in Лекции по алгебре
as , , , ,

В настоящее время теория алгоритмов развивается, главным образом, по трем направлениям. Классическая теория алгоритмов изучает проблемы формулировки задач в терминах формальных языков, вводит понятие задачи разрешения, проводит классификацию задач по классам сложности (P, NP и др.). Теория асимптотического анализа алгоритмов рассматривает методы получения асимптотических оценок ресурсоемкости или времени выполнения алгоритмов, в частности, для рекурсивных алгоритмов. […]

Классы сложности

Posted by admin on 23 Июль 2010 with No Comments
in Лекции по алгебре
as , , , ,

В рамках классической теории осуществляется классификация задач по классам сложности (P-сложные, NP-сложные, экспоненциально сложные и др.). К классу P относятся задачи, которые могут быть решены за время, полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (например, машины Тьюринга), а к классу NP — задачи, которые могут быть решены за полиномиально выраженное время […]

Аксиоматика теории множеств

Posted by admin on 23 Июль 2010 with No Comments
in Лекции по алгебре
as , , , ,

Cовременная теория множеств строится на системе аксиом — утверждений, принимаемых без доказательства, из которых выводятся все теоремы и утверждения теории множеств. Система аксиом Цермело—Френкеля (ZF) является стандартной системой аксиом для теории множеств. Эта и подобные ей системы аксиом любопытны потому, что любая математическая теория может быть «переведена» на язык теории множеств таким образом, что теоремы […]

Парадоксы теории множеств

Posted by admin on 23 Июль 2010 with No Comments
in Лекции по алгебре
as , , , ,

Парадоксами теории множеств называют рассуждения, демонстрирующие противоречивость наивной теории множеств, такие как парадокс Бурали-Форти (1897) парадокс Кантора (1899) парадокс Рассела (1905) рассуждения, результат которых интуитивно кажется ложным или «парадоксальным», но которые, тем не менее, являются следствием аксиом формальной теории множеств, включая: предложенный Б. Расселом «парадокс Тристрама Шенди», демонстрирующий нарушение принципа «часть меньше целого» для бесконечных […]

Краткий конспект курса высшей алгебры

Posted by admin on 23 Июль 2010 with No Comments
in Лекции по алгебре
as , , , ,

Числа Натуральные числа. Принцип математической индукции. Свойства операций сложения и умножения натуральных чисел. Кольцо целых чисел. Поля рациональных и вещественных (действительных) чисел. Аксиомы поля. Поле комплексных чисел: определение; свойства мнимой единицы, вещественной и мнимой частей комплексного числа, сопряженного комплексного числа, модуля и аргумента комплексного числа. Умножение комплексных чисел в тригонометрической форме. Формулы Муавра для решения […]

Теория множеств Кантора

Posted by admin on 23 Июль 2010 with No Comments
in Лекции по алгебре
as , , , ,

Во второй половине XIX века немецкий математик Георг Кантор разработал свою программу стандартизации математики, в рамках которой любой математический объект должен был оказываться тем или иным «множеством». Этот подход изложен в двух его статьях, опубликованных в 1879—1897 годах в известном немецком журнале «Математические анналы» (нем. «Mathematische Annalen»).[1] Например, натуральное число, по Кантору, следовало рассматривать как […]