Учебно-методический комплекс дисциплины опд. В 1 дополнительные главы дискретной математики основная образовательная программа подготовки специалиста по специальности 010200 (010501) «Прикладная математика и информатика»

ГЛАВА II. РЕКУРРЕНТНЫЕ УРАВНЕНИЯ (РУ) § 1. Основные определения Задача Фибоначчи. Пара кроликов приносит 1 раз в 1 месяц приплод − девочку и мальчика. Через 1 месяц после рождения крольчата вырастают и через 2 месяца после рождения приносят приплод. Сколько пар кроликов набралось к концу года, если в начале года была 1 пара (в течение года кролики не умирали, воспроизводство не прекращалось)? Составим математическую модель задачи. Обозначим f(n+1) − количество пар кроликов по истечении (n+1) месяца с начала года. Тогда через месяц количество пар кроликов составит: f(n+2) = f(n+ 1) + f(n), причём f(0) = 1, f(1) = 2. Решением этой задачи является последовательность Фибоначчи: 1, 2, 3, 5, 8, 13, 21, …, f(12) = 377, … Чтобы получить выражение для f(n) в симметричном виде, к этой последовательности слева добавляют единицу: 1, 1, 2, 3, 5, 8, 13,…, т.е. считают, что f(0) = f(1) = 1. Общий вид РУ: f(n+k) = F(n, f(n+k−1), …, f(n)), (1.1) где k − порядок РУ, f(n) − неизвестная числовая последовательность, F − функция от (k+1)-й переменной. Последовательность a(n) называется решением РУ (1.1), если при подстановке её в (1.1) вместо f(n) получается истинное равенство при n=0,1,2,... В общем случае РУ имеет бесконечное множество решений. Чтобы однозначно определить решение РУ (1.1), следует задать k начальных условий: f(0) = 0, f(1) = 1, …, f(k−1) = k−1. Пусть C1, C2,…,Ck − независимые числовые параметры. Последовательность Ф(C1, C2,…,Ck, n) называется общим решением РУ (1.1), если при любом выборе параметров C1, C2,…,Ck последовательность является решением (1.1), для любого решения a(n) можно так подобрать значения параметров C1*, C2*,…,Ck*, что равенство a(n) = Ф(C1*, C2*,…,Ck*, n) выполняется при n=0,1,2,... Решение, полученное из общего решения при фиксированном значении параметров, называется частным решением РУ (1.1). § 2. Линейные РУ с постоянными коэффициентами РУ вида f(n+k) = 1 f(n+k−1) + 2 f(n+k−2) + … + k f(n) + (n), где k > 0, (2.1) называется линейным РУ с постоянными коэффициентами; РУ вида f(n+k) = 1 f(n+k−1) + 2 f(n+k−2) + … + k f(n), где k > 0, (2.2) называется линейным однородным РУ с постоянными коэффициентами. Последовательности, являющиеся решением РУ (2.2), называются возвратными. Теорема 2.1. Общее решение РУ (2.1) можно представить в виде суммы общего решения однородного РУ (2.2) и какого-нибудь частного решения РУ (2.1). Лемма 2.1. Если а(n) и b(n) − решения однородного РУ (2.2), то для ,   R последовательность  а(n) +  b(n) − тоже решение однородного РУ (2.2). Лемма 2.2. Для m  N выражение является многочленом от n степени j−1. Пусть 0, 1, …, k − некоторые числа, причём 0  0. Составим многочлен: Pm (x) = i (k − i)m xk − i, (2.3) где m  {0, 1, 2, …, k}. Лемма 2.3. Если   0 − корень кратности r (1  r  k)многочлена P0 (x), то P0 () = P1 () = … = Pr−1 () = 0, а Pr ()  0. Уравнение zk − 1 zk−1 − 2 zk−2 − … − k = 0 (2.4) называется характеристическим уравнением для однородного РУ (2.2) Теорема 2.2. о линейных однородных РУ. Пусть а(n) − числовая последовательность, причём аi, i  C (множеству комплексных чисел), k  0. Тогда равносильны следующие три утверждения: 1. последовательность а(n) − решение однородного РУ (2.2); 2. производящую функцию последовательности а(n) можно представить в виде: а(x) = P(x) / Q(x), где Q(x) = 1 − 1 x − 2 x2 − … − k xk, P(x) − многочлен степени не выше k−1; 3. последовательность а(n) можно представить в виде: а(n) = Ri (n) in , где 1, 2, …, s − различные корни характеристического уравнения соответственно кратности r1, r2, …, rs, а Ri (n) − многочлен степени не выше ri − 1 (i = 1, 2, …, s). Перейдём к решению уравнения (2.1). Пусть (n) = Rm (n) n, где Rm (n) − многочлен аргумента n степени m, n  0. В этом случае частное решение уравнения (2.1) можно подобрать в виде: 1. Qm (n) n, если  не является корнем характеристического уравнения (2.4); 2. Qm (n) n nr, если  − корень характеристического уравнения (2.4) кратности r. Коэффициенты многочлена Qm (n) определяются путём подстановки решения Qm (n) n (Qm (n) n 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 будем употреблять греческую букву . Состояние 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. Машина с алфавитом А={, a1=1, a2=2,}, состояниями {q1, q0} и системой команд (1) q1 1  1 R q1 %сдвинуться вправо (2) q1 2  1 R q1 %заменить 2 на 1 и сдвинуться вправо (3) q1    E q0 %встретив пустую ячейку, остановиться заменит в исходном слове все двойки на единицы. 2. Машина с алфавитом А={, 1}, состояниями {q1, q0} и системой команд (1) q1 1  1 R q1 %сдвинуться вправо (2) q1   1 R q1 %заменить пустой символ на единицу из любой начальной конфигурации будет работать , заполняя 1-ми всю ленту вправо от начальной точки. Исходными данными машины Тьюринга будем считать записанные на ленте слова в алфавите исходных данных Аисх (Аисх А) и векторы Vисх из таких слов. Для любого вектора Vисх машина Тьюринга либо работает бесконечно, либо перерабатывает его в совокупность слов в алфавите, который назовем алфавитом результатов и обозначим Арез ; Аисх и Арез могут пересекаться и даже совпадать. В общем случае, А=АисхАрез{}. Рассмотрим машину Тьюринга U, которая обладает следующим свойством: если записать на ее ленте программу произвольной машины Тьюринга М и произвольное слово во внешнем алфавите этой машины, она переработает это слово так же, как переработала бы его машина М. Такую машину называют универсальной. Доказано, что машина U существует. § 2. Функция, вычислимая по Тьюрингу Пусть f  функция, отображающая множество векторов Vисх над Аисх в множество векторов Vрез над Арез. Машина Тьюринга правильно вычисляет функцию f, если: 1. для любых v и w, таких, что f(v)=w, выполняется: q1 v w q0 ; 2. для любого v, такого, что f(v) не определена, машина Т, запущенная в начальной конфигурации q1 v, работает бесконечно. Если для f существует машина Т, которая ее правильно вычисляет, функция f называется правильно вычислимой по Тьюрингу. С другой стороны, всякой правильно вычисляющей МТ, т.е. машине, которая, начав со стандартной начальной конфигурации q1 , может остановиться только в стандартной заключительной ситуации q0, можно поставить в соответствие вычисляемую ею функцию. Определения, связанные с вычислением функций, заданных на словарных векторах, даны с явным “запасом общности” и имеют в виду переработку нечисловых объектов. В дальнейшем будут рассматриваться числовые функции: f: Nk  N или f: Nk  B = {0, 1} (k  N).

Похожие:

	Учебно-методический комплекс дисциплины опд. В. 4 Математические... Целями изучения дисциплины являются: формирование профессиональных навыков по изучению, анализу и оптимизации экономических процессов...		Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Дополнительные главы дискретной математики. Учебно-методический комплекс. Рабочая программа для студентов очной формы...
	Учебно-методический комплекс дисциплины дс компьютерные сети и системы... Рецензенты: кандидат физико-математических наук, доцент Маренич А. С., кандидат технических наук, доцент Ланина Н. Р		Учебно-методический комплекс дисциплины опд. Ф. 25 (опд. Ф. 13) «Специальная психология» Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. Ф. 25 (опд. Ф. 13) «Специальная психология» Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины опд. Ф. 11 Основы коммуникативной... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. Ф. 10, Опд. Ф. 12, Опд.... А. В. Прялухина, кандидат психологических наук, доцент, зав кафедрой психологии Российского государственного социального университета...		Учебно-методический комплекс дисциплины опд. Ф. 21 Методы географических... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. В 2 опд. В 1 Современный... Педагогика и методика начального образования со специализацией «Обучение информатике в начальной школе»		Учебно-методический комплекс гсэ. В 1 история математической науки... Автор программы: кандидат физ мат наук, доцент кафедры математики и мом локоть Наталья Васильевна
	Учебно-методический комплекс фтд: универсальная алгебра основная... ...		Учебно-методический комплекс дисциплины опд. Ф. 8 Религиоведение... Пащенко Л. В., к ф н., старший преподаватель кафедры связей с общественностью и лингвистики мгту
	Учебно-методический комплекс дисциплины математическая логика Основная... Автор программы: Шиманский Сергей Александрович, ст преподаватель кафедры информатики и отд		Учебно-методический комплекс дисциплины опд. Ф. 4 История религии... ...
	Учебно-методический комплекс дисциплины фтд. 1 Основы кинезиологии... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины опд. Ф. 2 Геоморфология основная... Цель дисциплины. В соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности...