ДМ_МУ_САМ РАБ

5.Дайте стислу характеристику основних правил дедуктивного висновку.

6.Перелічить правила дедуктивних висновків логіки висловлень.

7.У чому полягає повнота і несуперечність обчислення висловлень?

8.Дайте визначення незалежної системи аксіом.

9.Сформулюйте теорему дедукції.

10.У чому полягає метод доведення від супротивного?

4.5.6 Тема 3 «Предикати. Алгебра предикатів»

Вивчення теми 3 «Предикати. Алгебра предикатів» пов’язане із розглядом таких питань [1-4, 6-8, 18-23]: основні поняття і визначення логіки предикатів; операції логіки предикатів, кванторні операції; формули та їхня інтерпретація в логіці предикатів; закони і тотожності логіки предикатів; випереджені нормальні форми.

Основними поняттями і визначеннями теми «Предикати. Алгебра предикатів», які надаються в [1-4, 6-8, 18-23], є: предикат; універс (предметна область); область визначення предиката; область значень предиката; порядок предиката; n-місний предикат (одномісний, двомісний, нульмісний предикат);

терм; предикатна змінна, індивідуальний символ; символ предметних змінних; функціональний символ; квантор загальності; квантор існування; елементарна формула логіки предикатів (атом); область дії квантора; зв’язана змінна; вільна змінна; замкнута формула; інтерпретація формули логіки предикатів;

загальнозначуща, суперечлива, здійсненна, незагальнозначуща формула; логічний наслідок; випереджена нормальна форма; алгоритм зведення до випередженої нормальної форми.

4.5.7Контрольні запитання

1.Дайте визначення поняття «предикат».

2.Що називається порядком предиката? Наведіть приклади n-місних предикатів.

3.Які типи символів дозволяється використовувати для побудови атомів логіки предикатів?

4.Дайте визначення поняття «терм».

5.Що розуміють під предметною областю?

6.Що розуміють під квантором загальності?

41

7.Дайте визначення поняття «квантор існування».

8.Які змінні називаються зв’язаними, а які вільними?

9.З чого складається інтерпретація формули логіки предикатів?

10.Поясніть, як здійснюється заміна зв’язаної змінної.

11.Сформулюйте комутативні властивості кванторів.

12.Запишіть формули закону де Моргана для кванторів.

13.Дайте визначення випередженої нормальної форми.

14.За допомогою яких законів можна опустити знаки операцій заперечення безпосередньо на предикати?

15.Яким чином можна перетворити довільну формулу логіки предикатів

увипереджену нормальну форму?

4.5.8 Тема 4 «Обчислення предикатів»

Вивчення теми 4 «Обчислення предикатів» пов’язане із розглядом таких питань [1-4, 6-8, 18-23]: вивідність у логіці предикатів; обчислення предикатів (мова, аксіоми, правила висновку).

Основними поняттями і визначеннями теми «Обчислення предикатів», які надаються в [1-4, 6-8, 18-20, 22], є: формальна система – обчислення предикатів; структура обчислення предикатів; мова обчислення предикатів; система аксіом обчислення предикатів; правила висновку обчислення предикатів; правило видалення квантора загальності; правило введення квантора загальності; правило видалення квантора; правило введення квантора існування; правило відділення; правило зв’язування квантором загальності; правило зв’язування квантором існування; правило перейменування вільних змінних; правило перейменування зв’язаних змінних.

4.5.9Контрольні запитання

1.Сформулюйте призначення обчислення предикатів.

2.Запишіть формули аксіом обчислення предикатів.

3.Поясніть обмеження аксіом обчислення предикатів.

4.Перелічите правила висновку, які можна використовувати для проведення дедуктивних умовиводів з висловленнями логіки предикатів.

5.Перелічить правила висновку обчислення предикатів.

6.Побудуйте схему правила узагальнення.

7.Сформулюйте правило перейменування вільних змінних.

42

8.В чому полягає сутність правила перейменування зв’язаних змінних?

9.Перелічите правила висновку, які можна використовувати для проведення дедуктивних умовиводів з числення логіки предикатів.

10.Сформулюйте призначення обчислення предикатів.

11.Запишіть формули аксіом обчислення предикатів.

12.Перелічить правила висновку обчислення предикатів.

4.6 Змістовий модуль 6 «Основи комбінаторного аналізу» 4.6.1 Перелік тем змістовного модуля 6

Під час вивчення змістового модуля 6 розглядаються такі теми:

тема 1 «Історія розвитку комбінаторики»;

тема 2 «Загальні визначення комбінаторики. Моделі типових комбінаторних конфігурацій»;

тема 3 «Властивості сполучень. Біном Ньютона»;

тема 4 «Принцип включення і виключення»;

тема 5 «Задачі про розподіл предметів за урнами (урнові схеми вирішення комбінаторних задач)»;

тема 6 «Підходи до вивчення комбінаторних об’єктів і чисел»;

тема 7 «Метод рекурентних співвідношень».

4.6.2 Тема 1 «Історія розвитку комбінаторики»

Вивчення теми 1 «Історія розвитку комбінаторики» пов’язане із розглядом таких питань [1, 17]: питання, які вивчає комбінаторика

(комбінаторний аналіз); задачі на перелічення; задачі про існування і побудову; задачі про вибір; суміжні задачі між комбінаторикою та теорією чисел;

кабалістики і містики у розвитку комбінаторики; астрологія і комбінаторика; схоластична наука і комбінаторика; роботи Фібоначчі з комбінаторики; «задача про кроликів» азартні ігри і комбінаторика; комбінаторний аналіз і генетика; комбінаторний аналіз і біологія в ХХ столітті; деякі класичні задачі комбінаторики (магічний квадрат, шахові задачі, латинські квадрати і блоксхеми, теорема про представників, теорема Д. Кеніга про матриці).

43

4.6.3 Контрольні запитання

1.Дайте визначення комбінаторики.

2.Поясніть, що являють собою задачі на перелічення.

3.Які задачі є задачами про існування та побудову.

4.Поясніть, що являють собою задачі про вибір.

5.Що являє собою магічний квадрат?

6.Поясніть зв’язок астрології і комбінаторики.

7.Поясніть появу «задачі про кроликів». Як її розв’язував Леонардо Пізанський (Фібоначчі)?

8.Поясніть на прикладах комбінаторний зміст деяких задач генетики та

біології.

4.6.4 Тема 2 «Загальні визначення комбінаторики. Моделі типових комбінаторних конфігурацій»

Вивчення теми 2 «Загальні визначення комбінаторики. Моделі типових комбінаторних конфігурацій» пов’язане із розглядом таких питань [1-5, 7, 1117, 19-23]: комбінаторні задачі; основні правила розв’язання задач комбінаторики (правило суми и правило добутку); приклади використання правила суми и правила добутку при розв’язанні комбінаторних задач;

складний вибір предметів; перелік і визначення типових (елементарних) комбінаторних конфігурацій (перестановки, розміщення, сполучення,

композиції; розбиття).

Основними поняттями і визначеннями теми «Загальні визначення комбінаторики. Моделі типових комбінаторних конфігурацій», які надаються в [1-5, 7, 14-17, 20, 22], є: r-вибірка; правило суми; правило добутку; сполучення;

розміщення; перестановка; композиція числа; розбиття числа; кількість розміщень без повторень; кількість розміщень з повтореннями; кількість перестановок без повторень; кількість перестановок з повтореннями; кількість сполучень без повторень; кількість сполучень з повтореннями; число всіх композицій числа; кількість всіх варіантів розбиття числа.

44

4.6.5 Контрольні запитання

1.Що являє собою r-вибірка?

2.Сформулюйте правило суми для комбінаторних задач. Поясніть на прикладі використання правила суми.

3.Сформулюйте правило добутку для комбінаторних задач. Яка формула використовується у правилі добутку?

4.Надайте визначення перестановки k-елементів.

5.Надайте визначення розміщення з n по k елементів.

6.Що являє собою розміщення з повтореннями з n по k елементів. За якою формулою обчислюється кількість k-розміщень з повтореннями з n по k

елементів.

7.За якою формулою обчислюється кількість k-сполучень з n елементів по k елементів з повтореннями і без повторень.

8.Надайте визначення композиції числа.

9.За якою формулою визначається кількість всіх варіантів розбиття числа n на k частин?

4.6.6 Тема 3 «Властивості сполучень. Біном Ньютона»

Вивчення теми 3 «Властивості сполучень. Біном Ньютона» пов’язане із розглядом таких питань [1-5, 7, 11-17, 19-23]: властивості біноміальних коефіцієнтів (властивість симетрії, властивості додавання, властивості винесення за дужки); арифметичний трикутник (трикутник Паскаля), числові й символічні трикутники Паскаля; правила побудови трикутника Паскаля;

властивості трикутників Паскаля; таблична формула трикутників Паскаля; біноміальна формула (біном Ньютона) та її використання; біноміальні коефіцієнти, їх знаходження; обчислення біноміальних коефіцієнтів за допомогою явних формул; обчислення біноміальних коефіцієнтів за допомогою рекурентних формул; обчислення біноміальних коефіцієнтів на основі побудови числових послідовностей; обчислення Cnk на основі біноміальних квадратів і прямокутників; біном Ньютона; властивості бінома Ньютона;

поліноміальна формула та її використання.

45

4.6.7 Контрольні запитання

1.Дайте визначення трикутника Паскаля й поясніть принцип його побудови.

2.Що таке числові й символічні трикутники Паскаля?

3.Які існують властивості трикутників Паскаля?

4.Побудуйте табличну форму трикутників Паскаля. У чому полягають переваги й недоліки такої побудови?

5.Що таке сполучення і біноміальні коефіцієнти?

6.Перелічить властивості сполучень, які випливають з арифметичного трикутника.

7.В чому полягають властивості симетрії для біноміальних коефіцієнтів?

8.В чому полягають властивості додавання для біноміальних коефіцієнтів?

9.В чому полягають властивості винесення за дужки для біноміальних коефіцієнтів?

10.Наведіть формулу, яка називається «біном Ньютона».

11.Наведіть формулу, яка називається поліноміальною формулою.

4.6.8 Тема 4 «Принцип включення і виключення»

Вивчення теми 4 «Принцип включення і виключення» пов’язане із розглядом таких питань [1-5, 7, 11-17, 19-23]: комбінаторний принцип включення і виключення (підрахування кількості предметів, позбавлених всіх без виключення властивостей); загальна формула включень та виключень;

приклади використання формули включень та виключень; частковий випадок теореми включення і виключення; формула «повного безладдя» (субфакторіал).

4.6.9Контрольні запитання

1.Надайте загальну постановку задачі, для розв’язання якої використовують принцип включення і виключення.

2.Запишіть загальну формулу включень та виключень.

3.Наведіть приклади застосування принципу включення і виключення при розв’язанні комбінаторних задач.

4.Доведіть загальну теорему включень та виключень методом індукції.

46

5. У яких випадках використовується формула «повного безладдя»

(субфакторіал)?

4.6.10 Тема 5 «Задачі про розподіл предметів за урнами (урнові схеми вирішення комбінаторних задач)»

Вивчення теми 5 «Задачі про розподіл предметів за урнами (урнові схеми вирішення комбінаторних задач)» пов’язане із розглядом таких питань [1, 3, 17, 20, 22]: аналіз змісту задач при розв’язанні задач про розміщення (розподіл предметів за урнами); розподіл n різних предметів за k урнами; розподіл n однакових предметів за k урнами; розподіл різних предметів без урахування порядку предметів в урнах; розподіл різних предметів між однаковими урнами за умови, що урни не порожні; розподіл різних предметів з урахуванням їх порядку в урнах.

4.6.11 Контрольні запитання

1.Як проводиться аналіз змісту комбінаторних задач про розміщення предметів?

2.За якою формулою обчислюється кількість розміщень за k урнами n різних предметів?

3.За якою формулою обчислюється кількість розміщень за k урнами n однакових предметів?

4.Чи можна знайти кількість розподілів різних предметів без урахування

порядку предметів в урнах, використовуючи формулу kn ?

5.У якому випадку для розв’язання задач про розподіл предметів за урнами використовуються числа Моргана, число Стирлінга другого роду, числа Белла?

6.За якою формулою обчислюється кількість розподілів різних предметів

зурахуванням їх порядку в урнах?

4.6.12 Тема 6 «Підходи до вивчення комбінаторних об’єктів і чисел»

Вивчення теми 6 «Підходи до вивчення комбінаторних об’єктів і чисел» пов’язане із розглядом таких питань [1, 3, 16, 20, 22]: розв’язок задачі про знаходження всіх простих чисел серед натуральних від 1 до N (решето

47

Ератосфена); поняття про рекурентні співвідношення; поняття про продуктивні функції; операції над послідовностями та продуктивними функціями; продуктивні функції сполучень; продуктивні функції розміщень та перестановок; продуктивні функції для розбиття чисел.

4.6.13 Контрольні запитання

1.Яка функція називається продуктивною функцією для послідовності a0, a1,a2,..., an,... ?

2.Яка функція називається експоненціальною продуктивною функцією

для послідовності a0, a1,a2,..., an,... ?

3.Наведіть формулу, яка є продуктивною функцією для сполучень.

4.Який вигляд мають продуктивні функції для розміщень та перестановок?

5.Який вигляд має продуктивна функція для розбиття чисел?

6.Наведіть спосіб, який використав Ератосфен, для розв’язку задачі про знаходження всіх простих чисел серед натуральних від 1 до N.

4.6.14 Тема 7 «Метод рекурентних співвідношень»

Вивчення теми 7 «Метод рекурентних співвідношень» пов’язане із розглядом таких питань [1-5, 7, 14-16, 19-23]: сутність методу рекурентних співвідношень у комбінаторному аналізі; задача, яку розв’язував Леонардо Фібоначчі за допомогою рекурентного співвідношення; задача «про кроліків»;

характеристичне рівняння для рекурентного співвідношення Фібоначчі; задачі,

вяких використовуються числа Фібоначчі.

4.6.15Контрольні запитання

1.У чому полягає метод рекурентних співвідношень?

2.Проілюструйте метод рекурентних співвідношень на прикладі сполучень з повтореннями.

3.Який вигляд має задача, яку розв’язував Леонардо Фібоначчі за допомогою рекурентного співвідношення?

4.Які числа називаються числами Фібоначчі?

5.Прокоментуйте «задачу про кроліків».

48

6. Наведіть явну формулу для обчислення довільного числа Фібоначчі,

яку вперше одержав Біне.

7. Яке рівняння носить назву характеристичного рівняння для рекурентного співвідношення Фібоначчі?

4.7 Змістовий модуль 7 «Основи теорії кодування» 4.7.1 Основні положення теорії кодування

Вивчення матеріалів змістового модуля 7 «Основи теорії кодування» пов’язане із розглядом таких питань [14, 20]: формулювання задачі кодування; типова задача теорії кодування; алфавітне кодування; розділимі схеми кодування; префіксні схеми кодування; приклади схем алфавітного кодування (азбука Морзе); кодування з мінімальною надлишковістю (оптимальне кодування); мінімізація довжини коду повідомлення; ціна (довжина) кодування; рекурсивні алгоритми кодування (алгоритм Фано, алгоритм Хаффмена);

використання завадостійкого кодування (кодування з виправленням помилок); класифікація похибок; стиснення даних; стиснення текстів; алгоритм Лемпела-

Зіва; захист комп’ютерних даних від несанкціонованого доступу; кодування даних з метою захисту від несанкціонованого доступу (шифрування); область знань про шифри, методи їх створення і розкриття (криптографія, тайнопис); використання шифрів з відкритим ключем.

Основними поняттями і визначеннями змістового модуля «Основи теорії кодування», які надаються в [14, 20], є: кодування; код; декодування; двійкове кодування; m-ічне кодування; алфавіт; буква; слово; порожнє слово; префікс слова; постфікс слова; таблиця кодів; нерівність Макмиллана; завадостійкість;

складність (простота) кодування; ціна (довжина) кодування; оптимальний код Хаффмена; завадостійке кодування; кодова відстань (метрика); метрика Хеммінга; код Хеммінга; стиснення; коефіцієнт стиснення; словар коду; адаптивне стиснення; шифр; шифрування; розшифрування; криптографія;

крипостійкість; гамма шифру; ключ; відкритий ключ; симетричний шифр; цифровий (електронний) підпис.

4.7.2 Контрольні запитання

1.Сформулюйте задачу кодування у формальному вигляді.

2.Поясніть десяткову позиційну систему числення як спосіб кодування натуральних чисел.

49

3.Поясніть декартову систему координат як спосіб кодування геометричних об’єктів числами.

4.Що являє собою двійкове кодування?

5.Що називається алфавітом, буквою алфавіта в теоріх кодування?

6.Поясніть особливості алфавітного кодування.

7.Якою схемою (таблицею кодів) задається алфавітне кодування?

8.Поясніть використання розділимих та префіксних схем в алфавітному кодуванні.

9.Як і для чого використовується кодування з мінімальною надлишковістю (оптимальне кодування)?

10.Надайте алгоритм Фано.ь Для чого він використоваується?

11.Який рекурсивний алгоритм будує схему оптимального префіксного алфавітного кодування для заданого розподілення ймовірностей появи букв?

12.У яких випадках використовується завадостійке кодування?

13.Що таке метрика?

14.Як можна побудувати код Хеммінга для виправлення похибки?

15.За допомогою яких методів можна здійснити стиснення текстів?

16.Чим можна визначити якість стиснення даних?

17.Наведіть алгоритм Лемпела-Зіва, який використовується для адаптивного стиснення даних.

18.Поясніть використання терміну шифрування. Яке кодування називається шифруванням?

19.Що називається криптографією?

20.Поясніть використання прийому кодування, який називається «цифровий підпис».

4.8 Змістовий модуль 8 «Основні поняття теорії графів»

4.8.1 Перелік тем змістовного модуля 8

Під час вивчення змістового модуля 8 розглядаються такі теми:

тема 1 «Зародження теорії графів як математичної дисципліни»;

тема 2 «Походження графів. Визначення графів»;

тема 3 «Операції над графами»;

тема 4 «Ізоморфізм графів. Плоскі та планарні графи»;

тема 5 «Зв'язність графів. Ейлерові та гамільтонові графи»;

тема 6 «Цикломатика графів»;

50