- •Введение
- •1. Теория множеств
- •1.1. Основные понятия
- •1.2. Операции над множествами
- •1.3. Алгебраические свойства операций над множествами
- •1.4. Нечёткие множества
- •2. Элементы комбинаторики
- •2.1. Основные правила комбинаторики
- •2.2. Выборки элементов без повторений
- •2.3. Выборки элементов с повторениями
- •2.4. Объединение комбинаторных конфигураций
- •2.5. Бином Ньютона
- •3. Отношения на множествах
- •3.1. Декартово произведение множеств
- •3.2. Булев куб и его свойства
- •3.3. Понятие отношения
- •3.4. Операции над отношениями
- •3.5. Свойства отношений на множестве
- •3.6. Отношения эквивалентности, толерантности и порядка
- •3.7. Нечеткие отношения
- •3.8. Понятие отображения
- •3.9. Алгебраическая операция
- •3.10. Общие сведения об алгебраических системах
- •4 Булевы функции
- •4.1. Основные определения и операции над высказываниями
- •4.2. Типы пф.
- •4.3. Равносильность формул
- •4.4. Дизъюнктивные и конъюнктивные нормальные формы
- •4.5 Алгоритм приведения пф к нормальным формам
- •4.6 Аналитический способ приведения к сднф
- •4.7. Табличный способ приведения к сднф
- •4.8. Табличный способ приведения к скнф
- •4.9. Логическое следствие
- •4.10. Алгоритм проверки правильности рассуждений
- •4.11. Алгоритм определения всех логических следствий из данных посылок
- •4.12. Алгоритм определения всех посылок, логическим следствием которых является данная формула
- •4.13. Полнота систем булевых функций
- •4.14. Полином Жегалкина
- •4.15. Замкнутость
- •4.16. Теорема Поста
- •4.17. Нечеткая логика
- •5. Многозначные функции
- •5.1. Функции и формулы k-значной логики
- •5.2. Полнота и замкнутость функций k-значной логики
- •5.3. Особенности k – значной логики
- •6.. Основные понятия теории графов.
- •6.1. Задачи теории графов.
- •6.2. Основные определения.
- •6.3. Степени вершин графа.
- •6.4. Изоморфизм графов.
- •6.5. Матричные способы задания графов.
- •6.6. Основные операции над графами.
- •6.7. Маршруты в графах
- •6.8. Связность в графах.
- •Связность и матрица смежности графа.
- •6.9. Матрица взаимодостижимости.
- •6.10. Деревья Свободные деревья.
- •Ориентированные, упорядоченные и бинарные деревья.
- •6.11. Эйлеровы графы.
- •6.12 Гамильтоновы графы.
- •6.13. Планарные графы.
- •6.14. Потоки в сетях. Основные определения.
- •Теорема Форда и Фалкерсона.
- •Алгоритм построения максимального потока в сети.
- •7. Конечные автоматы
- •7.1. Понятие конечного автомата Общие сведения о конечных автоматах
- •7.2. Абстрактное определение конечного автомата
- •7.3. Автоматная функция и её моделирование Понятие ограниченно детерминированной функции
- •Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •7.4. Эксперименты с автоматами
- •8. Рекуррентные уравнения
- •8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения
- •8.2. Решение линейного неоднородного рекуррентного уравнения
- •8.3. Решение рекуррентного уравнения для чисел Фибоначчи
- •Заключение
- •Библиографический список
- •Оглавление
- •1.Теория множеств 5
- •2 Элементы комбинаторики 14
- •3 Отношения на множествах 22
- •4. Булевы функции 42
- •5. Многозначные функции 64
- •6. Основные понятия теории графов 70
- •7. Конечные автоматы 106
- •8. Рекуррентные уравнения 120
- •394026 Воронеж, Московский просп., 14
7.4. Эксперименты с автоматами
Эксперимент с автоматами — это способ получений информации о внутренней структуре автоматов по их поведению. Основная задача экспериментов — получить сведения о строении автомата путем наблюдения его реакции на внешние воздействия.
Рассмотрим автоматы, в которых не выделены начальные состояния. В этом случае автомат задается пятеркой (A,S,B,φ, ). Множество всех конечных слов в алфавите обозначается . Пусть автомат (A,S,B,φ, ) находится в состоянии и на вход подаётся слово . Тогда на выходе будет некоторое слово и после подачи всего слова автомат оказывается в состоянии . Раcширяя функции и , положим .
Определение 1. Два состояния и автомата (A,S,B,φ, ) называются отличимыми, если существует входное слово такое, что . При этом слово называется экспериментом, отличающим от . Длину слова I( ) называют длиной эксперимента.
Теорема (Мура). Если в автомате состояния и отличимы и , то существует эксперимент , отличающий и , длина которого .8.
8. Рекуррентные уравнения
8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения
Рекуррентным соотношением (уравнением, рекуррентной формулой) называется соотношение вида
,
которое позволяет вычислить все члены последовательности a0,a1,a2,.., если заданы её первые k членов.
k – порядок рекуррентного уравнения.
Примеры. 1) an+1 = an + d -–арифметическая прогрессия.
2) an+1 = q ∙ an -–геометрическая прогрессия.
3) an+2 = an + an+1 -–последовательность чисел Фибоначчи.
В случае, когда рекуррентное уравнение линейно и однородно, то есть выполняется соотношение вида
Последовательность a0, a1, a2,.., удовлетворяющая данному уравнению называется возвратной.
Многочлен
называется характеристическим многочленом для возвратной последовательности .
Корни этого многочлена называются характеристическими. Множество всех последовательностей, удовлетворяющих рекуррентному уравнению (1) называется его общим решением.
Общее решение однородного линейного рекуррентного уравнения имеет аналогию с решением линейного дифференциального уравнения. А именно, справедливы теоремы.
Теорема 1. Пусть - корень характеристического многочлена (2), тогда последовательность , где c – производная константа, удовлетворяет уравнению (1).
Теорема 2. Если - простые корни характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:
,
где c1,c2,..,ck – произвольные константы.
Теорема 3. Если - корень кратности (i = 1,2,..,s) характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:
где cij – произвольные константы.
Зная общее решение рекуррентного уравнения (1), по начальным условиям a0, a1,.., ak-1, можно найти неопределенные постоянные cij, и, тем самым, получить частное уравнении (1) с данными начальными условиями.
Пример. Найти последовательность {an}, удовлетворяющую рекуррентному уравнению
Характеристический многочлен
8.2. Решение линейного неоднородного рекуррентного уравнения
Рассмотрим линейное неоднородное рекуррентное уравнение
an+k + p1an+k-1 + … + pkan = f(n), (n = 0, 1, 2,…) (3)
Пусть {bn} – общее решение однородного уравнения (1). {cn} – частное (конкретное) решение неоднородного уравнения (3).
Тогда последовательность {bn + cn} образует общее решение уравнения (3). Таким образом, справедлива теорема.
Теорема 4. Общее решение линейного неоднородного рекуррентного уравнения представляется в виде суммы общего решения соответствующего линейного однородного рекуррентного уравнения и некоторого частного решении неоднородного уравнения.
В результате, задача нахождения общего решения неоднородного уравнения (3) сводится к нахождению его частного решения. В отдельных случаях имеются рецепты нахождении частного решения.
1сли f(n) = βn, (где β не является корнем характеристического уравнения), то частное решение следует искать в виде cn = Cβn . Тогда, подставляя его в (3), получаем:
.
Отсюда
В результате, частное решение задаётся формулой
Пусть f(n)–многочлен степени r от переменной n, и число 1 не является характеристическим корнем. Тогда и частное решение следует искать в виде
Подставляя cn в (3) вместо an, получаем
Сравнивая коэффициенты левой и правой частей полученного равенства, найдём соотношения для чисел di, позволяющие эти числа определить.
Пример. Найти решение рекуррентного уравнения
с начальным условием .
Решение. Рассмотрим характеристический многочлен данного рекуррентного уравнения
.
Его корень . Тогда по теореме 1 общее решение соответствующего однородного рекуррентного уравнения задаётся формулой , где – произвольная константа.
Так как , т.е. единица не является корнем характеристического многочлена, а правая часть есть многочлен первой степени, то частное решение неоднородного уравнения ищется в виде полинома первой степени с неопределёнными коэффициентами , где и – неизвестные коэффициенты. Подставив вместо в исходное уравнение, получим или . Приравнивая коэффициенты левой и правой части последнего равенства, получаем систему уравнений для определения неизвестных и :
.
Отсюда, находим: и . Таким образом, частное решение исходного уравнения имеет вид . По теореме 4 получаем общее решение неоднородного рекуррентного уравнения . Из начального условия . В результате, окончательно имеем: .