ДИСКРЕТНА МАТЕМАТИКА

·        Детерміновані функції. Визначення. Представлення детермінованих функцій деревами.

·        Обмежено-детерміновані функції. Діаграми Мура. Оцінка числа функцій в класі P. Канонічні рівняння, які визначають обмежено-детерміновані функції.

·        Машини Тьюрінга: опис, загальні визначення. Машини Тьюрінга та обчислюванні функції. Машинні коди машини Тьюрінга.

·        Операції суперпозиції та примітивної рекурсії. Операція мінімізації. Приклад.

·        Частково-обчислюванні функції. Теза Черча.

·        Числення висловлень.

·        Логіка предикатів. Логічні операції. Формули логіки предикатів.

·        Функції алгебри логіки. Властивості "елементарних" функцій. Формули в Р₂. Реалізація функцій алгебри логіки формулами.

·        Досконала диз'юнктивна нормальна форма (ДНФ) та досконала кон'юнктивна нормальна форма (КНФ).

·        Поліном Жегалкіна. Єдиність розкладання в поліном Жегалкіна. Метод невизначених коефіцієнтів.

·        Найважливіші замкнені класи: Т₀, Т₁, S, М, L.

·        Типи ДНФ та їхні властивості. Метод Блейка побудови скороченої ДНФ.

·        Елементарні функції k-значної логіки.

·        Графи. Підграфи. Ланцюги. Цикли (основні поняття). Зв'язні графи. Орієнтовані графи.

·        Дерева. Бінарні дерева. Алгоритм побудови остова.

·        Побудувати перші 5 ярусів для функції . Визначити її ранг. Побудувати діаграму Мура, канонічну таблицю, канонічні рівняння.

·        Розкладаючи функцію  в поліном Жегалкіна, визначити, чи є вона лінійною. Чи є функція  монотонною? Знайти двоїсту функцію до даної функції. Чи є вона самодвоїстою?

·        Побудувати таблицю істинності.

 Основна література

1.      Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислитель­ных алгоритмов. М.: Мир, !979. - 536 с.

2.      Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной мате­матике. М.: Наука, 1977. - 386 с.

3.      Гиндикин С. Г. Алгебра логики в задачах. М.: Наука, 1972. — 288 с.

4.      Глушков В. М. Синтез цифровых автоматов. М.: ГФМЛ, 1962.-476 с.

5.      Грэхсм Р., Кнут Д., Паташник О. Конкретная математика (основание информатики). М.: Мир, 1998. - 703 с.

6.      Дискретная математика и математические вопросы кибернетики / Под ред. С. В. Яблонского и О. Б. Лупанова. М.: Паука, 1974. - 312 с.

7.      Донской В.И. Дискретная математика. Учебное пособие. Симферополь: Сонат, 2000. – 360 с.

8.      Журавлев Ю. И. Избранные научные труды. М.: Издательство Ма­гистр, 1998.- 420с.

9.      Клини С. К. Математическая логика. М.: Мир, 1973. - 480 с.

10.  Кофман А. Введениев прикладную комбинаторику. – М.: Наука, 1975.

11.  Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математи­ческой логике и теории алгоритмов. М.: Физико-математическая литература, 1995. -256с.

12.  Линдон Р. Заметки по логике. М.: Мир, 1968. - 128 с.

13.  Липский В. Комбинаторика для программистов. М.: Мир, 1988.-215 с.

14.  Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: Издательство МАИ, 1992. -  264с.

15.  Новиков П.С. Элементы математической логики. – М.: Наука, 1973.

16.  Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: теория и практика. – М.: Мир, 1980.

17.  Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. - 384 с.

 Додаткова література

1.      Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976.

2.      Гери М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -  М.: Мир, 1982.

3.      Кострикин А.И. Введение в алгебру. – М.: Наука, 1977.

4.      Комбинаторный анализ: задачи и упражнения. / Под общ. Ред. К.А. Рыбникова. – М.: Наука, 1982.

5.      Мендельсон Э. Введение в математическую логику. - М.: Наука, 1976.-320 с.

6.      Оре О. Теория графов. М.: Наука, 1980. - 336 с.

7.      Сапоженко А. А. Дизъюнктивные нормальные формы. Изд-во МГУ, 1975.-90 с.

8.      Сачков В. Н. Введение в комбинаторные методы дискретной матема­тики. М.: Наука, 1982. - 384 с.

9.      Шоломов Л. А. Основы теории дискретных логических и вычисли­тельных устройств. М.: Наука, 1980. - 400 с.

36

15

Чи можна вважати, що відношення до даної телепередачі не залежить від статіглядача? Прийняти α = 0,1.

19. Середня температура травня в Харкові вимірювалася впродовж 14 років. Дані приведені:

Побудувати довірчий інтервал для середньої температури травня для її дисперсії з довірчою вірогідністю α = 0,9, вважаючи, що середня температура є нормально розподіленою.

20. Лікар припускає, що у пацієнта одне із захворювань: Н1 (з вірогідністю 0,6) або Н2 (з вірогідністю 0,4). Для уточнення діагнозу призначений аналіз крові, який у разі діагнозу Н1 дає деякий результат А з вірогідністю 0,9, у разі діагнозу Н2 – результат А з вірогідністю 0,05. Після проведення аналізу здійснилася подія А. Найти Р(Н1/А), Р(Н2/А).