http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Mamoshkin.Arseny&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T09:10:00ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BD%D0%BA%D1%83%D1%80%D1%81_%D0%B4%D0%BB%D1%8F_%D0%B1%D0%BE%D0%BB%D0%B5%D0%B5_%D1%83%D0%B4%D0%B0%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_URL_%D1%81%D0%B0%D0%B9%D1%82%D0%B0_%D0%B2%D0%B8%D0%BA%D0%B8-%D0%BA%D0%BE%D0%BD%D1%81%D0%BF%D0%B5%D0%BA%D1%82%D0%BE%D0%B2&diff=17500Конкурс для более удачного URL сайта вики-конспектов2012-01-21T08:59:08Z<p>Mamoshkin.Arseny: /* Варианты */</p>
<hr />
<div>Хочется избавиться от имени mediawiki, потому что это название вики-движка .<br />
<br />
Предлагайте варианты URL для вики-конспектов на этой странице.<br />
Подписывайтесь, бонусы возможны.<br />
<br />
== Варианты ==<br />
<br />
{| class="wikitable"<br />
!Вариант!!Автор (<nowiki>~~~</nowiki>)<br />
|-<br />
|knowledge||[[Участник:Kirelagin|Кирилл Елагин]]<br />
|-<br />
|wikiconsp||[[Участник:Igor buzhinsky|Игорь Бужинский]]<br />
|-<br />
|wk ''(что бы это ни значило)''||[[Участник:Kirelagin|Кирилл Елагин]]<br />
|-<br />
|lectures||[[Участник:Igor buzhinsky|Игорь Бужинский]]<br />
|-<br />
|theory||[[Участник:Shevchen|Дмитрий Шевченко]]<br />
|-<br />
|outlines||[[Участник:Shevchen|Дмитрий Шевченко]]<br />
|-<br />
|wikikt||[[Участник:Mamoshkin.Arseny|Арсений Мамошкин]]<br />
|}</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0&diff=9003Натуральные числа2011-05-28T18:42:39Z<p>Mamoshkin.Arseny: /* Существование наименьшего элемента */</p>
<hr />
<div>{{Требует доработки<br />
|item1=('''Исправлено''') Пожалуйста, прочитайте статью [[Обсуждение:Алгоритмы алгебры и теории чисел]]<br />
}}<br />
<br />
==Деление чисел с остатком==<br />
<br />
{{Определение<br />
|definition=<br />
Если натуральное число <tex>n\,</tex> не делится на натуральное число <tex>m\,</tex>, т.е. не существует такого натурального числа <tex>k\,</tex> , что <tex>n = m\,k,</tex> то деление называется '''делением с остатком'''.<br />
}}<br />
<br />
'''Формула деления с остатком''': <tex>n = m\,k + r,</tex> где <tex>n\,</tex> — делимое, <tex>m\,</tex> — делитель, <tex>k\,</tex> — частное, <tex>r\,</tex> — остаток, причем <tex>0\leqslant r < b </tex><br />
<br />
:Любое число можно представить в виде: <tex>n = 2\,k + r,</tex> , где остаток <tex>r\,</tex> = <tex>0\,</tex> или <tex>r\,</tex> = <tex>1\,</tex><br />
<br />
:Любое число можно представить в виде: <tex>n = 4\,k + r,</tex> , где остаток <tex>r\,</tex> = <tex>0\,</tex> или <tex>r\,</tex> = <tex>1\,</tex> или <tex>r\,</tex> = <tex>2\,</tex> или <tex>r\,</tex> = <tex>3\,</tex><br />
<br />
:Любое число можно представить в виде: <tex>n = m\,k + r,</tex> , где остаток <tex>r\,</tex> принимает значения от <tex>0\,</tex> до <tex>(m-1)\,</tex><br />
<br />
==Принцип индукции, существование наименьшего числа в любом множестве натуральных чисел==<br />
<br />
===Индукция===<br />
<br />
Формулировка '''принципа математической индукции''':<br />
<br />
:Пусть имеется последовательность утверждений <tex>A_1, A_2, A_3, \ldots</tex> И пусть первое утверждение <tex>A_1</tex> верно и мы умеем доказать, что из верности утверждения <tex>A_k</tex> следует верность <tex>A_{k + 1}</tex>. Тогда все утверждения в этой последовательности верны.<br />
<br />
Верность этого метода доказательства вытекает из так называемой '''аксиомы индукции''', пятой из аксиом Пеано, которые определяют натуральные числа. Рассмотрение аксиом Пеано выходит за рамки этой статьи.<br />
<br />
Также существует '''принцип полной математической индукции'''. Вот его строгая формулировка:<br />
<br />
:Пусть имеется последовательность утверждений <tex>A_1, A_2, A_3, \ldots</tex>. И пусть мы умеем доказать, что из верности утверждения <tex>A_1, A_2, A_3, \ldots, A_k</tex> следует верность <tex>A_{k + 1}</tex>. Тогда все утверждения в этой последовательности верны.<br />
<br />
===Существование наименьшего элемента===<br />
<br />
Аксиому индукции можно заменить на аксиому существования минимума, и доказать аксиому индукции как теорему.<br />
<br />
{{Теорема<br />
|id=th1<br />
|about=О существовании минимума<br />
|statement=<br />
Для любого подмножества натурального ряда всегда существует минимум.<br />
Т. е. <tex>\forall A \subset \mathbb N, A \ne \varnothing, \exists x \in A: \forall y \in A, x \leqslant y</tex><br />
|proof=<br />
Если <tex>1 \in A</tex>, то <tex>1</tex> и есть '''min'''. Иначе <tex>1 \notin A</tex><br />
Если <tex>2 \in A</tex>, то <tex>2</tex> и есть '''min'''. Иначе <tex>2 \notin A</tex><br />
<tex>P(n)</tex> - все элементы <tex>\leqslant n</tex> не лежат в <tex>A</tex> <tex>\Rightarrow</tex> <tex>P(1) ... P(n)</tex> - верно и <tex>P(n+1)</tex> - верно (т.к. он был бы '''min''') <tex>\Rightarrow</tex> в <tex>A</tex> ничего не лежит. Противоречие.<br />
}}<br />
<br />
[[Категория: Классы чисел]]</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0_%D1%87%D0%B8%D1%81%D0%B5%D0%BB_%D0%B2_b-%D0%B8%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B5_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_(%D0%94%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0)&diff=9002Арифметика чисел в b-ичной системе счисления (Длинная арифметика)2011-05-28T18:37:51Z<p>Mamoshkin.Arseny: /* Подбор значения очередной цифры в алгоритме деления в столбик */</p>
<hr />
<div>{{Определение<br />
|definition=<br />
Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.<br />
}}<br />
<br />
Основная идея заключается в том, что число хранится в виде массива его цифр.<br />
<br />
Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.<br />
<br />
==Представление в памяти==<br />
<br />
Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа в '''b'''-й системе счисления.<br />
<br />
Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).<br />
<br />
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.<br />
<br />
==Сложение, вычитание, умножение, деление на короткое, деление на длинное==<br />
<br />
Операции над числами в этом виде длинной арифметики производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.<br />
<br />
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.<br />
<br />
==Подбор значения очередной цифры в алгоритме деления в столбик==<br />
<br />
Подбор следующей цифры <tex>k \in [0, b)</tex> частного можно производить с помощью стандартного алгоритма двоичного поиска за <tex>\ln(b)</tex>.<br />
<br />
Но также существуют и более быстрые алгоритмы. Довольно интересный способ состоит в высказывании догадки ('''qGuess''') по первым цифрам<br />
делителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированно<br />
правильного результата, однако неплохое приближение все же получится.<br />
Пусть очередной шаг представляет собой деление некоторого <tex>U = (u_0, u_1, \cdots, u_n)</tex> на <tex>B = (b_0, b_1, \cdots, b_{n-1})</tex>.<br />
Если <tex>b_{n-1} \ge</tex> '''BASE''' <tex>/2</tex> ('''BASE''' — основание системы счисления), то можно доказать следующие факты:<br />
<br />
*1. Если положить '''qGuess''' <tex> = (u_n \cdot </tex> '''BASE''' <tex>+ u_{n-1}) / b_{n-1}</tex> , то '''qGuess'''<tex>-2 \le q \le</tex> '''qGuess'''.<br />
Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного,<br />
но может быть больше на 1 или 2.<br />
*2. Если же дополнительно выполняется неравенство '''qGuess'''<tex> \cdot b_{n-2} ></tex> '''BASE''' <tex>\cdot r + u_{n-2}</tex> , где r – остаток при нахождении '''qGuess''' и '''qGuess''' ≠ '''BASE''', то '''qGuess''' <tex>-1 \le q \le</tex> '''qGuess''', причем вероятность события '''qGuess''' = q + 1 приблизительно равна 2 / '''BASE'''.<br />
Таким образом, если <tex>b_{n-1} \ge</tex> '''BASE'''<tex>/2</tex>, то можно вычислить '''qGuess''' <tex> = (u_n \cdot</tex>'''BASE''' <tex> + u_{n-1}) / b_{n-1}</tex> и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным q, либо, с вероятностью 2/'''BASE''', на единицу большим числом.<br />
<br />
Что делать, если <tex>b_{n-1}</tex> слишком мало, чтобы пользоваться таким способом?<br />
Например, можно домножить делитель и делимое на одно и то же число '''scale'''='''BASE'''<tex> / ( b_{n-1} +1 )</tex>.<br />
При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если '''qGuess''' получилось все же на единицу большим q, будем использовать вычитание, которое вместо отрицательного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен -1. Это сигнал, что необходимо прибавить одно B назад.<br />
Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос (-1)).<br />
<br />
http://forum.sources.ru/index.php?showtopic=210512&hl=</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0_%D1%87%D0%B8%D1%81%D0%B5%D0%BB_%D0%B2_b-%D0%B8%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B5_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_(%D0%94%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0)&diff=9001Арифметика чисел в b-ичной системе счисления (Длинная арифметика)2011-05-28T17:54:13Z<p>Mamoshkin.Arseny: /* Подбор значения очередной цифры в алгоритме деления в столбик */</p>
<hr />
<div>{{Определение<br />
|definition=<br />
Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.<br />
}}<br />
<br />
Основная идея заключается в том, что число хранится в виде массива его цифр.<br />
<br />
Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.<br />
<br />
==Представление в памяти==<br />
<br />
Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа в '''b'''-й системе счисления.<br />
<br />
Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).<br />
<br />
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.<br />
<br />
==Сложение, вычитание, умножение, деление на короткое, деление на длинное==<br />
<br />
Операции над числами в этом виде длинной арифметики производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.<br />
<br />
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.<br />
<br />
==Подбор значения очередной цифры в алгоритме деления в столбик==<br />
<br />
Подбор следующей цифры <tex>k \in [0, b)</tex> частного можно производить с помощью стандартного алгоритма двоичного поиска за <tex>\ln(b)</tex>.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=9000Системы счисления2011-05-28T17:53:04Z<p>Mamoshkin.Arseny: /* Запись числа в b-ичной системе счисления */</p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Систе́ма счисле́ния''' — символический метод записи чисел, представление чисел с помощью письменных знаков.<br />
}}<br />
<br />
==Позиционные системы счисления==<br />
<br />
В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.<br />
<br />
Под позиционной системой счисления обычно понимается ''b''-ричная система счисления, которая определяется [[целое число|целым числом]] <math>b>1</math>, называемым основанием системы счисления.<br />
<br />
===Запись числа в b-ичной системе счисления===<br />
<br />
Целое число ''x'' в ''b''-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа ''b'':<br />
: <tex>x = \sum_{k=0}^{n-1} a_k b^k</tex>, где <tex>a_k</tex> — это целые числа, называемые '''цифрами''', удовлетворяющие неравенству <tex>0 \leq a_k \leq (b-1)</tex>.<br />
Каждая степень <tex>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ричном представлении <tex>x</tex> была также ненулевой.<br />
<br />
Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число <tex>x</tex> записывают в виде последовательности его ''b''-ричных цифр, перечисляемых по убыванию старшинства разрядов слева направо:<br />
: <tex>x = a_{n-1} a_{n-2}\dots a_0.</tex><br />
Например, число ''сто три'' представляется в десятичной системе счисления в виде:<br />
: <tex> 103 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0}.</tex><br />
<br />
Наиболее употребляемыми в настоящее время позиционными системами являются:<br />
* 1 — единичная (как позиционная может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.);<br />
* 2 — двоичная (в дискретной математике, информатике, программировании);<br />
* 8 — восьмеричная;<br />
* 10 — десятичная (используется повсеместно);<br />
* 12 — двенадцатеричная (счёт дюжинами);<br />
* 16 — шестнадцатеричная (используется в программировании, информатике).<br />
<br />
==Смешанные системы счисления==<br />
<br />
'''Смешанная система счисления''' является обобщением <tex>b</tex>-ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел <tex>\{b_k\}_{k=0}^{\infty}</tex> и каждое число <tex>x</tex> представляется как линейная комбинация:<br />
: <tex>x = \sum_{k=0}^{n-1} a_{k}b_k</tex>, где на коэффициенты <tex>a_{k}</tex> (называемые как и прежде ''цифрами'') накладываются некоторые ограничения.<br />
Записью числа <tex>x</tex> в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса <tex>k</tex>, начиная с первого ненулевого.<br />
<br />
В зависимости от вида <tex>b_k</tex> как функции от ''k'' смешанные системы счисления могут быть степенными, показательными и т. п. Когда <tex>b_k=b^k</tex> для некоторого <tex>b</tex>, показательная смешанная система счисления совпадает с <tex>b</tex>-ричной системой счисления.<br />
<br />
Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина ''d дней h часов m минут s секунд'' соответствует значению <tex>d\cdot 24\cdot 60\cdot 60 + h\cdot 60\cdot 60 + m\cdot 60 + s</tex> секунд.<br />
<br />
==Фибоначчиева система счисления==<br />
<br />
{{Определение<br />
|definition=<br />
последовательность чисел Фибоначчи <tex>\left\{F_n\right\}</tex> задается линейным рекуррентным соотношением:<br />
: <tex>F_0 = 0,\qquad F_1 = 1,\qquad F_{n+1} = F_n + F_{n-1}, \quad n\in\mathbb{N}.</tex><br />
}}<br />
<br />
'''Фибоначчиева система счисления''' основывается на [[числа Фибоначчи|числах Фибоначчи]].<br />
<br />
: <tex>x = \sum_{k=0}^n f_k F_k</tex>, где <tex>F_k</tex> — числа Фибоначчи, <tex>f_k\in\{0,1\}</tex>, при этом в записи <tex>f_nf_{n-1}\dots f_0</tex> не встречается две единицы подряд.<br />
<br />
Таким образом, любое неотрицательное целое число <tex>a = 0,\ 1,\ 2,\dots</tex> можно единственным образом представить через последовательность битов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub>: <tex>a = \sum_k \varepsilon_k F_k,\ \varepsilon_k = 0,1</tex>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <tex>\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</tex>.<br />
За исключением последнего свойства, данное представление аналогично двоичной системе счисления.<br />
<br />
{{Теорема<br />
|id=th1<br />
|author=Цекендорф<br />
|statement=<br />
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.<br />
|proof=<br />
Доказательство существования легко провести по индукции. Любое целое число <tex>a\ge 1</tex> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого <tex>n\ge 2</tex> верно неравенство: <tex>F_n \le a < F_{n+1}</tex>. Таким образом, <tex>a = F_n + a'</tex>, где <tex>a'=a-F_n\ <\ F_{n-1}</tex>, так что разложение числа <tex>a'</tex> уже не будет содержать слагаемого <tex>F_{n-1}</tex>.<br />
}}</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D1%8B_%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%BB%D0%B0%D1%85&diff=8999Теоремы о простых числах2011-05-28T17:52:25Z<p>Mamoshkin.Arseny: /* Теорема о расходимости ряда \sum_{}^{}1/n */</p>
<hr />
<div>==Теорема о существовании бесконечного числа простых чисел==<br />
<br />
{{Теорема<br />
|id=th1<br />
|statement=<br />
Простых чисел бесконечно много.<br />
|proof=<br />
Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.<br />
}}<br />
<br />
==Теорема о расходимости ряда <tex>\sum_{}^{}1/n</tex>==<br />
<br />
{{Теорема<br />
|id=th2<br />
|statement=<br />
Ряд <tex>\sum_{}^{}1/n</tex> расходится.<br />
|proof=<br />
<tex>\sum_{n=1}^\infty\frac{1}{n} = \prod_{p} {(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots)}</tex>, где <tex>p</tex> — простое. Таким образом, получаем все числа по одному разу после раскрытия скобок.<br />
}}<br />
Заметим для некоторого <tex>k</tex>: <tex>\sum_{p \le k}^{}{(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots)} \ge \sum_{n \le k} \frac{1}{n}</tex>.<br />
Теперь, пользуясь выражением <tex> \ln(1+x) \approx x + o(x) </tex> и логарифмируя, выводим:<br />
<tex> \sum_{p} {\ln(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots)} \approx \sum_{p} { (\frac{1}{p} + \frac{1}{p^2} + \cdots)} \le \frac{c}{p^2} </tex> - расходится.<br />
<br />
==Теорема о расходимости ряда <tex>\sum_{}^{}1/p</tex>==<br />
<br />
{{Теорема<br />
|id=th3<br />
|statement=<br />
Ряд <tex>\sum_{}^{}1/p</tex>, где <tex>p</tex> - простое, расходится.<br />
|proof=<br />
Работая в условиях [[#th2|предыдущей теоремы]], продолжаем:<br />
<tex> \ln(1+x) \le x</tex>, тогда <tex> \sum_{}^{} {\ln(1 + \frac{1}{p} + \cdots)} \le \sum_{}^{} {( \frac{1}{p} + \frac{1}{p^2} + \cdots)}</tex>.<br />
Финально: <tex> \sum_{}^{} \frac{1}{p} \ge \sum_{}^{} {[\ln(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots) - \frac{c}{p^2}]} </tex> - расходится.<br />
}}<br />
<br />
[[Категория: Классы чисел]]</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B8&diff=8998Основная теорема арифметики2011-05-28T17:50:54Z<p>Mamoshkin.Arseny: /* Собственно теорема */</p>
<hr />
<div>==Основная теорема арифметики==<br />
<br />
===Лемма Евклида===<br />
<br />
{{Лемма<br />
|id=th1<br />
|statement=<br />
Если простое число <tex>p</tex> делит без остатка произведение двух целых чисел <tex>x\cdot y</tex>, то <tex>p</tex> делит <tex>x</tex> или <tex>y</tex>.<br />
|proof=<br />
Пусть <tex>x\cdot y</tex> делится на <tex>p</tex>, но <tex>x</tex> не делится на <tex>p</tex>. Тогда <tex>x</tex> и <tex>p</tex> — взаимно простые, следовательно, найдутся такие целые числа <tex>u</tex> и <tex>v</tex>, что<br />
: <tex>x\cdot u+p\cdot v=1</tex> ([[Наибольший общий делитель|соотношение Безу]]).<br />
Умножая обе части на <tex>y</tex>, получаем<br />
: <tex>(x\cdot y)\cdot u+p\cdot v\cdot y=y.</tex><br />
Оба слагаемых левой части делятся на <tex>p</tex>, значит, и правая часть делится на <tex>p</tex>, ч.т.д.<br />
}}<br />
<br />
===Собственно теорема===<br />
<br />
{{Теорема<br />
|id=th666<br />
|statement=<br />
Каждое натуральное число <tex>n>1</tex> представляется в виде <tex>n=p_1\cdot\dots\cdot p_k</tex>, где <tex>p_1,\dots,p_k</tex> — [[простые числа]], причём такое представление единственно с точностью до порядка следования сомножителей.<br />
|proof=<br />
'''Существование'''. Пусть <tex>n</tex> — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если <tex>n</tex> составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, значит, <tex>n</tex> тоже является произведением простых чисел. Противоречие.<br />
<br />
'''Единственность'''. Пусть <tex>n</tex> — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть <tex>p</tex> — любой из сомножителей в любом из двух разложений. Если <tex>p</tex> входит и в другое разложение, мы можем сократить оба разложения на <tex>p</tex> и получить два разных разложения числа <tex>n/p</tex>, что невозможно. А если <tex>p</tex> не входит в другое разложение, то одно из произведений делится на <tex>p</tex>, а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству.<br />
}}<br />
<br />
[[Категория: Классы чисел]]</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B8&diff=8997Основная теорема арифметики2011-05-28T17:48:56Z<p>Mamoshkin.Arseny: /* Собственно теорема */</p>
<hr />
<div>==Основная теорема арифметики==<br />
<br />
===Лемма Евклида===<br />
<br />
{{Лемма<br />
|id=th1<br />
|statement=<br />
Если простое число <tex>p</tex> делит без остатка произведение двух целых чисел <tex>x\cdot y</tex>, то <tex>p</tex> делит <tex>x</tex> или <tex>y</tex>.<br />
|proof=<br />
Пусть <tex>x\cdot y</tex> делится на <tex>p</tex>, но <tex>x</tex> не делится на <tex>p</tex>. Тогда <tex>x</tex> и <tex>p</tex> — взаимно простые, следовательно, найдутся такие целые числа <tex>u</tex> и <tex>v</tex>, что<br />
: <tex>x\cdot u+p\cdot v=1</tex> ([[Наибольший общий делитель|соотношение Безу]]).<br />
Умножая обе части на <tex>y</tex>, получаем<br />
: <tex>(x\cdot y)\cdot u+p\cdot v\cdot y=y.</tex><br />
Оба слагаемых левой части делятся на <tex>p</tex>, значит, и правая часть делится на <tex>p</tex>, ч.т.д.<br />
}}<br />
<br />
===Собственно теорема===<br />
<br />
{{Теорема<br />
|id=th666<br />
|statement=<br />
Каждое натуральное число <math>n>1</math> представляется в виде <math>n=p_1\cdot\dots\cdot p_k</math>, где <math>p_1,\dots,p_k</math> — [[простые числа]], причём такое представление единственно с точностью до порядка следования сомножителей.<br />
|proof=<br />
'''Существование'''. Пусть <math>n</math> — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если <math>n</math> составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, значит, <math>n</math> тоже является произведением простых чисел. Противоречие.<br />
<br />
'''Единственность'''. Пусть <math>n</math> — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть <math>p</math> — любой из сомножителей в любом из двух разложений. Если <math>p</math> входит и в другое разложение, мы можем сократить оба разложения на <math>p</math> и получить два разных разложения числа <math>n/p</math>, что невозможно. А если <math>p</math> не входит в другое разложение, то одно из произведений делится на <math>p</math>, а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству.<br />
}}<br />
<br />
[[Категория: Классы чисел]]</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B8&diff=8996Основная теорема арифметики2011-05-28T17:48:17Z<p>Mamoshkin.Arseny: /* Лемма Евклида */</p>
<hr />
<div>==Основная теорема арифметики==<br />
<br />
===Лемма Евклида===<br />
<br />
{{Лемма<br />
|id=th1<br />
|statement=<br />
Если простое число <tex>p</tex> делит без остатка произведение двух целых чисел <tex>x\cdot y</tex>, то <tex>p</tex> делит <tex>x</tex> или <tex>y</tex>.<br />
|proof=<br />
Пусть <tex>x\cdot y</tex> делится на <tex>p</tex>, но <tex>x</tex> не делится на <tex>p</tex>. Тогда <tex>x</tex> и <tex>p</tex> — взаимно простые, следовательно, найдутся такие целые числа <tex>u</tex> и <tex>v</tex>, что<br />
: <tex>x\cdot u+p\cdot v=1</tex> ([[Наибольший общий делитель|соотношение Безу]]).<br />
Умножая обе части на <tex>y</tex>, получаем<br />
: <tex>(x\cdot y)\cdot u+p\cdot v\cdot y=y.</tex><br />
Оба слагаемых левой части делятся на <tex>p</tex>, значит, и правая часть делится на <tex>p</tex>, ч.т.д.<br />
}}<br />
<br />
===Собственно теорема===<br />
<br />
{{Теорема<br />
|id=th666<br />
|statement=<br />
Каждое натуральное число <math>n>1</math> представляется в виде <math>n=p_1\cdot\dots\cdot p_k</math>, где <math>p_1,\dots,p_k</math> — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.<br />
|proof=<br />
'''Существование'''. Пусть <math>n</math> — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если <math>n</math> составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, значит, <math>n</math> тоже является произведением простых чисел. Противоречие.<br />
<br />
'''Единственность'''. Пусть <math>n</math> — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть <math>p</math> — любой из сомножителей в любом из двух разложений. Если <math>p</math> входит и в другое разложение, мы можем сократить оба разложения на <math>p</math> и получить два разных разложения числа <math>n/p</math>, что невозможно. А если <math>p</math> не входит в другое разложение, то одно из произведений делится на <math>p</math>, а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству.<br />
}}<br />
<br />
[[Категория: Классы чисел]]</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B8%D0%B9_%D0%BE%D0%B1%D1%89%D0%B8%D0%B9_%D0%B4%D0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C&diff=8995Наибольший общий делитель2011-05-28T17:45:55Z<p>Mamoshkin.Arseny: /* Стандартный алгоритм Евклида */</p>
<hr />
<div>==Наибольший общий делитель как максимальное число, делящее два данных числа==<br />
<br />
{{Определение<br />
|definition=<br />
'''Наибольшим общим делителем''' ('''НОД''') для двух целых чисел ''m'' и ''n'' называется наибольший из их общих делителей.<br />
}}<br />
Пример: для чисел 70 и 105 наибольший общий делитель равен 35.<br />
<br />
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел ''m'' или ''n'' не ноль.<br />
<br />
Возможные обозначения наибольшего общего делителя чисел ''m'' и ''n'':<br />
* НОД(''m'', ''n'')<br />
* (''m'', ''n'')<br />
* gcd(''m'', ''n'') (от англ. Greatest Common Divisor)<br />
<br />
Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.<br />
<br />
==Алгоритм Евклида==<br />
<br />
===Стандартный алгоритм Евклида===<br />
<br />
Пусть <tex>a</tex> и <tex>b</tex> — целые числа, не равные одновременно нулю, и последовательность чисел<br />
: <tex> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</tex><br />
определена тем, что каждое <tex>r_k</tex> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть<br />
: <tex>a = bq_0 + r_1</tex><br />
: <tex>b = r_1q_1 + r_2</tex><br />
: <tex>r_1 = r_2q_2 + r_3</tex><br />
: <tex>\cdots</tex><br />
: <tex>r_{k-2} = r_{k-1} q_{k-1} + r_k</tex><br />
: <tex>\cdots</tex><br />
: <tex>r_{n-1} = r_n q_n</tex><br />
<br />
Тогда НОД(''a'',''b''), наибольший общий делитель <tex>a</tex> и <tex>b</tex>, равен<br />
<tex>r_n</tex>, последнему ненулевому члену этой последовательности.<br />
<br />
'''Существование''' таких <tex>r_1, r_2, ...</tex>, то есть возможность деления с остатком <tex>m</tex> на <tex>n</tex> для любого целого <tex>m</tex> и целого <tex>n\ne 0</tex>, доказывается индукцией по ''m''.<br />
<br />
'''Корректность''' этого алгоритма вытекает из следующих двух утверждений:<br />
{{Лемма<br />
|id=l1<br />
|statement=Пусть <tex>a = bq + r</tex>, тогда <tex>\gcd (a,b) = \gcd (b,r).</tex><br />
|proof=Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда <tex> a = t_1 k </tex> ; <tex> b = t_2 k; </tex> где <tex> t_1 </tex> и <tex> t_2 </tex> — целые числа из определения.<br />
# Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а <tex>r = a - bq = (t_1 - t_2 q)k </tex> (выражение в скобках есть целое число, следовательно, k делит r без остатка)<br />
# Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.<br />
# Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.<br />
# В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.<br />
}}<br />
{{Лемма<br />
|statement=<tex>\gcd (0,r) = r</tex> для любого ненулевого <tex>r.</tex><br />
}}<br />
<br />
Проще сформулировать алгоритм Евклида так: если даны натуральные числа <tex>a</tex> и <tex>b</tex> и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.<br />
<br />
===Расширенный алгоритм Евклида===<br />
<br />
Формулы для <tex>r_i</tex> могут быть переписаны следующим образом:<br />
<br />
: <tex>r_1 = a + b(-q_0)</tex><br />
: <tex>r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)</tex><br />
: <tex>\cdots</tex><br />
: <tex>\gcd (a,b) = r_n = as + bt</tex><br />
здесь ''s'' и ''t'' целые. Это представление наибольшего общего делителя называется '''соотношением Безу''', а числа ''s'' и ''t'' — '''коэффициентами Безу'''. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.<br />
<br />
==== Связь с цепными дробями ====<br />
<br />
Отношение <tex>a/b</tex> допускает представление в виде цепной дроби:<br />
: <tex>\frac ab=[q_0; q_1, q_2,\cdots,q_n]</tex>.<br />
<br />
При этом цепная дробь без последнего члена равна отношению коэффициентов Безу <tex>t/s</tex>, взятому со знаком минус:<br />
: <tex>[q_0; q_1, q_2,\cdots,q_{n-1}] = -\frac ts</tex>.<br />
<br />
[[Категория: Классы чисел]]</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0&diff=8994Натуральные числа2011-05-28T17:44:31Z<p>Mamoshkin.Arseny: /* Деление чисел с остатком */</p>
<hr />
<div>{{Требует доработки<br />
|item1=('''Исправлено''') Пожалуйста, прочитайте статью [[Обсуждение:Алгоритмы алгебры и теории чисел]]<br />
}}<br />
<br />
==Деление чисел с остатком==<br />
<br />
{{Определение<br />
|definition=<br />
Если натуральное число <tex>n\,</tex> не делится на натуральное число <tex>m\,</tex>, т.е. не существует такого натурального числа <tex>k\,</tex> , что <tex>n = m\,k,</tex> то деление называется '''делением с остатком'''.<br />
}}<br />
<br />
'''Формула деления с остатком''': <tex>n = m\,k + r,</tex> где <tex>n\,</tex> — делимое, <tex>m\,</tex> — делитель, <tex>k\,</tex> — частное, <tex>r\,</tex> — остаток, причем <tex>0\leqslant r < b </tex><br />
<br />
:Любое число можно представить в виде: <tex>n = 2\,k + r,</tex> , где остаток <tex>r\,</tex> = <tex>0\,</tex> или <tex>r\,</tex> = <tex>1\,</tex><br />
<br />
:Любое число можно представить в виде: <tex>n = 4\,k + r,</tex> , где остаток <tex>r\,</tex> = <tex>0\,</tex> или <tex>r\,</tex> = <tex>1\,</tex> или <tex>r\,</tex> = <tex>2\,</tex> или <tex>r\,</tex> = <tex>3\,</tex><br />
<br />
:Любое число можно представить в виде: <tex>n = m\,k + r,</tex> , где остаток <tex>r\,</tex> принимает значения от <tex>0\,</tex> до <tex>(m-1)\,</tex><br />
<br />
==Принцип индукции, существование наименьшего числа в любом множестве натуральных чисел==<br />
<br />
===Индукция===<br />
<br />
Формулировка '''принципа математической индукции''':<br />
<br />
:Пусть имеется последовательность утверждений <tex>A_1, A_2, A_3, \ldots</tex> И пусть первое утверждение <tex>A_1</tex> верно и мы умеем доказать, что из верности утверждения <tex>A_k</tex> следует верность <tex>A_{k + 1}</tex>. Тогда все утверждения в этой последовательности верны.<br />
<br />
Верность этого метода доказательства вытекает из так называемой '''аксиомы индукции''', пятой из аксиом Пеано, которые определяют натуральные числа. Рассмотрение аксиом Пеано выходит за рамки этой статьи.<br />
<br />
Также существует '''принцип полной математической индукции'''. Вот его строгая формулировка:<br />
<br />
:Пусть имеется последовательность утверждений <tex>A_1, A_2, A_3, \ldots</tex>. И пусть мы умеем доказать, что из верности утверждения <tex>A_1, A_2, A_3, \ldots, A_k</tex> следует верность <tex>A_{k + 1}</tex>. Тогда все утверждения в этой последовательности верны.<br />
<br />
===Существование наименьшего элемента===<br />
<br />
Аксиому индукции можно заменить на аксиому существования минимума, и доказать аксиому индукции как теорему.<br />
<br />
{{Теорема<br />
|id=th1<br />
|about=О существовании минимума<br />
|statement=<br />
Для любого подмножества натурального ряда всегда существует минимум.<br />
Т. е. <tex>\forall A \subset \mathbb N, A \ne \varnothing, \exists x \in A: \forall y \in A x \leqslant y</tex><br />
|proof=<br />
Если <tex>1 \in A</tex>, то <tex>1</tex> и есть '''min'''. Иначе <tex>1 \notin A</tex><br />
Если <tex>2 \in A</tex>, то <tex>2</tex> и есть '''min'''. Иначе <tex>2 \notin A</tex><br />
<tex>P(n)</tex> - все элементы <tex>\leqslant n</tex> не лежат в <tex>A</tex> <tex>\Rightarrow</tex> <tex>P(1) ... P(n)</tex> - верно и <tex>P(n+1)</tex> - верно (т.к. он был бы '''min''') <tex>\Rightarrow</tex> в <tex>A</tex> ничего не лежит. Противоречие.<br />
}}<br />
<br />
[[Категория: Классы чисел]]</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0&diff=8993Натуральные числа2011-05-28T17:43:26Z<p>Mamoshkin.Arseny: /* Существование наименьшего элемента */</p>
<hr />
<div>{{Требует доработки<br />
|item1=('''Исправлено''') Пожалуйста, прочитайте статью [[Обсуждение:Алгоритмы алгебры и теории чисел]]<br />
}}<br />
<br />
==Деление чисел с остатком==<br />
<br />
{{Определение<br />
|definition=<br />
Если натуральное число <tex>n\,</tex> не делится на натуральное число <tex>m\,</tex>, т.е. не существует такого натурального числа <tex>k\,</tex> , что <tex>n = m\,k,</tex> то деление называется '''делением с остатком'''.<br />
}}<br />
<br />
'''Формула деления с остатком''': <tex>n = m\,k + r,</tex> где <tex>n\,</tex> - делимое, <tex>m\,</tex> - делитель, <tex>k\,</tex> - частное, <tex>r\,</tex> - остаток, причем <tex>0\leqslant r < b </tex><br />
<br />
:Любое число можно представить в виде: <tex>n = 2\,k + r,</tex> , где остаток <tex>r\,</tex> = <tex>0\,</tex> или <tex>r\,</tex> = <tex>1\,</tex><br />
<br />
:Любое число можно представить в виде: <tex>n = 4\,k + r,</tex> , где остаток <tex>r\,</tex> = <tex>0\,</tex> или <tex>r\,</tex> = <tex>1\,</tex> или <tex>r\,</tex> = <tex>2\,</tex> или <tex>r\,</tex> = <tex>3\,</tex><br />
<br />
:Любое число можно представить в виде: <tex>n = m\,k + r,</tex> , где остаток <tex>r\,</tex> принимает значения от <tex>0\,</tex> до <tex>(m-1)\,</tex><br />
<br />
==Принцип индукции, существование наименьшего числа в любом множестве натуральных чисел==<br />
<br />
===Индукция===<br />
<br />
Формулировка '''принципа математической индукции''':<br />
<br />
:Пусть имеется последовательность утверждений <tex>A_1, A_2, A_3, \ldots</tex> И пусть первое утверждение <tex>A_1</tex> верно и мы умеем доказать, что из верности утверждения <tex>A_k</tex> следует верность <tex>A_{k + 1}</tex>. Тогда все утверждения в этой последовательности верны.<br />
<br />
Верность этого метода доказательства вытекает из так называемой '''аксиомы индукции''', пятой из аксиом Пеано, которые определяют натуральные числа. Рассмотрение аксиом Пеано выходит за рамки этой статьи.<br />
<br />
Также существует '''принцип полной математической индукции'''. Вот его строгая формулировка:<br />
<br />
:Пусть имеется последовательность утверждений <tex>A_1, A_2, A_3, \ldots</tex>. И пусть мы умеем доказать, что из верности утверждения <tex>A_1, A_2, A_3, \ldots, A_k</tex> следует верность <tex>A_{k + 1}</tex>. Тогда все утверждения в этой последовательности верны.<br />
<br />
===Существование наименьшего элемента===<br />
<br />
Аксиому индукции можно заменить на аксиому существования минимума, и доказать аксиому индукции как теорему.<br />
<br />
{{Теорема<br />
|id=th1<br />
|about=О существовании минимума<br />
|statement=<br />
Для любого подмножества натурального ряда всегда существует минимум.<br />
Т. е. <tex>\forall A \subset \mathbb N, A \ne \varnothing, \exists x \in A: \forall y \in A x \leqslant y</tex><br />
|proof=<br />
Если <tex>1 \in A</tex>, то <tex>1</tex> и есть '''min'''. Иначе <tex>1 \notin A</tex><br />
Если <tex>2 \in A</tex>, то <tex>2</tex> и есть '''min'''. Иначе <tex>2 \notin A</tex><br />
<tex>P(n)</tex> - все элементы <tex>\leqslant n</tex> не лежат в <tex>A</tex> <tex>\Rightarrow</tex> <tex>P(1) ... P(n)</tex> - верно и <tex>P(n+1)</tex> - верно (т.к. он был бы '''min''') <tex>\Rightarrow</tex> в <tex>A</tex> ничего не лежит. Противоречие.<br />
}}<br />
<br />
[[Категория: Классы чисел]]</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=7026Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T20:45:57Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Дана упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
|proof=<br />
<br />
Полуразрешимость: возможно взять по возрастанию все возможные наборы индексов, применить конкатенацию и сравнить полученные строки. При совпадении задача будет решена, иначе - программа зависнет.<br />
<br />
Докажем неразрешимость:<br />
<br />
Сначала приведём доказательства для случая, когда <tex>i_1 = 1</tex>, т.е. для '''МПСП'''.<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
Считаем, что '''Машина Тьюринга''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Таким образом выводятся следующие последовательности: <tex>\$ A_0 \$ \ldots \$ A_k \$</tex> и <tex>\$ A_i \ldots</tex> - мгновенное описание.<br />
<br />
Если <tex>MT</tex> остановится, нужно добиться того, чтобы строка закончилась. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> построим следующую пару <tex>(a_i=c, b_i = c), (a_i = \$, b = \$)</tex>.<br />
<tex>b</tex> должно сойтись с соответствующей <tex>a</tex> в предыдущем мгновенном описании.<br />
<br />
Соответственно <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = \langle p, d, \rightarrow \rangle</tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = \langle p, d, \leftarrow \rangle </tex>.<br />
Аналогично следует поступить и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>a</tex>: <tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<br />
<tex>b</tex>: <tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
<br />
Требуется добиться остановки. Для этого добавляется далее:<br />
* <tex>a = \#_y</tex>, <tex>b = \#_y c</tex><br />
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex><br />
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex><br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Теперь необходимо начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, в которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=7022Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T20:39:30Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Дана упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Проблема соответствий Поста неразрешима.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
|proof=<br />
<br />
Полуразрешимость: возможно взять по возрастанию все возможные наборы индексов, применить конкатенацию и сравнить полученные строки. При совпадении задача будет решена, иначе - программа зависнет.<br />
<br />
Докажем неразрешимость:<br />
<br />
Сначала приведём доказательства для случая, когда <tex>i_1 = 1</tex>, т.е. для '''МПСП'''. Считаем, что '''Машина Тьюринга''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Таким образом выводятся следующие последовательности: <tex>\$ A_0 \$ \ldots \$ A_k \$</tex> и <tex>\$ A_i \ldots</tex> - мгновенное описание.<br />
<br />
Если <tex>MT</tex> остановится, нужно добиться того, чтобы строка закончилась. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> построим следующую пару <tex>(a_i=c, b_i = c), (a_i = \$, b = \$)</tex>.<br />
<tex>b</tex> должно сойтись с соответствующей <tex>a</tex> в предыдущем мгновенном описании.<br />
<br />
Соответственно <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = \langle p, d, \rightarrow \rangle</tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = \langle p, d, \leftarrow \rangle </tex>.<br />
Аналогично следует поступить и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>a</tex>: <tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<br />
<tex>b</tex>: <tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
<br />
Требуется добиться остановки. Для этого добавляется далее:<br />
* <tex>a = \#_y</tex>, <tex>b = \#_y c</tex><br />
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex><br />
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex><br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Теперь необходимо начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, в которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=7019Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T20:36:01Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Дана упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Проблема соответствий Поста неразрешима.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
|proof=<br />
<br />
Полуразрешимость: возможно взять по возрастанию все возможные наборы индексов, применить конкатенацию и сравнить полученные строки. При совпадении задача будет решена, иначе - программа зависнет.<br />
<br />
Докажем неразрешимость:<br />
<br />
Сначала приведём доказательства для случая, когда <tex>i_1 = 1</tex>, т.е. для '''МПСП'''. Считаем, что '''Машина Тьюринга''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Таким образом выводятся следующие последовательности: <tex>\$ A_0 \$ \ldots \$ A_k \$</tex> и <tex>\$ A_i \ldots</tex> - мгновенное описание.<br />
<br />
Если <tex>MT</tex> остановится, нужно добиться того, чтобы строка закончилась. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> построим следующую пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<tex>b</tex> должно сойтись с соответствующей <tex>a</tex> в предыдущем мгновенном описании.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = \langle p, d, \rightarrow \rangle</tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = \langle p, d, \leftarrow \rangle </tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>a</tex>: <tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<br />
<tex>b</tex>: <tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
<br />
т.е. добавляем элементы и находим соответствующие переходы.<br />
<br />
Требуется добиться остановки. Для этого добавляется далее:<br />
* <tex>a = \#_y</tex>, <tex>b = \#_y c</tex><br />
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex><br />
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex><br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6974Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T20:06:50Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Дана упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Проблема соответствий Поста неразрешима.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
|proof=<br />
<br />
Полуразрешимость: Возьмём по возрастанию все возможные наборы индексов, применим конкатенацию и сравним. Сошлось - задача решена, иначе - программа зависла.<br />
<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринга''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.<br />
<br />
Если <tex>MT</tex> остановится, добьёмся того, чтобы строка закончилось. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<tex>b</tex> должно сойтись с соответствующей <tex>a</tex> в предыдущем мгновенном описании.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = \langle p, d, \rightarrow \rangle</tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = \langle p, d, \leftarrow \rangle </tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>a</tex>: <tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<br />
<tex>b</tex>: <tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
<br />
т.е. добавляем элементы и находим соответствующие переходы.<br />
<br />
Требуется добиться остановки. Для этого добавляется далее:<br />
* <tex>a = \#_y</tex>, <tex>b = \#_y c</tex><br />
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex><br />
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex><br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6966Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T20:03:28Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Дана упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Проблема соответствий Поста неразрешима.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
|proof=<br />
<br />
Полуразрешимость: Возьмём по возрастанию все возможные наборы индексов, применим конкатенацию и сравним. Сошлось - задача решена, иначе - программа зависла.<br />
<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринга''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.<br />
<br />
Если <tex>MT</tex> остановится, добьёмся того, чтобы строка закончилось. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<tex>b</tex> должно сойтись с соответствующей <tex>a</tex> в предыдущем мгновенном описании.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = <p, d, \rightarrow></tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>a</tex>: <tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<br />
<tex>b</tex>: <tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
<br />
т.е. добавляем элементы и находим соответствующие переходы.<br />
<br />
Требуется добиться остановки. Для этого добавляется далее:<br />
* <tex>a = \#_y</tex>, <tex>b = \#_y c</tex><br />
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex><br />
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex><br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6883Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T18:30:56Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
(Не существует примера неразрешимого языка, который является языком программ)<br />
|proof=<br />
<br />
Полуразрешимость: Возьмём по возрастанию все возможные наборы индексов, применим конкатинацию и сравним. Сошлось - задача решена, иначе - программа зависла.<br />
<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.<br />
<br />
Если <tex>MT</tex> остановится, добьёмся того, чтобы строка закончилось. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<tex>b</tex> должно сойтись с соответствующей <tex>a</tex> в предыдущем мгновенном описании.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = <p, d, \rightarrow></tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>a</tex>: <tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<br />
<tex>b</tex>: <tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
<br />
т.е. добавляем элементы и находим соответствующие переходы.<br />
<br />
Требуется добиться остановки. Для этого добавляется далее:<br />
* <tex>a = \#_y</tex>, <tex>b = \#_y c</tex><br />
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex><br />
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex><br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6864Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T18:02:29Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
(Не существует примера неразрешимого языка, который является языком программ)<br />
|proof=<br />
<br />
Полуразрешимость: Возьмём по возрастанию все возможные наборы индексов, применим конкатинацию и сравним. Сошлось - задача решена, иначе - программа зависла.<br />
<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.<br />
<br />
Если <tex>MT</tex> остановится, добьёмся того, чтобы строка закончилось. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<tex>b</tex> должно сойтись с соответствующей <tex>a</tex> в предыдущем мгновенном описании.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = <p, d, \rightarrow></tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>a</tex>: <tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<br />
<tex>b</tex>: <tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
<br />
т.е. добавляем элементы и находим соответствующие переходы.<br />
<br />
Требуется добиться остановки. Для этого добавляется далее:<br />
* <tex>a = \#_y</tex>, <tex>b = \#_y c</tex><br />
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex><br />
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex><br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6863Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T18:01:21Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
(Не существует примера неразрешимого языка, который является языком программ)<br />
|proof=<br />
<br />
Полуразрешимость: Возьмём по возрастанию все возможные наборы индексов, применим конкатинацию и сравним. Сошлось - задача решена, иначе - программа зависла.<br />
<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.<br />
<br />
Если <tex>MT</tex> остановится, добьёмся того, чтобы строка закончилось. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<tex>b</tex> должно сойтись с соответствующей <tex>a</tex> в предыдущем мгновенном описании.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = <p, d, \rightarrow></tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<br />
<tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
<br />
т.е. добавляем элементы и находим соответствующие переходы.<br />
<br />
Требуется добиться остановки. Для этого добавляется далее:<br />
* <tex>a = \#_y</tex>, <tex>b = \#_y c</tex><br />
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex><br />
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex><br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6844Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T17:28:58Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
(Не существует примера неразрешимого языка, который является языком программ)<br />
|proof=<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex>. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.<br />
<br />
Если <tex>MT</tex> остановится, добьёмся того, что зак. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = <p, d, \rightarrow></tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<br />
<tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
<br />
т.е. добавляем элементы и находим соответствующие переходы.<br />
<br />
Добавим далее:<br />
* <tex>a = \#_y</tex>, <tex>b = \#_y c</tex><br />
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex><br />
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex><br />
}}<br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6843Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T17:28:37Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
(Не существует примера неразрешимого языка, который является языком программ)<br />
|proof=<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex>. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.<br />
<br />
Если <tex>MT</tex> остановится, добьёмся того, что зак. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = <p, d, \rightarrow></tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<br />
<tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
т.е. добавляем элементы и находим соответствующие переходы.<br />
<br />
Добавим далее:<br />
* <tex>a = \#_y</tex>, <tex>b = \#_y c</tex><br />
* или <tex>a = \#_y</tex>, <tex>b = c \#_y</tex><br />
* или <tex>a = \$</tex>, <tex>b = \#_y \$ \$</tex><br />
}}<br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6841Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T17:25:42Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
(Не существует примера неразрешимого языка, который является языком программ)<br />
|proof=<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex>. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.<br />
<br />
Если <tex>MT</tex> остановится, добьёмся того, что зак. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = <p, d, \rightarrow></tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
Как может быть устроен префикс решения '''МПСП''':<br />
<br />
<tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex><br />
<tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex><br />
т.е. добавляем элементы и находим соответствующие переходы.<br />
<br />
Добавим далее:<br />
* <tex>a = \#_y, b = \#_y c</tex><br />
* или <tex>a = \#_y, b = c \#_y</tex><br />
* или <tex>a = \$, b = \#_y \$ \$</tex><br />
}}<br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''':<br />
<br />
'''Известно''':<br />
* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''<br />
* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП'''<br />
'''Необходимо''':<br />
* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''<br />
<br />
Возьмём экземпляр задачи МПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = n + 1</tex><br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
<br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
<br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6815Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T16:51:33Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
(Не существует примера неразрешимого языка, который является языком программ)<br />
|proof=<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex>. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.<br />
<br />
Если <tex>MT</tex> остановится, добъёмся того, что зак. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = <p, d, \rightarrow></tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
<br />
}}<br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса:<br />
'''Верно''':<br />
* умеем '''1ПСП''' <tex>\Rightarrow</tex> умеем '''ПСП'''<br />
* не умеем '''1ПСП''' <tex>\Leftarrow</tex>не умеем '''ПСП'''<br />
'''Необходимо''':<br />
* не умеем '''1ПСП''' <tex>\Rightarrow</tex> не умеем '''ПСП'''<br />
<br />
Возьмём экземпляр задачи 1ПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6812Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T13:53:29Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
(Не существует примера неразрешимого языка, который является языком программ)<br />
|proof=<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex>. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.<br />
<br />
Если <tex>MT</tex> остановится, добъёмся того, что зак. Иначе строки будут расти до бесконечности, но никогда не закончатся.<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.<br />
<br />
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = <p, d, \rightarrow></tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.<br />
<br />
<br />
}}<br />
<br />
Теперь остаётся избавиться от требования фиксированного первого индекса:<br />
'''Верно''':<br />
* умеем '''1ПСП''' <tex>\Rightarrow</tex> умеем '''ПСП'''<br />
* не умеем '''1ПСП''' <tex>\Leftarrow</tex>не умеем '''ПСП'''<br />
'''Необходимо''':<br />
* не умеем '''1ПСП''' <tex>\Rightarrow</tex> не умеем '''ПСП'''<br />
<br />
Возьмём экземпляр задачи 1ПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6811Примеры неразрешимых задач: проблема соответствий Поста2011-01-15T11:00:16Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
(Не существует пример неразрешимого языка, который является языком программ)<br />
|proof=<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''МТ''' никогда не приходит в '''N'''. '''MT''': <tex>(m, \omega)</tex>. Задача <tex>m(\omega) = y</tex> не разрешима. Предположим, что мы умеем решать '''ПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
<tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ \ldots</tex><br />
<br />
Если '''MT''' остановился, добъёмся того, что зак. Иначе стр будут расти до бесконечности, но никогда не зак<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex><br />
<br />
<tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex>, <tex>\delta(q, c) = <p, d, \rightarrow></tex><br />
<br />
<tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex><br />
<tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично переход на месте, или считаем, что таких не бывает.<br />
}}<br />
<br />
'''Верно''':<br />
* умеем '''1ПСП''' <tex>\Rightarrow</tex> умеем '''ПСП'''<br />
* не умеем '''1ПСП''' <tex>\Leftarrow</tex>не умеем '''ПСП'''<br />
'''Надо''':<br />
* не умеем '''1ПСП''' <tex>\Rightarrow</tex> не умеем '''ПСП'''<br />
<br />
Возьмём экземпляр задачи 1ПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6204Примеры неразрешимых задач: проблема соответствий Поста2010-12-23T10:47:35Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Язык имеющих решение проблем соответствий поста перечислим, но не разрешим.<br />
(Не существует пример неразрешимого языка, который является языком программ)<br />
|proof=<br />
Докажем неразрешимость:<br />
<br />
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''МТ''' никогда не приходит в '''N'''. '''MT''': <tex>(m, \omega)</tex>. Задача <tex>m(\omega) = y</tex> не разрешима. Предположим, что мы умеем решать '''ПСП'''.<br />
<br />
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.<br />
<tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ \ldots</tex><br />
<br />
Если '''MT''' остановился, добъёмся того, что зак. Иначе стр будут расти до бесконечности, но никогда не зак<br />
<br />
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex><br />
<br />
<tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex>, <tex>\delta(q, c) = <p, d, \rightarrow></tex><br />
<br />
<tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex><br />
<tex>\delta (a, c) = <p, d, \leftarrow></tex>.<br />
Аналогично переход на месте, или считаем, что таких не бывает.<br />
}}<br />
<br />
'''Верно''':<br />
* умеем '''1ПСП''' <tex>\Rightarrow</tex> умеем '''ПСП'''<br />
* не умеем '''1ПСП''' <tex>\Leftarrow</tex>не умеем '''ПСП'''<br />
'''Надо''':<br />
* не умеем '''1ПСП''' <tex>\Rightarrow</tex> не умеем '''ПСП'''<br />
<br />
Возьмём экземпляр задачи 1ПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.<br />
<br />
<tex>i = 2 \ldots n </tex>:<br />
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex><br />
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><br />
<tex>i = 1</tex><br />
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex><br />
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><br />
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.<br />
* <tex>a_{n+1} = \$</tex><br />
* <tex>b_{n+1} = *\$</tex><br />
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6194Примеры неразрешимых задач: проблема соответствий Поста2010-12-23T09:40:06Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Постовской системой соответствия над алфавитом <tex>\Sigma</tex>''' называется упорядоченная пара конечных последовательностей <tex>(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))</tex>, где <tex>x_i \in \Sigma ^*</tex> и <tex>x_i \in \Sigma ^*</tex> для всех '''i'''.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Решением постовской системы соответствия <tex>(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))</tex>''' называется непустая последовательность индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющая условию <tex><br />
x_{i_1} \ldots x_{i_k} = y_{i_1} \ldots y_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j.<br />
}}<br />
===Пример===<br />
Пусть <tex>\Sigma = \{ a , b , c \}</tex>. Рассмотрим постовскую систему соответствия <tex>((aab, a, caa),(a, aa, bc))</tex>.<br />
Последовательность <tex>(2,1,3,2,2)</tex> является решением этой системы, так как <tex>a \cdot aab \cdot caa \cdot a \cdot a =<br />
aa \cdot a \cdot bc \cdot aa \cdot aa</tex>.<br />
{{Определение<br />
|definition=<br />
'''Проблемой соответствий Поста (ПСП)''' (Post correspondence problem) называется проблема нахождения алгоритма, выясняющего для каждой постовской системы соответствия, существует ли решение этой системы.<br />
}}<br />
===Модифицированная проблема соответствий поста===<br />
Рассмотрим промежуточную версию ПСП, которая называется '''модифицированной проблемой соответствий Поста''', или '''МПСП'''. В <br />
модифицированной ПСП на решение накладывается дополнительное требование, чтобы первой парой в решении была пара первых элементов списков '''А''' и '''В'''. Более формально, экземпляр МПСП состоит из двух списков <tex>A = ( x_1 , \ldots , x_k )</tex> и <tex>B = ( y_k , \ldots , y_k )</tex>, и решением является последовательность из О или нескольких целых чисел <tex>i_1, \ldots, i_m</tex> при которой <tex>x_1 x_{i_1} \ldots x_{i_k} = y_1 y_{i_1} \ldots y_{i_m}</tex><br />
<br />
{{Теорема<br />
|statement=<br />
Пусть <tex>| \Sigma | \geq 2</tex>. Тогда не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом <tex>\Sigma</tex> узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)<br />
|proof=<br />
<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6189Примеры неразрешимых задач: проблема соответствий Поста2010-12-22T23:20:55Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Постовской системой соответствия над алфавитом <tex>\Sigma</tex>''' называется упорядоченная пара конечных последовательностей <tex>(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))</tex>, где <tex>x_i \in \Sigma ^*</tex> и <tex>x_i \in \Sigma ^*</tex> для всех '''i'''.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Решением постовской системы соответствия <tex>(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))</tex>''' называется непустая последовательность индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющая условию <tex><br />
x_{i_1} \ldots x_{i_k} = y_{i_1} \ldots y_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j.<br />
}}<br />
===Пример===<br />
Пусть <tex>\Sigma = \{ a , b , c \}</tex>. Рассмотрим постовскую систему соответствия <tex>((aab, a, caa),(a, aa, bc))</tex>.<br />
Последовательность <tex>(2,1,3,2,2)</tex> является решением этой системы, так как <tex>a \cdot aab \cdot caa \cdot a \cdot a =<br />
aa \cdot a \cdot bc \cdot aa \cdot aa</tex>.<br />
{{Определение<br />
|definition=<br />
'''Проблемой соответствий Поста''' (Post correspondence problem) называется проблема нахождения алгоритма, выясняющего для каждой постовской системы соответствия, существует ли решение этой системы.<br />
}}<br />
{{Теорема<br />
|statement=<br />
Пусть <tex>| \Sigma | \geq 2</tex>. Тогда не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом <tex>\Sigma</tex> узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)<br />
|proof=<br />
<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0&diff=6188Примеры неразрешимых задач: проблема соответствий Поста2010-12-22T23:06:14Z<p>Mamoshkin.Arseny: Новая страница: «{{Определение |definition= Постовской системой соответствия над алфавитом <tex>\Sigma</tex> называется…»</p>
<hr />
<div>{{Определение<br />
|definition=<br />
Постовской системой соответствия над алфавитом <tex>\Sigma</tex> называется упорядоченная пара конечных последовательностей <tex>(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))</tex>, где <tex>x_i \in \Sigma ^*</tex> и <tex>x_i \in \Sigma ^*</tex> для всех '''i'''.<br />
}}<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B8&diff=5900Основная теорема арифметики2010-12-15T22:23:43Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>==Основная теорема арифметики==<br />
<br />
===Лемма Евклида===<br />
<br />
{{Лемма<br />
|id=th1<br />
|statement=<br />
Если простое число <tex>p</tex> делит без остатка произведение двух целых чисел <tex>x\cdot y</tex>, то <tex>p</tex> делит <tex>x</tex> или <tex>y</tex>.<br />
|proof=<br />
Пусть <tex>x\cdot y</tex> делится на <tex>p</tex>, но <tex>x</tex> не делится на <tex>p</tex>. Тогда <tex>x</tex> и <tex>p</tex> — взаимно простые, следовательно, найдутся такие целые числа <tex>u</tex> и <tex>v</tex>, что<br />
: <tex>x\cdot u+p\cdot v=1</tex> (соотношение Безу).<br />
Умножая обе части на <tex>y</tex>, получаем<br />
: <tex>(x\cdot y)\cdot u+p\cdot v\cdot y=y.</tex><br />
Оба слагаемых левой части делятся на <tex>p</tex>, значит, и правая часть делится на <tex>p</tex>, ч.т.д.<br />
}}<br />
<br />
===Собственно теорема===<br />
<br />
{{Теорема<br />
|id=th666<br />
|statement=<br />
Каждое натуральное число <math>n>1</math> представляется в виде <math>n=p_1\cdot\dots\cdot p_k</math>, где <math>p_1,\dots,p_k</math> — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.<br />
|proof=<br />
'''Существование'''. Пусть <math>n</math> — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если <math>n</math> составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, значит, <math>n</math> тоже является произведением простых чисел. Противоречие.'return'<br />
<br />
'''Единственность'''. Пусть <math>n</math> — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть <math>p</math> — любой из сомножителей в любом из двух разложений. Если <math>p</math> входит и в другое разложение, мы можем сократить оба разложения на <math>p</math> и получить два разных разложения числа <math>n/p</math>, что невозможно. А если <math>p</math> не входит в другое разложение, то одно из произведений делится на <math>p</math>, а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству.<br />
}}<br />
<br />
[[Категория: Классы чисел]]</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0_%D1%87%D0%B8%D1%81%D0%B5%D0%BB_%D0%B2_b-%D0%B8%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B5_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_(%D0%94%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0)&diff=5899Арифметика чисел в b-ичной системе счисления (Длинная арифметика)2010-12-15T22:22:29Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.<br />
}}<br />
<br />
Основная идея заключается в том, что число хранится в виде массива его цифр.<br />
<br />
Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.<br />
<br />
==Представление в памяти==<br />
<br />
Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа в '''b'''-й системе счисления.<br />
<br />
Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).<br />
<br />
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.<br />
<br />
==Сложение, вычитание, умножение, деление на короткое, деление на длинное==<br />
<br />
Операции над числами в этом виде длинной арифметики производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.<br />
<br />
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.<br />
<br />
==Подбор значения очередной цифры в алгоритме деления в столбик==<br />
<br />
Подбор следующей цифры <tex>k \in [0, b]</tex> частного можно производить с помощью стандартного алгоритма двоичного поиска за <tex>ln(b)</tex>.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0_%D1%87%D0%B8%D1%81%D0%B5%D0%BB_%D0%B2_b-%D0%B8%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B5_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_(%D0%94%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0)&diff=5894Арифметика чисел в b-ичной системе счисления (Длинная арифметика)2010-12-15T20:12:57Z<p>Mamoshkin.Arseny: /* Сложение, вычитание, умножение, деление на короткое, деление на длинное */</p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.<br />
}}<br />
<br />
Основная идея заключается в том, что число хранится в виде массива его цифр.<br />
<br />
Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), либо двоичная система счисления.<br />
<br />
==Представление в памяти==<br />
<br />
Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа. Для повышения эффективности удобно работать в системе по основанию миллиард (может храниться в ''int32''), т.е. каждый элемент вектора содержит не одну, а сразу 9 цифр.<br />
<br />
Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы, десятки, сотни, и т.д.).<br />
<br />
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.<br />
<br />
==Сложение, вычитание, умножение, деление на короткое, деление на длинное==<br />
<br />
Операции над числами в этом виде длинной арифметики производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.<br />
<br />
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.<br />
<br />
==Подбор значения очередной цифры в алгоритме деления в столбик==</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0_%D1%87%D0%B8%D1%81%D0%B5%D0%BB_%D0%B2_b-%D0%B8%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B5_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_(%D0%94%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0)&diff=5890Арифметика чисел в b-ичной системе счисления (Длинная арифметика)2010-12-15T17:36:38Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.<br />
}}<br />
<br />
Основная идея заключается в том, что число хранится в виде массива его цифр.<br />
<br />
Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), либо двоичная система счисления.<br />
<br />
==Представление в памяти==<br />
<br />
Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа. Для повышения эффективности удобно работать в системе по основанию миллиард (может храниться в ''int32''), т.е. каждый элемент вектора содержит не одну, а сразу 9 цифр.<br />
<br />
Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы, десятки, сотни, и т.д.).<br />
<br />
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.<br />
<br />
==Сложение, вычитание, умножение, деление на короткое, деление на длинное==<br />
<br />
==Подбор значения очередной цифры в алгоритме деления в столбик==</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%B4%D0%B0%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B5%D1%81%D0%BF%D0%BE%D0%BB%D0%B5%D0%B7%D0%BD%D1%8B%D1%85_%D1%81%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB%D0%BE%D0%B2_%D0%B8%D0%B7_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8&diff=3989Удаление бесполезных символов из грамматики2010-10-14T20:54:24Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''непорождающим''', если из него не может быть выведена конечная терминальная цепочка.<br />
}}<br />
<br />
Рассматривая правила грамматики, можно сделать вывод, что если и только если все нетерминальные символы правой части являются порождающими, то порождающим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непорождающих символов в следующем виде: <br />
# Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов. <br />
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части. <br />
# Если на шаге 2 список больше не пополняется, то получен список всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.<br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''недостижимым''' в КС-грамматике '''<tex>\Gamma</tex>''', если строку, содержащую '''<tex>A</tex>''', нельзя вывести из стартового нетерминала.<br />
}}<br />
<br />
Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так: <br />
# Образовать одноэлементный список, состоящий из начального символа <br />
# Если найдено правило, левая часть которого уже имеется в списке, то включить в список все символы, содержащиеся в его правой части. <br />
# Если на шаге 2 новые нетерминалы в список больше не добавляются, то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми. <br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''бесполезным''' в <br />
КС-грамматике '''<tex>\Gamma</tex>''', если он не может встретиться в выводе слова из терминалов.<br />
}}<br />
{{Теорема<br />
|id=th1<br />
|statement=<br />
Грамматика <tex>\Gamma</tex> не содержит бесполезных символов '''тогда и только тогда, когда''' она не содержит ни недостижимых символов, ни непорождающих.<br />
|proof=<br />
<tex>\Rightarrow</tex> Очевидно, т.к. недостижимые и непорождающие символы являются бесполезными.<br />
<tex>\Leftarrow</tex> Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижимый, существуют <tex>\alpha</tex> и <tex>\beta</tex>, такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой сивол является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> - не бесполезный.<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%B4%D0%B0%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B5%D1%81%D0%BF%D0%BE%D0%BB%D0%B5%D0%B7%D0%BD%D1%8B%D1%85_%D1%81%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB%D0%BE%D0%B2_%D0%B8%D0%B7_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8&diff=3987Удаление бесполезных символов из грамматики2010-10-14T20:48:26Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''непорождающим''', если из него не может быть выведена конечная терминальная цепочка.<br />
}}<br />
<br />
Рассматривая правила грамматики, можно сделать вывод, что если и только если все нетерминальные символы правой части являются порождающими, то порождающим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непорождающих символов в следующем виде: <br />
# Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов. <br />
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части. <br />
# Если на шаге 2 список больше не пополняется, то получен список всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.<br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''недостижимым''' в КС-грамматике '''<tex>\Gamma</tex>''', если '''<tex>A</tex>''' нельзя вывести из стартового нетерминала.<br />
}}<br />
<br />
Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так: <br />
# Образовать одноэлементный список, состоящий из начального символа <br />
# Если найдено правило, левая часть которого уже имеется в списке, то включить в список все символы, содержащиеся в его правой части. <br />
# Если на шаге 2 новые нетерминалы в список больше не добавляются, то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми. <br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''бесполезным''' в <br />
КС-грамматике '''<tex>\Gamma</tex>''', если он не может встретиться в выводе слова из терминалов.<br />
}}<br />
{{Теорема<br />
|id=th1<br />
|statement=<br />
Грамматика <tex>\Gamma</tex> не содержит бесполезных символов '''тогда и только тогда, когда''' она не содержит ни недостижимых символов, ни непорождающих.<br />
|proof=<br />
<tex>\Rightarrow</tex> Очевидно, т.к. недостижимые и непорождающие символы являются бесполезными.<br />
<tex>\Leftarrow</tex> Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижимый, существуют <tex>\alpha</tex> и <tex>\beta</tex>, такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой сивол является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> - не бесполезный.<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%BE%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0%D0%BC&diff=3986Правоконтекстные грамматики, эквивалентность автоматам2010-10-14T20:48:13Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Праволинейной грамматикой''' <tex>\Gamma</tex> называется грамматика, в которой все правила имеют вид <tex> A \to a </tex>, <tex> A \to aB </tex>.<br />
}}<br />
<br />
Аналогично можно определить леволинейные грамматики.<br />
<br />
{{Теорема<br />
|statement=<br />
Множество языков, задаваемых праволинейными грамматиками совпадает со множеством языков, задаваемых конечными автоматами.<br />
|proof=<br />
Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, добавим в грамматику правило <tex> A \to cB </tex>. Затем для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, и <tex> B </tex> – является допускающим состоянием в автомате, добавим в грамматику правило <tex> A \to c </tex>. <br />
<br />
Докажем, что если для автомата верно <tex>\langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>, то для построенной грамматики верно <tex> S \Rightarrow^* \alpha U </tex>. Будем доказывать индукцией по переходам в автомате.<br />
<br />
Базой индукции будут переходы за 0 шагов.<br />
Индукционный переход: пусть данное свойство выполняется для переходов длины <tex>k-1</tex>. Докажем что верно и для переходов за <tex>k</tex> шагов.<br />
<br />
Рассмотрим переход <tex>\langle S, \alpha \rangle \vdash^{k} \langle U, \varepsilon \rangle </tex>, а именно его последний шаг: <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle Q, c \rangle \vdash \langle U, \varepsilon \rangle </tex><br />
Так как для <tex>k-1</tex> шагов верно, то <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q </tex> но по построению грамматики имеется правило <tex> Q \to c U</tex>, значит <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q \Rightarrow \alpha c^{-1} c U = \alpha U</tex>. Таким образом доказали для <tex>k</tex> шагов.<br />
<br />
Докажем в обратную сторону, а именно из <tex> S \Rightarrow^* \alpha U </tex> следует <tex> \langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>. Доказательство так же проведем по индукции. Индукция будет идти по количеству примененных подряд правил.<br />
<br />
Базой индукции будут строки, выводимые в грамматике из начального нетерминала <tex> S </tex> за 0 применений правил.<br />
<br />
Индукционный переход: пусть верно для <tex>k-1</tex> применения правил. Рассмотрим произвольную строку, полученную за <tex>k</tex> применений правил. Рассмотрим последнее применение правила. Если оно имело вид <tex> A \to aB </tex>, значит в автомате возможен переход <tex> \langle A,a \rangle \vdash \langle B,\varepsilon \rangle </tex>, а если <tex> A \to a </tex>, то <tex> B </tex> является допускающим в автомате. Таким образом свойство выполняется для <tex> k </tex> последовательно примененных правил. Эквивалентность языков автомата и грамматики доказана.<br />
<br />
<br />
Теперь пусть имеется праволинейная грамматика. Построим по ней конечный детерминированный автомат. <br />
Введем специальное допускающее состояние <tex> ok </tex>. Множеством состояний автомата будет множество нетерминалов грамматики вместе с состоянием <tex> ok </tex> (<tex> Q = N \cup ok </tex>). Для правил вида <tex> A \to aB </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = B </tex>. Для правил вида <tex> A \to a </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = ok </tex>.<br />
<br />
Докажем, что если слово выводится в грамматике, то оно допускается автоматом. Рассмотрим последовательность применений правил, дающую слово <tex> \alpha </tex> длины <tex> k </tex>. Для каждого правила вида <tex> A \to aB </tex> в автомате существует переход из состояния <tex> A </tex> в состояние <tex> B</tex> по символу <tex> a </tex>. Таким образом, если после <tex> k-1 </tex> применения правил мы можем получить строку вида <tex> \alpha c^{-1}B </tex>, то в автомате имеется соответствующая последовательность переходов <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle B, c \rangle </tex>, а поскольку можно вывести <tex> \alpha </tex>, то хотя бы для одной строки такого вида существует правило <tex> B \to c </tex>, а значит в автомате есть переход <tex> \langle B,c \rangle \vdash \langle ok,\varepsilon \rangle </tex>. Таким образом автомат допускает слово <tex> \alpha </tex>.<br />
<br />
Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово <tex> \alpha </tex> длины <tex> k </tex>. Рассмотрим какую-либо последовательность переходов автомата, допускающую данное слово <tex> \langle S,\alpha \rangle \vdash^k \langle ok,\varepsilon \rangle </tex>. Для каждого одношагового перехода в автомате существует соответствующее правило в грамматике. Значит для подпоследовательности переходов из <tex> k-1 </tex> шага <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle U,c \rangle </tex> существует соответствующая последовательность применений правил <tex> S \Rightarrow^{k-1} \alpha c^{-1} U </tex>. Для последнего перехода в автомате <tex> \langle U,c \rangle \vdash \langle ok, \varepsilon \rangle </tex> существует правило <tex> U \Rightarrow c </tex>. Таким образом, существует последовательность применений правил грамматики, выводящая слово <tex> \alpha </tex>.<br />
<br />
Теорема доказана.<br />
<br />
}}<br />
<br />
== Литература ==<br />
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%B4%D0%B0%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B5%D1%81%D0%BF%D0%BE%D0%BB%D0%B5%D0%B7%D0%BD%D1%8B%D1%85_%D1%81%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB%D0%BE%D0%B2_%D0%B8%D0%B7_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8&diff=3975Удаление бесполезных символов из грамматики2010-10-14T20:04:26Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''непорождающим''', если из него не может быть выведена конечная терминальная цепочка.<br />
}}<br />
<br />
Рассматривая правила грамматики, можно сделать вывод, что если и только если все нетерминальные символы правой части являются порождающими, то порождающим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непорождающих символов в следующем виде: <br />
# Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов. <br />
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части. <br />
# Если на шаге 2 список больше не пополняется, то получен список всех порождающих нетерминалов грамматики, а все нетерминалы не попавшие в него являются непорождающими.<br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''недостижимым''' в КС-грамматике '''<tex>\Gamma</tex>''', если '''<tex>A</tex>''' не появляется ни в одной выводимой цепочке.<br />
}}<br />
<br />
Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так: <br />
# Образовать одноэлементный список, состоящий из начального символа <br />
# Если найдено правило, левая часть которого уже имеется в списке, то включить в список все символы, содержащиеся в его правой части. <br />
# Если на шаге 2 новые нетерминалы в список больше не добавляются, то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми. <br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''бесполезным''' в <br />
КС-грамматике '''<tex>\Gamma</tex>''', если он не может встретиться в выводе слова из терминалов.<br />
}}<br />
{{Теорема<br />
|id=th1<br />
|statement=<br />
Грамматика <tex>\Gamma</tex> не содержит бесполезных символов '''тогда и только тогда, когда''' она не содержит ни недостижимых символов, ни непорождающих.<br />
|proof=<br />
<tex>\Rightarrow</tex> Очевидно, т.к. недостижимые и непорождающие символы являются бесполезными.<br />
<tex>\Leftarrow</tex> Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижимый, существуют <tex>\alpha</tex> и <tex>\beta</tex>, такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой сивол является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> - не бесполезный.<br />
}}</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%B4%D0%B0%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B5%D1%81%D0%BF%D0%BE%D0%BB%D0%B5%D0%B7%D0%BD%D1%8B%D1%85_%D1%81%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB%D0%BE%D0%B2_%D0%B8%D0%B7_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8&diff=3953Удаление бесполезных символов из грамматики2010-10-14T06:40:17Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''непроизводящим''', если из него не может быть выведена конечная терминальная цепочка.<br />
}}<br />
<br />
Рассматривая правила грамматики, можно сделать вывод, что если все символы правой части являются производящими, то производящим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих символов в следующем виде: <br />
# Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов. <br />
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части. <br />
# Если на шаге 2 список больше не пополняется, то получен список всех производящих нетерминалов грамматики, а все нетерминалы не попавшие в него являются непроизводящими.<br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''недостижимым''' в КС-грамматике '''<tex>\Gamma</tex>''', если '''<tex>A</tex>''' не появляется ни в одной выводимой цепочке.<br />
}}<br />
<br />
Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так: <br />
# Образовать одноэлементный список, состоящий из начального символа <br />
# Если найдено правило, левая часть которого уже имеется в списке, то включить в список все символы, содержащиеся в его правой части. <br />
# Если на шаге 2 новые нетерминалы в список больше не добавляются, то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми. <br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''бесполезным''' в <br />
КС-грамматике '''<tex>\Gamma</tex>''', если он является недостижимым или непроизводящим.<br />
}}<br />
<br />
{{Теорема<br />
|id=th1<br />
|statement=<br />
Исключить бесполезные символы из грамматики можно удаляя правила, содержащие вначале непроизводящие, а затем недостижимые символы.<br />
|proof=<br />
Любой терминальный символ является генерирующим.<br />
Пусть <tex>A \rightarrow \alpha</tex> и известно, что <tex>\alpha</tex> состоит только из генерирующих символов, тогда <tex>A</tex> - генерирующий символ.<br />
Если <tex>\alpha = \epsilon</tex>, тогда <tex>A</tex> также генерирующий символ.<br />
}}</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%B4%D0%B0%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B5%D1%81%D0%BF%D0%BE%D0%BB%D0%B5%D0%B7%D0%BD%D1%8B%D1%85_%D1%81%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB%D0%BE%D0%B2_%D0%B8%D0%B7_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8&diff=3952Удаление бесполезных символов из грамматики2010-10-14T06:27:24Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>{{В разработке}}<br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''непроизводящим''', если из него не может быть выведена конечная терминальная цепочка.<br />
}}<br />
<br />
Рассматривая правила грамматики, можно сделать вывод, что если все символы правой части являются производящими, то производящим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих символов в следующем виде: <br />
# Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов. <br />
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части. <br />
# Если на шаге 2 список больше не пополняется, то получен список всех производящих нетерминалов грамматики, а все нетерминалы не попавшие в него являются непроизводящими.<br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''недостижимым''' в КС-грамматике '''<tex>\Gamma</tex>''', если '''<tex>A</tex>''' не появляется ни в одной выводимой цепочке.<br />
}}<br />
<br />
Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так: <br />
# Образовать одноэлементный список, состоящий из начального символа <br />
# Если найдено правило, левая часть которого уже имеется в списке, то включить в список все символы, содержащиеся в его правой части. <br />
# Если на шаге 2 новые нетерминалы в список больше не добавляются, то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми. <br />
<br />
{{Определение<br />
|definition=<br />
Символ '''<tex>A</tex>''' называется '''бесполезным''' в <br />
КС-грамматике '''<tex>\Gamma</tex>''', если он является недостижимым или непроизводящим.<br />
}}<br />
<br />
Исключить бесполезные символы из грамматики можно удаляя правила, содержащие вначале непроизводящие, а затем недостижимые символы.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%B4%D0%B0%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B5%D1%81%D0%BF%D0%BE%D0%BB%D0%B5%D0%B7%D0%BD%D1%8B%D1%85_%D1%81%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB%D0%BE%D0%B2_%D0%B8%D0%B7_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8&diff=3904Удаление бесполезных символов из грамматики2010-10-13T22:57:54Z<p>Mamoshkin.Arseny: Новая страница: «{{В разработке}}»</p>
<hr />
<div>{{В разработке}}</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0_%D1%87%D0%B8%D1%81%D0%B5%D0%BB_%D0%B2_b-%D0%B8%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B5_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_(%D0%94%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0)&diff=3031Арифметика чисел в b-ичной системе счисления (Длинная арифметика)2010-10-02T05:19:50Z<p>Mamoshkin.Arseny: Новая страница: «{{В разработке}} ==Представление в памяти== ==Сложение, вычитание, умножение, деление на коро…»</p>
<hr />
<div>{{В разработке}}<br />
<br />
==Представление в памяти==<br />
<br />
==Сложение, вычитание, умножение, деление на короткое, деление на длинное==<br />
<br />
==Подбор значения очередной цифры в алгоритме деления в столбик==</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B8%D1%82%D0%B5%D0%BB%D0%B8_(%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F)&diff=3030Разложение на множители (факторизация)2010-10-02T05:18:41Z<p>Mamoshkin.Arseny: </p>
<hr />
<div>'''Перебор делителей''' — алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.<br />
<br />
==Проверка числа на простоту за <tex>O(\sqrt{n})</tex>==<br />
<br />
Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа ''n'' и в вычислении остатка от деления ''n'' на каждое из этих чисел. Если остаток от деления на некоторое число ''m'' равен нулю, то ''m'' является делителем ''n''. В этом случае либо ''n'' объявляется составным, и алгоритм заканчивает работу.<br />
<br />
Таким образом, осуществляя проверку на делимость за <tex>O(n)</tex> и перебирая не более <tex>\sqrt{n}</tex> чисел, получаем максимальную оценку времени работы алгоритма: <tex>O(\sqrt{n})</tex>.<br />
<br />
==Разложение на множители за <tex>O(\sqrt{n})</tex>==<br />
<br />
Для поиска разложения числа на множители воспользуемся так же простым перебором чисел от <tex>1</tex> до <tex>\sqrt{n}</tex>. С помощью алгоритма проверки простоты найдём первый делитель числа <tex>n</tex> - <tex>m</tex>. Далее <tex>n</tex> сокращается в <tex>m</tex> раз и процедура повторяется. По достижении квадратного корня из <tex>n</tex> и невозможности сократить <tex>n</tex> ни на одно из меньших чисел, <tex>n</tex> объявляется неразложимым.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B8%D1%82%D0%B5%D0%BB%D0%B8_(%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F)&diff=3029Разложение на множители (факторизация)2010-10-02T05:16:50Z<p>Mamoshkin.Arseny: /* Разложение на множители за O(\sqrt{n}) */</p>
<hr />
<div>{{В разработке}}<br />
<br />
==Проверка числа на простоту за <tex>O(\sqrt{n})</tex>==<br />
<br />
Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа ''n'' и в вычислении остатка от деления ''n'' на каждое из этих чисел. Если остаток от деления на некоторое число ''m'' равен нулю, то ''m'' является делителем ''n''. В этом случае либо ''n'' объявляется составным, и алгоритм заканчивает работу.<br />
<br />
Таким образом, осуществляя проверку на делимость за <tex>O(n)</tex> и перебирая не более <tex>\sqrt{n}</tex> чисел, получаем максимальную оценку времени работы алгоритма: <tex>O(\sqrt{n})</tex>.<br />
<br />
==Разложение на множители за <tex>O(\sqrt{n})</tex>==<br />
<br />
Для поиска разложения числа на множители воспользуемся так же простым перебором чисел от <tex>1</tex> до <tex>\sqrt{n}</tex>. С помощью алгоритма проверки простоты найдём первый делитель числа <tex>n</tex> - <tex>m</tex>. Далее <tex>n</tex> сокращается в <tex>m</tex> раз и процедура повторяется. По достижении квадратного корня из <tex>n</tex> и невозможности сократить <tex>n</tex> ни на одно из меньших чисел, <tex>n</tex> объявляется неразложимым.</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B8%D1%82%D0%B5%D0%BB%D0%B8_(%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F)&diff=3028Разложение на множители (факторизация)2010-10-02T05:06:06Z<p>Mamoshkin.Arseny: /* Проверка числа на простоту за O(\sqrt{n}) */</p>
<hr />
<div>{{В разработке}}<br />
<br />
==Проверка числа на простоту за <tex>O(\sqrt{n})</tex>==<br />
<br />
Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа ''n'' и в вычислении остатка от деления ''n'' на каждое из этих чисел. Если остаток от деления на некоторое число ''m'' равен нулю, то ''m'' является делителем ''n''. В этом случае либо ''n'' объявляется составным, и алгоритм заканчивает работу.<br />
<br />
Таким образом, осуществляя проверку на делимость за <tex>O(n)</tex> и перебирая не более <tex>\sqrt{n}</tex> чисел, получаем максимальную оценку времени работы алгоритма: <tex>O(\sqrt{n})</tex>.<br />
<br />
==Разложение на множители за <tex>O(\sqrt{n})</tex>==</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B8%D1%82%D0%B5%D0%BB%D0%B8_(%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F)&diff=3027Разложение на множители (факторизация)2010-10-02T04:51:45Z<p>Mamoshkin.Arseny: Новая страница: «{{В разработке}} ==Проверка числа на простоту за <tex>O(\sqrt{n})</tex>== ==Разложение на множители за <…»</p>
<hr />
<div>{{В разработке}}<br />
<br />
==Проверка числа на простоту за <tex>O(\sqrt{n})</tex>==<br />
<br />
==Разложение на множители за <tex>O(\sqrt{n})</tex>==</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D1%8B_%D0%B8_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D1%87%D0%B8%D1%81%D0%B5%D0%BB&diff=3021Алгоритмы алгебры и теории чисел2010-10-02T02:12:35Z<p>Mamoshkin.Arseny: /* Практика - Разложение на множители и длинная арифметика */</p>
<hr />
<div>== Лекция - Классы чисел и основная теорема арифметики ==<br />
* [[Классы чисел]]<br />
* [[Натуральные и целые числа]]<br />
* [[Простые числа]]<br />
* [[Наибольший общий делитель]]<br />
* [[Основная теорема арифметики]]<br />
* [[Теоремы о простых числах]]<br />
=== Практика - Разложение на множители и длинная арифметика ===<br />
* [[Системы счисления]]<br />
* [[Арифметика чисел в b-ичной системе счисления (Длинная арифметика)]]<br />
* [[Разложение на множители (факторизация)]]<br />
<br />
== Лекция - Основные элементы теории чисел ==<br />
* [[Сравнения, вычеты, остатки]]<br />
* [[Теоретико-числовые функции]]<br />
<br />
=== Практика - Основные алгоритмы теории чисел ===<br />
<br />
== Лекция - Основы теории групп ==<br />
* [[Полугруппа]], [[моноид]], [[группа]]<br />
* [[Абелева группа]], [[Конечная группа]]<br />
* [[Гомоморфизм групп]], [[изоморфизм групп]]<br />
* [[Подгруппа]], [[нормальная подгруппа]]<br />
* [[Порядок элемента группы]], [[циклическая группа]], [[конечно порожденная группа]]<br />
* [[Теорема о подгруппах циклической группы]]<br />
* [[Смежные классы]], [[теорема Лагранжа]], [[факторгруппы]]<br />
=== Практика - Основы теории групп ===<br />
* [[Вычисление порядка элемента в группе]]<br />
* [[Вычисление порядка перестановки в группе перестановок]]<br />
* [[Дискретное логарифмирование в группе]]<br />
* [[Действие группы на множестве]]<br />
* [[Лемма Бернсайда, задача о числе ожерелий]]<br />
* [[Представление групп]]<br />
<br />
== Лекция - Основы теории колец ==<br />
*[[Определение кольца, подкольца, изоморфизмы колец]]<br />
*[[Делители нуля, области целостности]]<br />
*[[Единицы (обратимые элементы), группа обратимых элементов]]<br />
*[[Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах]]<br />
*[[Евклидовы кольца]]<br />
=== Практика - Арифметика полиномов от одной переменной над полем ===<br />
<br />
== Лекция - Основы теории полей ==<br />
* [[Определение поля и подполя, изоморфизмы полей]]<br />
* [[Примеры полей]]<br />
* [[Мультипликативная группа поля]]<br />
* [[Расширения полей]]<br />
<br />
== Лекция - Первообразные корни и квадратичные вычеты ==<br />
* [[Теорема о цикличности мультипликативной группы поля Z/pZ|Теорема о цикличности мультипликативной группы поля <tex>\mathbb{Z}/p\mathbb{Z}</tex>]]<br />
* [[Первообразные корни]]<br />
* [[Квадратичные вычеты]]<br />
=== Практика - Первообразные корни и квадратичные вычеты ===<br />
<br />
== Лекция - Квадратичные вычеты ==<br />
*[[Квадратичный закон взаимности]]<br />
*[[Символ Якоби и его свойства]]<br />
*[[Обобщенный квадратичный закон взаимности]]<br />
*[[Алгоритм вычисления символа Якоби]]<br />
=== Практика - Вероятностные тесты чисел на простоту ===<br />
*[[Тест Ферма проверки чисел на простоту, числа Кармайкла]]<br />
*[[Тест Соловея-Штрассена]]<br />
*[[Тест Миллера-Рабина]]<br />
<br />
== Лекция - Аналитическая теория чисел ==<br />
* [[Факты из математического анализа]]<br />
* [[Теорема Чебышёва]]<br />
* [[Постулат Бертрана]]<br />
* [[Уточнение констант в теореме Чебышёва]]<br />
* [[Сумма обратных к простым]]<br />
* [[Асимптотический закон распределения простых чисел]]<br />
=== Практика - Вычисление <math>\pi(x)</math> ===<br />
<br />
== Лекция - Цепные (непрерывные) дроби и уравнение Пелля ==<br />
* [[Цепная дробь]]<br />
** [[Связь цепных дробей и алгоритма Евклида]]<br />
** [[Сходимость цепных дробей]]<br />
** [[Цепные дроби как приближение к числу]]<br />
** [[Квадратичная иррациональность]]<br />
** [[Периодичность цепных дробей]]<br />
** [[Цепные дроби для sqrtd и квадратичных иррациональностей|Цепные дроби для <tex>\sqrt{d}</tex> и квадратичных иррациональностей]]<br />
* [[Уравнение Пелля]]<br />
* [[Представление простых в виде суммы двух квадратов]]<br />
<br />
== Лекция - Конечные поля ==<br />
=== Практика - Методы разложения полиномов на множители над конечными полями ===</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=3020Системы счисления2010-10-02T02:10:02Z<p>Mamoshkin.Arseny: /* Фибоначчиева система счисления */</p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Систе́ма счисле́ния''' — символический метод записи чисел, представление чисел с помощью письменных знаков.<br />
}}<br />
<br />
==Позиционные системы счисления==<br />
<br />
В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.<br />
<br />
Под позиционной системой счисления обычно понимается ''b''-ричная система счисления, которая определяется [[целое число|целым числом]] <math>b>1</math>, называемым основанием системы счисления.<br />
<br />
===Запись числа в b-ичной системе счисления===<br />
<br />
Целое число ''x'' в ''b''-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа ''b'':<br />
: <tex>x = \sum_{k=0}^{n-1} a_k b^k</tex>, где <tex>a_k</tex> — это целые числа, называемые '''цифрами''', удовлетворяющие неравенству <tex>0 \leq a_k \leq (b-1)</tex>.<br />
Каждая степень <tex>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ричном представлении <tex>x</tex> была также ненулевой.<br />
<br />
Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число <tex>x</tex> записывают в виде последовательности его ''b''-ричных цифр, перечисляемых по убыванию старшинства разрядов слева направо:<br />
: <tex>x = a_{n-1} a_{n-2}\dots a_0.</tex><br />
Например, число ''сто три'' представляется в десятичной системе счисления в виде:<br />
: <tex> 103 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0}.</tex><br />
<br />
Наиболее употребляемыми в настоящее время позиционными системами являются:<br />
* 1 — единичная (как позиционная может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.);<br />
* 2 — двоичная (в дискретной математике, информатике, |программировании);<br />
* 8 — восьмеричная;<br />
* 10 — десятичная (используется повсеместно);<br />
* 12 — двенадцатеричная (счёт дюжинами);<br />
* 16 — шестнадцатеричная (используется в программировании, информатике.<br />
<br />
==Смешанные системы счисления==<br />
<br />
'''Смешанная система счисления''' является обобщением <tex>b</tex>-ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел <tex>\{b_k\}_{k=0}^{\infty}</tex> и каждое число <tex>x</tex> представляется как линейная комбинация:<br />
: <tex>x = \sum_{k=0}^{n-1} a_{k}b_k</tex>, где на коэффициенты <tex>a_{k}</tex> (называемые как и прежде ''цифрами'') накладываются некоторые ограничения.<br />
Записью числа <tex>x</tex> в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса <tex>k</tex>, начиная с первого ненулевого.<br />
<br />
В зависимости от вида <tex>b_k</tex> как функции от ''k'' смешанные системы счисления могут быть степенными, показательными и т. п. Когда <tex>b_k=b^k</tex> для некоторого <tex>b</tex>, показательная смешанная система счисления совпадает с <tex>b</tex>-ричной системой счисления.<br />
<br />
Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина ''d дней h часов m минут s секунд'' соответствует значению <tex>d\cdot 24\cdot 60\cdot 60 + h\cdot 60\cdot 60 + m\cdot 60 + s</tex> секунд.<br />
<br />
==Фибоначчиева система счисления==<br />
<br />
{{Определение<br />
|definition=<br />
последовательность чисел Фибоначчи <tex>\left\{F_n\right\}</tex> задается линейным рекуррентным соотношением:<br />
: <tex>F_0 = 0,\qquad F_1 = 1,\qquad F_{n+1} = F_n + F_{n-1}, \quad n\in\mathbb{N}.</tex><br />
}}<br />
<br />
'''Фибоначчиева система счисления''' основывается на [[числа Фибоначчи|числах Фибоначчи]].<br />
<br />
: <tex>x = \sum_{k=0}^n f_k F_k</tex>, где <tex>F_k</tex> — числа Фибоначчи, <tex>f_k\in\{0,1\}</tex>, при этом в записи <tex>f_nf_{n-1}\dots f_0</tex> не встречается две единицы подряд.<br />
<br />
Таким образом, любое неотрицательное целое число <tex>a = 0,\ 1,\ 2,\dots</tex> можно единственным образом представить через последовательность битов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub>: <tex>a = \sum_k \varepsilon_k F_k,\ \varepsilon_k = 0,1</tex>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <tex>\forall k\ge 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</tex>.<br />
За исключением последнего свойства, данное представление аналогично двоичной системе счисления.<br />
<br />
{{Теорема<br />
|id=th1<br />
|author=Цекендорф<br />
|statement=<br />
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.<br />
|proof=<br />
Доказательство существования легко провести по индукции. Любое целое число <tex>a\ge 1</tex> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого <tex>n\ge 2</tex> верно неравенство: <tex>F_n \le a < F_{n+1}</tex>. Таким образом, <tex>a = F_n + a'</tex>, где <tex>a'=a-F_n\ <\ F_{n-1}</tex>, так что разложение числа <tex>a'</tex> уже не будет содержать слагаемого <tex>F_{n-1}</tex>.<br />
}}</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=3019Системы счисления2010-10-02T01:57:51Z<p>Mamoshkin.Arseny: /* Смешанные системы счисления */</p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Систе́ма счисле́ния''' — символический метод записи чисел, представление чисел с помощью письменных знаков.<br />
}}<br />
<br />
==Позиционные системы счисления==<br />
<br />
В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.<br />
<br />
Под позиционной системой счисления обычно понимается ''b''-ричная система счисления, которая определяется [[целое число|целым числом]] <math>b>1</math>, называемым основанием системы счисления.<br />
<br />
===Запись числа в b-ичной системе счисления===<br />
<br />
Целое число ''x'' в ''b''-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа ''b'':<br />
: <tex>x = \sum_{k=0}^{n-1} a_k b^k</tex>, где <tex>a_k</tex> — это целые числа, называемые '''цифрами''', удовлетворяющие неравенству <tex>0 \leq a_k \leq (b-1)</tex>.<br />
Каждая степень <tex>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ричном представлении <tex>x</tex> была также ненулевой.<br />
<br />
Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число <tex>x</tex> записывают в виде последовательности его ''b''-ричных цифр, перечисляемых по убыванию старшинства разрядов слева направо:<br />
: <tex>x = a_{n-1} a_{n-2}\dots a_0.</tex><br />
Например, число ''сто три'' представляется в десятичной системе счисления в виде:<br />
: <tex> 103 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0}.</tex><br />
<br />
Наиболее употребляемыми в настоящее время позиционными системами являются:<br />
* 1 — единичная (как позиционная может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.);<br />
* 2 — двоичная (в дискретной математике, информатике, |программировании);<br />
* 8 — восьмеричная;<br />
* 10 — десятичная (используется повсеместно);<br />
* 12 — двенадцатеричная (счёт дюжинами);<br />
* 16 — шестнадцатеричная (используется в программировании, информатике.<br />
<br />
==Смешанные системы счисления==<br />
<br />
'''Смешанная система счисления''' является обобщением <tex>b</tex>-ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел <tex>\{b_k\}_{k=0}^{\infty}</tex> и каждое число <tex>x</tex> представляется как линейная комбинация:<br />
: <tex>x = \sum_{k=0}^{n-1} a_{k}b_k</tex>, где на коэффициенты <tex>a_{k}</tex> (называемые как и прежде ''цифрами'') накладываются некоторые ограничения.<br />
Записью числа <tex>x</tex> в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса <tex>k</tex>, начиная с первого ненулевого.<br />
<br />
В зависимости от вида <tex>b_k</tex> как функции от ''k'' смешанные системы счисления могут быть степенными, показательными и т. п. Когда <tex>b_k=b^k</tex> для некоторого <tex>b</tex>, показательная смешанная система счисления совпадает с <tex>b</tex>-ричной системой счисления.<br />
<br />
Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина ''d дней h часов m минут s секунд'' соответствует значению <tex>d\cdot 24\cdot 60\cdot 60 + h\cdot 60\cdot 60 + m\cdot 60 + s</tex> секунд.<br />
<br />
==Фибоначчиева система счисления==</div>Mamoshkin.Arsenyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=3018Системы счисления2010-10-02T01:48:27Z<p>Mamoshkin.Arseny: /* Позиционные системы счисления */</p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Систе́ма счисле́ния''' — символический метод записи чисел, представление чисел с помощью письменных знаков.<br />
}}<br />
<br />
==Позиционные системы счисления==<br />
<br />
В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.<br />
<br />
Под позиционной системой счисления обычно понимается ''b''-ричная система счисления, которая определяется [[целое число|целым числом]] <math>b>1</math>, называемым основанием системы счисления.<br />
<br />
===Запись числа в b-ичной системе счисления===<br />
<br />
Целое число ''x'' в ''b''-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа ''b'':<br />
: <tex>x = \sum_{k=0}^{n-1} a_k b^k</tex>, где <tex>a_k</tex> — это целые числа, называемые '''цифрами''', удовлетворяющие неравенству <tex>0 \leq a_k \leq (b-1)</tex>.<br />
Каждая степень <tex>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ричном представлении <tex>x</tex> была также ненулевой.<br />
<br />
Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число <tex>x</tex> записывают в виде последовательности его ''b''-ричных цифр, перечисляемых по убыванию старшинства разрядов слева направо:<br />
: <tex>x = a_{n-1} a_{n-2}\dots a_0.</tex><br />
Например, число ''сто три'' представляется в десятичной системе счисления в виде:<br />
: <tex> 103 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0}.</tex><br />
<br />
Наиболее употребляемыми в настоящее время позиционными системами являются:<br />
* 1 — единичная (как позиционная может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.);<br />
* 2 — двоичная (в дискретной математике, информатике, |программировании);<br />
* 8 — восьмеричная;<br />
* 10 — десятичная (используется повсеместно);<br />
* 12 — двенадцатеричная (счёт дюжинами);<br />
* 16 — шестнадцатеричная (используется в программировании, информатике.<br />
<br />
==Смешанные системы счисления==<br />
<br />
==Фибоначчиева система счисления==</div>Mamoshkin.Arseny