практические занятия
3. Н., А. Курс дискретной математики. М.: Издательство МАИ, 1992. - 264 с.
1.9 Материально-техническое обеспечение дисциплины.
1.9.1 Электронный конспект лекций
1.10 Примерные зачетные тестовые задания.
Контрольная работа №1. «Производящие функции и рекуррентные уравнения»
Пример одного варианта
1. Даны последовательности: 2, 3, 6, 11, 18, 27, 38, 51, ... и 6, 36, 216, 1296, ...
а) Составить их ПФ a(x), b(x) и вычислить коэффициент при x3 в произведении
a(x) × b(x);
б) Составить их ЭПФ ae(x), be(x) и вычислить коэффициент при x2 в произведении ae(x) × be(x).
2. По данной ПФ восстановить числовую последовательность:
a*(x) = (2x2 + 13x + 27) / (4 + x)3
3. Решить уравнение:
f(n+4) = 2 f(n+3) + 12 f(n+2) + 14 f(n+1) + 5 f(n)
при заданных начальных условиях: f(0) = 4, f(1) = 1; f(2) = 34; f(3) = 107.
4. Решить уравнение:
f(n+2) = -7 f(n+1) + 18 f(n) + (- 44n - 8) 2n;
при заданных начальных условиях: f(0) = 11, f(1) = 0.
Контрольная работа №2 «Теория алгоритмов»
Пример одного варианта
l | 1 | 1. Изображая на каждом такте работы машины Тьюринга получающуюся конфигурацию, определите, в какое слово перерабатывает машина каждое из следующих слов (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ l, в следующей слева ячейке уже записан символ 1): а) l11l1111l, б) l1111l11111l, в) l11l11l111111l. 2. Доказать, что функция f(x) = x! примитивно-рекурсивна.. | |
q1 | l L q2 | 1 E q0 | |
q2 | l E q5 | l E q3 | |
q3 | l L q4 | 1 E q0 | |
q4 | 1 E q5 | 1 L q4 | |
q5 | l E q0 | 1 L q6 | |
q6 | l E q0 | l E q7 | |
q7 | l R q8 | 1 E q0 | |
q8 | 1 E q9 | 1 R q8 | |
q9 | l E q0 | 1 L q10 | |
q10 | l E q0 | l E q11 | |
q11 | l L q12 | 1 E q0 | |
q12 | 1 E q13 | 1 L q12 | |
q13 | l E q0 | 1 E q0 |
1.11 Примерный перечень вопросов к зачету (экзамену).
Производящие функции и их применение
1. Алгебра отношений. Биномиальная алгебра. Доказательство того факта, что обе алгебры являются целостными кольцами
2. Формальные степенные ряды (ФСР). Композиция ФСР. Условие, при котором осуществима композиция (с доказательством)
3. Формальные степенные ряды (ФСР). Обратимость ФСР. Условие существования обратного ряда (с доказательством)
4. Формальные степенные ряды (ФСР). Интегрирование и дифференцирование ФСР (с доказательством любых двух свойств).
5. Производящая функция (ПФ). Экспоненциальная ПФ. Основной принцип теории ПФ.
6. Операции над ПФ: линейные, изменение масштаба, сдвиг начала, подобие, свёртка (с доказательством).
7. Применение ПФ к решению перечислительных задач: сочетания, сочетания с повторениями, размещения, размещения с повторениями.
8. Применение ПФ к решению перечислительных задач: композиции, разбиения.
Рекуррентные уравнения
9. Рекуррентные уравнения. Основные определения. Задача Фибоначчи.
10. Линейные рекуррентные уравнения с постоянными коэффициентами. Теорема о виде общего решения (с доказательством).
11. Однородные линейные рекуррентные уравнения с постоянными коэффициентами. Теорема об общем решении (с доказательством).
12. Пути решения нелинейных рекуррентных уравнений.
Теория алгоритмов
13. Определение машины Тьюринга, ее четыре составные части: лента, читающая головка, алфавиты и множество команд.
14. Конструирование машин Тьюринга на примере машины, стирающей последний символ исходного слова и машины, дописывающей три единицы к исходному слову.
15. Проблема остановки машины Тьюринга (с доказательством).
16. Тезис Черча-Тьюринга, его научный “статус” и применение в теории алгоритмов.
17. Проблема распознавания нетривиального инвариантного свойства машины Тьюринга (с доказательством).
18. Эквивалентные машины Тьюринга. Примеры эквивалентных машин.
19. Оператор суперпозиции. Оператор примитивной рекурсии. Определение примитивно-рекурсивной функции.
20. Примеры построения примитивно-рекурсивных функций.
21. Примитивно-рекурсивные операторы. Ограниченный оператор минимизации. Оператор обращения.
22. Функции Аккермана и их свойства.
23. Доказательство того факта, что функция Аккермана не является примитивно-рекурсивной.
24. Общерекурсивные и частично-рекурсивные функции.
1.12 Комплект экзаменационных билетов.
Билет № 1.
1. Теорема о целостных кольцах.
2. Функция Аккермана и её свойства.
Билет № 2.
1. Композиция формальных степенных рядов. Условие существования композиции.
2. Неразрешимая алгоритмическая проблема - проблема распознавания нетривиального инвариантного свойства.
Билет № 3.
1. Обратимость формальных степенных рядов. Условие существования обратного ряда.
2. Теорема о том, что функция Аккермана не является примитивно-рекурсивной.
Билет № 4.
1. Вывод формулы дифференцирования произведения формальных степенных рядов.
2. Ограниченный и неограниченный оператор минимизации. Оператор обращения. Частично-рекурсивные и общерекурсивные функции.
Билет № 5.
1. Шесть операций над производящими функциями, соответствующих операциями над числовыми последовательностями.
2. Неразрешимая алгоритмическая проблема - проблема остановки.
Билет № 6.
1. Производящие функции числа сочетаний, сочетаний с повторениями. Число сочетаний с повторениями без ограничения на кратность элементов.
2. Схема примитивной рекурсии. Примитивно-рекурсивные функции: определение, примеры (с доказательством примитивной рекурсивности).
Билет № 7.
1. Экспоненциальные производящие функции числа размещений, размещений с повторениями. Число размещений с повторениями без ограничения на кратность элементов.
2. Теорема о том, что функция Аккермана не является примитивно-рекурсивной.
Билет № 8.
1. Производящие функции числа композиций (на m частей, на произвольное количество частей).
2. Функция Аккермана и её свойства.
Билет № 9.
1. Производящие функции числа разбиений на m частей. Число решений в целых неотрицательных числах уравнения x1 + 2x2 + 3x3 + ... + mxm = k.
2. Неразрешимая алгоритмическая проблема - проблема распознавания нетривиального инвариантного свойства.
Билет № 10.
1. Теорема об общем виде решения линейного рекуррентного соотношения с постоянными коэффициентами.
2. Машина Тьюринга. Примеры машин Тьюринга. Функция, вычислимая по Тьюрингу. Тезис Чёрча-Тьюринга.
Билет № 11.
1. Лемма о нулях многочлена Pm(x) = 
bi (k-i)m xk-i.
2. Ограниченный и неограниченный оператор минимизации. Оператор обращения. Частично-рекурсивные и общерекурсивные функции.
Билет № 12.
1. Основная теорема об линейных однородных рекуррентных соотношениях: 1 Þ 2 (если an - решение... , то ее производящая функция представима в виде...).
2. Неразрешимая алгоритмическая проблема - проблема остановки.
Билет № 13.
1. Основная теорема об линейных однородных рекуррентных соотношениях: 2 Þ 3 (если производящая функция представима в виде... , то an представима в виде...).
2. Схема примитивной рекурсии. Примитивно-рекурсивные функции: определение, примеры (с доказательством примитивной рекурсивности).
Билет № 14.
1. Основная теорема об линейных однородных рекуррентных соотношениях: 3 Þ 1 (если an представима в виде... , то an - решение... ).
2. Машина Тьюринга. Примеры машин Тьюринга. Функция, вычислимая по Тьюрингу. Тезис Чёрча-Тьюринга.
1.13 Примерная тематика рефератов.
Треугольник Паскаля и его свойства.
Последовательность Фибоначчи и её свойства.
Универсальная машина Тьюринга и способ ее построения.
1.14 Примерная тематика курсовых работ.
Свойства интегралов для формальных степенных рядов.
Решение рекуррентных уравнений путём сведения их к дифференциальным уравнениям.
Подходы к решению нелинейных рекуррентных уравнений.
Примитивная рекурсивность функции, перечисляющей по порядку числа Фибоначчи.
1.15. Примерная тематика квалификационных (дипломных) работ.
не предусмотрено учебным планом по данной дисциплине.
1.16. Методика(и) исследования (если есть) - нет.
1.17. Бально-рейтинговая система, используемая преподавателем для оценивания знаний студентов по данной дисциплине.
Используется пятибалльная система оценивания знаний студентов.
РАЗДЕЛ 2. Методические указания по изучению дисциплины (или ее разделов) и контрольные задания для студентов заочной формы обучения.
Нет заочной формы обучения по данной дисциплине.
РАЗДЕЛ 3. Содержательный компонент теоретического материала.
Примерное содержание лекционного материала.
ГЛАВА I. ПРОИЗВОДЯЩАЯ ФУНКЦИЯ
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)