РУ вида
f(n+k) = a1 f(n+k−1) + a2 f(n+k−2) + … + ak f(n), где k > 0, (2.2)
называется линейным однородным РУ с постоянными коэффициентами.
Последовательности, являющиеся решением РУ (2.2), называются возвратными.
Теорема 2.1. Общее решение РУ (2.1) можно представить в виде суммы общего решения однородного РУ (2.2) и какого-нибудь частного решения РУ (2.1).
Лемма 2.1. Если а(n) и b(n) − решения однородного РУ (2.2), то для "m, n Î R последовательность m а(n) + n b(n) − тоже решение однородного РУ (2.2).
Лемма 2.2. Для "m Î N выражение 
является многочленом от n степени j−1.
Пусть b0, b1, …, bk − некоторые числа, причём b0 ¹ 0. Составим многочлен:
Pm (x) = 
bi (k − i)m xk − i, (2.3)
где m Î {0, 1, 2, …, k}.
Лемма 2.3. Если l ¹ 0 − корень кратности r (1 £ r £ k)многочлена P0 (x), то
P0 (l) = P1 (l) = … = Pr−1 (l) = 0, а Pr (l) ¹ 0.
Уравнение
zk − a1 zk−1 − a2 zk−2 − … − ak = 0 (2.4)
называется характеристическим уравнением для однородного РУ (2.2)
Теорема 2.2. о линейных однородных РУ. Пусть а(n) − числовая последовательность, причём аi, ai Î C (множеству комплексных чисел), ak ¹ 0. Тогда равносильны следующие три утверждения:
1. последовательность а(n) − решение однородного РУ (2.2);
2. производящую функцию последовательности а(n) можно представить в виде:
а(x) = P(x) / Q(x),
где Q(x) = 1 − a1 x − a2 x2 − … − ak xk, P(x) − многочлен степени не выше k−1;
3. последовательность а(n) можно представить в виде:
а(n) = 
Ri (n) lin ,
где l1, l2, …, ls − различные корни характеристического уравнения соответственно кратности r1, r2, …, rs, а Ri (n) − многочлен степени не выше ri − 1 (i = 1, 2, …, s).
Перейдём к решению уравнения (2.1).
Пусть u(n) = Rm (n) ln, где Rm (n) − многочлен аргумента n степени m, ln ¹ 0.
В этом случае частное решение уравнения (2.1) можно подобрать в виде:
1. Qm (n) ln, если l не является корнем характеристического уравнения (2.4);
2. Qm (n) ln nr, если l − корень характеристического уравнения (2.4) кратности r.
Коэффициенты многочлена Qm (n) определяются путём подстановки решения Qm (n) ln (Qm (n) ln nr) в исходное уравнение.
ГЛАВА III . ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
Под алгоритмом в самом широком смысле понимают точное и строгое описание последовательности операций, позволяющей за конечное число шагов получить решение задачи.
Свойства алгоритмов
1. Дискретность: в начальный момент времени задается исходная конечная система величин (СВ), а в каждый следующий момент СВ получается по определенному закону (программе) из СВ, имевшихся в предыдущий момент времени.
2. Детерминированность: СВ, получаемых в какой-то (не начальный) момент t, однозначно определяется СВ, получаемых в предшествующие моменты t.
3. Элементарность шагов: закон получения последующей СВ из предшествующей должен быть простым и локальным.
4. Направленность (результативность): остановка после конечного числа шагов (зависящего от данных). Если способ получения последующей величины из какой-нибудь заданной не дает результата, то должно быть указано, что надо считать результатом алгоритма.
5. Массовость: начальная СВ может выбираться из потенциально ¥-го множества.
Понятие алгоритма, определяемое требованиями 1-5, не строгое: в формулировках этих требований встречаются слова “способ”, “величина”, “простой”, “локальный”, точный смысл которых не установлен. Это понятие называется непосредственным или интуитивным определением алгоритма.
§ 1. Определение машины Тьюринга
Обычно в алгоритмических проблемах математики речь идет не об алгоритмах, а о вычислимости некоторых специальным образом построенных функций. Понятие вычислимой функции является вторичным по отношению к понятию алгоритма: в теории алгоритмов принято сначала уточнить непосредственно само понятие алгоритма и затем при его помощи точно определить класс вычислимых функций.
Это и было сделано Постом и Тьюрингом независимо друг от друга и почти одновременно. Основная мысль Поста и Тьюринга заключалась в том, что алгоритмические процессы - это процессы, которые может совершать подходяще устроенная “машина”. В соответствии с этой мыслью ими были описаны в точных математических терминах довольно узкие классы машин, но на этих машинах оказалось возможным осуществить или имитировать все алгоритмические процессы, которые фактически когда-либо описывались математиками.
Машины, введенные Постом и Тьюрингом, отличались не очень существенно и в дальнейшем и те, и другие стали называться машинами Тьюринга.
Попытаемся сформулировать математически точное определение алгоритма. В настоящее t существует много вариантов этого определения. Все они представляют собой довольно сложные конструкции и по форме нередко различаются между собой. Однако все эти конструкции равносильны между собой. Одна из них получила особенно широкое распространение ввиду своей наглядности и удобства. В честь автора ее назвали “машиной Тьюринга”.
Машина Тьюринга есть совокупность следующих четырех компонент:
1. Бесконечная в обе стороны лента, разделенная на ячейки. На ленте выбрано направление, называемое направлением слева направо.
2. Читающая головка, которая в каждый момент работы машины находится в некоторой ячейке ленты - или, как обычно говорят, обозревает эту ячейку.
3. Два конечных алфавита - внешний А={a0, a1,..., an} (n³0) и внутренний Q={q0, q1,..., qt} (t³1), называемый также множеством состояний.
Элементы a0,...,an называются внешними символами машины, элементы q0, q1,...,qt - внутренними состояниями или просто состояниями. В каждый момент работы машина находится в некотором сост. qj и в каждой ячейке ленты записан некоторый внешний символ ai.
Символ a0 называется пустым символом. Пустой символ служит для того, чтобы можно было рассматривать ленту, у которой в некоторых ячейках ничего не записано, и в то же время формально считать, что в каждой ячейке всегда записан какой-то символ. Таким образом, a0 означает, что ячейка пуста. Вместо a0 будем употреблять греческую букву l.
Состояние q0 называется заключительным состоянием, а состояние q1 - начальным состоянием; q1и q0 указывают соответственно начало и конец процесса вычисления.
4. Программа машины - конечное множество слов специального вида, называемых командами. Каждая команда имеет вид: qi аj ® ak D ql ,
где ® - спец. символ, не входящий ни в A, ни в Q; используется для наглядности;
аj, ak - внешние символы;
qi, ql - внутренние состояния; при этом qi - не заключительное (оказавшись в заключительном состоянии, машина должна закончить работу);
Сдвиг D (displacement) — одна из трех букв L (влево), R (вправо), E (на месте).
Часть команды, стоящую слева от стрелки, назовем левой частью, а справа от стрелки - правой частью. Программа должна удовлетворять следующему условию: если левые части двух входящих в программу команд совпадают, то совпадают и правые; это условие обеспечивает выполнение свойства детерминированности.
Каждая команда представляет собой предписание, в соответствии с которым выполняется очередной шаг вычисления: если машина находится в состоянии qi и головка обозревает ячейку с символом аj, то после команды qi аj ® ak D ql
- в обозреваемой ячейке символ аj стирается и вместо него записывается аk;
- головка сдвигается на 1 ячейку влево при D=L, вправо при D=R, остается на месте при D=E;
- машина переходит в состояние ql.
Если окажется, что машина находится в состоянии qi и головка обозревает ячейку, в которой записан символ аj, а программа вообще не содержит команды с левой частью qi аj, то вычисление прекращается.
Примеры.
1. Машина с алфавитом А={l, a1=1, a2=2,}, состояниями {q1, q0} и системой команд
(1) q1 1 ® 1 R q1 %сдвинуться вправо
(2) q1 2 ® 1 R q1 %заменить 2 на 1 и сдвинуться вправо
(3) q1 l ® l E q0 %встретив пустую ячейку, остановиться
заменит в исходном слове все двойки на единицы.
2. Машина с алфавитом А={l, 1}, состояниями {q1, q0} и системой команд
(1) q1 1 ® 1 R q1 %сдвинуться вправо
(2) q1 l ® 1 R q1 %заменить пустой символ на единицу
из любой начальной конфигурации будет работать ¥, заполняя 1-ми всю ленту вправо от начальной точки.
Исходными данными машины Тьюринга будем считать записанные на ленте слова в алфавите исходных данных Аисх (Аисх ÍА) и векторы Vисх из таких слов.
Для любого вектора Vисх машина Тьюринга либо работает бесконечно, либо перерабатывает его в совокупность слов в алфавите, который назовем алфавитом результатов и обозначим Арез ; Аисх и Арез могут пересекаться и даже совпадать. В общем случае, А=АисхÈАрезÈ{l}.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)