Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

ДМ_Контр вопросы

.pdf
Скачиваний:
55
Добавлен:
16.03.2016
Размер:
466.24 Кб
Скачать

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

ТИПОВІ КОНТРОЛЬНІ ТА ТЕСТОВІ ЗАВДАННЯ з дисципліни

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

для студентів усіх форм навчання напряму 6.050101 – «Комп’ютерні науки»

Електронне видання

ЗАТВЕРДЖЕНО кафедрою ІУС

Протокол № 1 от 29.08.2013 р.

ХАРКІВ 2013

1

Типові контрольні та тестові завдання з дисципліни «Дискретна математика» для студентів усіх форм навчання напряму 6.050101 «Комп’ютерні науки» [Електронне видання] / Упоряд. Н.В. Васильцова, Л.Е Чала. – Харків:

ХНУРЕ, 2013. – 14 с.

Упорядники Н.В. Васильцова

Л.Е. Чала

2

Теоретичні запитання

1.Мета і задачі дисципліни, її місце в системі підготовки фахівців з комп'ютерних наук.

2.Історія зародження, розвитку і становлення дискретної математики.

Внесок вчених у її розвиток.

3.Основні поняття і позначення теорії множин. Інтуїтивне поняття множини. Способи задання множин. Потужність множин. Множина і підмножини.

4.Геометрична інтерпретація множин: кола Ейлера та діаграми Венна.

5.Операції на множинах.

6.Загальне визначення алгебри. Поняття алгебри множин. Аксіоми алгебри множин. Тотожні перетворення формул алгебри множин.

7.Поняття відношення. Бінарні та n-арні відношення. Область визначення та область значень відношення.

8.Способи задання відношень.

9.Операції над відношеннями.

10.Властивості бінарних відношень. (рефлексивність, антирефлексивність, симетричність, антисиметричність, асиметричність,

транзитивність, антитранзитивність відношень).

11.Класи бінарних відношень. Відношення еквівалентності. Класи еквівалентності. Відношення порядку. Відношення толерантності.

12.Функціональні відношення. Області визначення і значень. Функції і відображення. Типи відображень: сюр'єкція, ін'єкція, бієкція.

13.Елементи реляційної алгебри. Реляційна модель даних. Поняття реляційної алгебри. Операції реляційної алгебри.

14.Алгебраїчні операції та їх властивості. Унарна, бінарна, n-арна операція. Способи записів операцій. Основні властивості операцій. Операції додавання та множення за модулем.

15.Поняття алгебраїчної структури Підструктура. Морфізми (гомоморфізм, ізоморфізм). Найпростіші алгебраїчні структури. Кільці і поля.

Гратки.

16.Булеві змінні і функції. Область визначення та область значень булевий функцій. Способи задання булевих функцій.

17.Булева алгебра. Реалізація булевих функцій формулами. Елементарні функції алгебри логіки.

3

18. Двоїстість в булевій алгебрі. Двоїсті та самодвоїсті булеві функції.

Принцип двоїстості.

19.Закони і тотожності булевої алгебри. Еквівалентні перетворення формул булевої алгебри.

20.Нормальні форми булевих функцій. Основні поняття.

21.Досконалі нормальні форми (ДДНФ, ДКНФ). Диз’юнктивні та кон’юнктивні розкладання булевих функцій. Перехід від таблиці булевої функції до формули алгебри логіки і навпаки.

22.Мінімізація булевих функцій. Основні поняття. Критерії мінімізації.

23.Основні методи мінімізації булевих функцій. Метод мінімізуючих карт (діаграми Карно-Вейча).

24.Алгебра Жегалкіна. Структура і тотожністі алгебри Жегалкіна. Поліном Жегалкіна та правило його побудови. Лінійні булеві функції.

25.Функціональна повнота наборів булевих функцій. Типи булевих функцій. Замкнені класи булевих функцій. Теореми Поста про функціональну повноту набору булевих функцій.

26.Логічні схеми. Синтез комбінаційних схем. Перемикальні ланцюги;

двох- і багатоступінчасті комбінаційні схеми.

27.Висловлення (основні поняття). Логічні зв'язки і формули логіки вісловлень. Побудова складних формул.

28.Алгебра логіки і логіка висловлень. Інтерпретація формул логіки висловлень. Правильні міркування.

29.Обчислення висловлень. Аксіоми та повнота обчислення логіки висловлень. Висновки в обчисленні висловлень. Дедуктивні висновки у логіці висловлень. Різні аксіоматизації обчислення висловлень.

30.Основні поняття логіки предикатів. Операції логіки предикатів. Кванторні операції. Формули та їх інтерпретація у логіці предикатів.

31.Закони і тотожності логіки предикатів. Випереджені нормальні

форми.

32.Обчислення предикатів. Логічний висновок у логіці предикатів.

33.Багатозначна логіка. Основні поняття і функції k-значної логіки.

34.Історія розвитку комбінаторики. Класичні задачі комбінаторного аналізу. Сучасні задачі, які вирішуються комбінаторними методами.

35.Загальні визначення комбінаторики. Моделі типових комбінаторних конфігурацій. Поняття r-вибірки.

36.Загальні правила і задачі комбінаторики. Правила суми і добутку.

4

37.Перестановки, розміщення, сполучення (без повторень та з повтореннями).

38.Властивості сполучень. Біном Ньютона. Біноміальні коефіцієнти.

Трикутник Паскаля. Поліноміальна теорема.

39.Принцип включення і виключення. Теорема та формула включень і виключень.

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

41.Композиції і розбиття.

42.Підходи до вивчення комбінаторних об’єктів і чисел. Поняття про продуктивні функції. Поняття про рекурентні співвідношення.

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

44.Метод рекурентних співвідношень. Числа Фібоначчі.

45.Основи теорії кодування. Алфавітне кодування. Кодування з мінімальною надлишковістю. Алгоритм Фано. Алгоритм Хаффмена.

Завадостійке кодування. Стиснення даних. Криптографія.

46.Зародження теорії графів як математичної дисципліни. Типові задачі теорії графів. Походження графів.

47.Визначення графів. Різновиди графів. Неорієнтовані та орієнтовані графи. Основні терміни для неорієнтованих та орієнтованих графів.

48.Способи задання графів. Геометрична реалізація графів. Матриця суміжності. Матриця інциденцій. Число вершин і ребер графа.

49.Операції над графами. Операції вилучення ребер та вершин. Операція введення ребра, операція введення вершини у ребро. Операція об’єднання графів. Операції додавання і множення графів.

50.Ізоморфізм графів. Підграфи. Алгебраїчний критерій ізоморфізму графів. Зв'язок з відношеннями. Ізоморфізм як відношення еквівалентності.

51.Плоскі та планарні графи. Гомеоморфні графи. Теорема ПонтрягінаКуратовського. Теорема Жордана. Жорданова крива. Побудова плоского зображення графа.

52.Зв'язність графів. Ейлерові та гамільтонові графи. Поняття зв'язності графів, компонента зв'язності, n-зв'язний граф. Властивості зв'язних графів. Метричні характеристики зв'язних графів.

53.Ейлерові графи. Теорема Ейлера. Алгоритм знаходження ейлерова цикла (теорема Флері).

5

53. Гамільтонові графи. Ознаки існування гамільтонових циклів, шляхів і контурів.

54 Цикломатика графів. Цикломатичне число та його властивості.

Цикломатична матриця. Базис циклів. Алгоритм побудови базису циклів.

55.Задача комівояжера. Приклади практичних задач, що зводяться до задачі комівояжера.

56.Дерева. Визначення дерева, властивості дерев, ліс.

57.Перелічення графів і дерев. Остови графа.

58.Орієнтовані і бінарні дерева. Правила обходу бінарних дерев.

Еквівалентні бінарні дерева.

59.Розфарбування графів. Фарбування вершин та ребер. Хроматичне число, теорема про біхроматичний граф. Хроматичний клас. Теорема Брукса.

60.Гіпотеза чотирьох фарб. Теорема про п'ять фарб. Прикладні задачі, що зв’язані з розфарбуванням графів

61.Двудольні та k-дольні графи.

62.Найкоротші відстані та шляхи у мережах. Алгоритм визначення відстані між вершинами на графі з одиничними довжинами ребер. Алгоритм Дейкстри (Форда) визначення відстані між вершинами на графі з довільними довжинами ребер.

63.Алгоритми Флойда і Данцига пошуку найкоротших шляхів між всіма парами вершин графа.

64.Течії у мережах. Задача про максимальну течію у мережі. Розріз мережі. Теорема про максимальну течію і мінімальний розріз. Алгоритм Форда-

Фалкерсона.

65.Елементи теорії формальних граматик. Задачі формалізації мов та перекладу. Задання мов за допомогою граматик. Типи граматик.

66.Елементи теорії скінчених автоматів. Загальна характеристика автоматів. Розпізнавачі.

67.Скінченні автомати. Способи задання автоматів. Автомати Мили і Мура. Автомати з магазинною пам’яттю. Машина Тьюринга.

Типові практичні завдання

1. Нехай множина перших 20 натуральних чисел - це універсум. Запишіть такі його підмножини: А – підмножина парних чисел; В – підмножина непарних чисел; С – підмножина квадратів чисел; D – підмножина простих чисел.

6

2. Чи рівні між собою множини А та В (якщо ні, то чому?): а) A={2,5,4},

B={5,4,2}; б) A={1,2,4,2}, B={1,2,4}; в) A={2,4,5}, B={2,4,3}; г) A={1, {2,5},6}, B={1,{5,2},6}; д) A={1,{2,5},6}, B={1,2,5,6}?

3.

Нехай A a,b,c, f ,g,d , B b,c,g,k,l . Знайти A B, A\ B,

A B.

4.

Нехай N - множина натуральних чисел, N0 - множина натуральних

чисел та 0. Знайти N N0 , N N0 , N \ N0 , N0 \ N , N0 N .

 

5.

Які з наведених нижче співвідношень невірні и чому?

 

а) x 2,a,x ; б) 3 1, 2,3 ,4 ; в) x 1,sinx ; г) x, y a, x, y ,b .

6.В яких відношеннях знаходяться між собою такі три множини: А={1,3}; B – множина непарних додатних чисел; С - множина рішень рівняння

x2 4x 3 0?

7.Нехай A a,b,c , B a,d . Знайти A B, | A B|.

8.

Используя диаграммы Венна, покажите равенства двух множеств

(

 

)

 

 

 

 

.

A B

A

B

9. Для каждого из приведенных ниже множеств используйте диаграммы Венна для двух множеств и заштрихуйте те её части, которые изображают

заданные множества: а) A B; б)

(A B) A B; в) (A B C).

 

10.

Визначити

та

навести

зображення

множин

A B; A B; A \ B; B \ A,

 

якщо

множини

задані

як

A (x,y) R2 : x y

 

 

 

 

 

 

B (x,y) R2 : |x| | y| 1 .

 

 

 

 

 

 

11.Дати оцінку справедливості рівняння. Відповідь підтвердити діаграмами Ейлера: ( A\ B) C ( A C )\ B.

12.Спростити вираз ( A B) (C B) ( A D) (C D).

13.Нехай X ={2,3} и Y ={3,4,5,6}. Визначити декартов добуток X Y , відношення R «бути дільником», відношення «рівність» (=), відношення ,

області визначення і значення відношення R.

14. Нехай X x1,x2,x3,x4,x5 ; Y y1,y2,y3,y4 і

R {(x1,y1),(x1,y3),(x2,y1),(x2,y3),(x2,y4),(x3,y1),(x3,y2),(x3,y4),(x4,y3), (x5,y2),(x5,y4)}.

Знайти переріз відношення R за елементами xi X .

Знайти переріз R(B) відношення R за підмножиною B {x2,x3}. 15. Нехай є два відношення

7

A {(x1,y1),(x1,y3),(x2,y1),(x2,y3),(x2,y4),(x3,y1),(x3,y2),(x3,y4),(x4,y3), (x5,y2),(x5,y4)} і B {(y1,z2),(y2,z1),(y2,z2),(y3,z3),(y4,z3)}.

Знайти композицію C B A, переріз C(x3).

 

16. Нехай A 1,2,3,4,5,6 і нехай відношення

R A A є множина

R {(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,2),(1,4),(2,1),(2,4),(3,5),(5,3),(4,1),(4,2)}

Показати, що відношення R є відношенням еквівалентності.

17. Нехай A { , , , } і нехай R A A визначено у вигляді

R {( , ),( , ),( , ),( , ),( , ),( , ),( , ),( , )}.

Чи

є

відношення R відношенням еквівалентності?

18.Для відношення еквівалентності, яке задається класами

еквівалентності

X1 {x1,x2,x4};

X2 {x3,x8};

X3 {x5,x6,x7,x9},

знайти

матрицю еквівалентності.

 

 

 

19.

Для відношення нестрогого порядку

A «бути дільником» на

множині X {1,2,3,4} Y {1,2,3,4,6,7,12,14,21,28} знайти матрицю відношень.

20.

Знайти

матрицю відношення строгого

порядку « »на

множині

X{1,2,3,4,5}.

21.Визначте, які властивості мають відношення, що задаються на деякій множині людей. Нехай (a,b) R, якщо:

а) a вище зростом, ніж b;

б) a і b народилися в один день; в) a є родичем b;

г) a знайомий з b.

22. В множині N {1,2,3,4,5} задані відношення:

а) {(1,2),(2,3),(2,4),(3,2),(5,1)}; б) {(2,1),(3,4),(4,4),(5,3)};

в) {(1,2),(2,3),(3,2),(4,3),(5,1)}; г) {(1,2),(2,3),(4,1),(4,5),(5,5)};

д) {(1,5),(2,1),(3,4),(4,3),(5,2)}.

Які з цих відношень є функціями, а які – відображеннями?

23. Які з наведених відношень в множині дійсних чисел R є функціями?

а) {(x,y) R R| y x2 2x 1};

б) {(x,y) R R| x y2 };

в) {(x,y) R R| | x| | y| 1};

г) {(x,y) R R| x2 y2 1 и y 0}.

8

24. Нехай A { , , }, B { , , ,}. Визначити, чи є наведені відношення

між елементами A і B всюди визначеними, сюр’єктивними, функціональними,

ін’єктивними, взаємно однозначним:

а) G1 {( , ),( , ),( , )};

б) G2 {( , ),( , ),( , )};

в) G3 {( , ),( , ),( , )}.

25.Скільки способів існує для того, щоб вибрати три різних фарби з

п’яти?

26.Скількома способами можна скласти трикольоровий смугастий стяг, як що є п’ять матеріалів різних кольорів?

27.Скільки словників треба видати, щоб можна було виконати безпосередній переклад з п’яти мов (російської, української, англійської,

французької, німецької) на любу з п’яти мов.

28. У одного студента є 7 книг з математики, а у другого студента – 9

книг. Скількома способами вони можуть обміняти книгу одного на книгу другого?

29.Наукове товариство складається з 25 чоловік. Треба вибрати президента, вченого секретаря, скарбника. Скількома способами це можна зробити, якщо кожний член товариства посідає тільки один пост?

30.На диск секретного замка нанесено 12 літер. Секретне слово складається з 5 літер. Скільки невдалих спроб може бути зроблено людиною, яка не знає секретного слова?

31.В цеху є 9 вільних робочих місць, 2 з яких можуть посідати тільки жінки, 3 – тільки чоловіки, а 4 чоловіки та жінки. Скількома способами можна розподілити 3-х жінок та 4-х чоловіків по робочих місцях?

32.Скількома способами можна впорядкувати множину 1,2,3,...,n так,

щоб числа 1, 2, 3 стояли поруч і в порядку зростання?

33.На зборах мають виступати 4 особи А, В, С, Д. Скількома способами їх можна розташувати в списку ораторів, якщо В не може виступати до того часу, поки не виступить А?

34.Скількома способами можна розсадити дев’ять пасажирів у три вагони щоб: а) у кожний вагон сіло три пасажири; б) у пронумеровані вагони: у

перший – чотири пасажири; у другий – три і в третій – два?

35.У ліфт семиповерхового будинку ввійшли три чоловіки. Скільки існує способів вийти: а) усім на однім поверсі; б) одночасно на будь-якому поверсі; в) усім на різних поверхах; с) усіляких комбінацій?

9

36. При x1 1;

x2 0;

x3 0;

x4 0 знайти значення функцій: 1)

x1 x2 ~ x2x3; 2) x1x2 x2 ~ x3 .

Скласти таблицю відповідності для формули x1 x2 x2 x3 .

37. Визначити, чи є наступні формули загальнозначущими, суперечливими та несуперечливими:

а) (A B) ( A B);

б) ( A) A;

в) (A B) (B A).

38. Скласти таблицю відповідності для формул F x1 x2 x3 x1 x3 і

Fx1 x2 ~ x1x2 x3 .

39.Перевірить за допомогою таблиць відповідності такі тотожності:

а) x y=x y; б) x x y x.

40.Знайдіть ДДНФ формули F x1 x2 x3 x1 x3 .

41.За допомогою еквівалентних перетворювань привести до ДНФ такі

формули: а) F x1 x2 x3 x1 x3 ; б) F x1 x2 x1x2 x3 .

42.За допомогою співвідношень виду x yz x y x z перетворити ДНФ D ~x3 x1 x2 x3 у КНФ.

43.Перевірить за допомогою таблиць відповідності такі тотожності:

а) x y=x y; б) x x y x; в) x xy=x y.

44.Визначити, які з даних речень є висловлюваннями: «Волга уливається

вЧорне море», «Волга уливається в Каспійське море», «Який сьогодні день?», «Відстань від Землі до Сонця дорівнює 150000000 км».

45.Записати в символічній формі такі висловлювання:

а) У мене не сучасний комп’ютер або я закінчу проект вчасно.

б) Невірно, що я закінчу проект вчасно та складу іспит.

в) У мене не сучасний комп’ютер або я не закінчу проект вчасно та складу іспит.

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

а) «Для того що би 2 2 4, необхідно і достатньо, що би 2 2 4»;

б) «2 2 5 рівносильно тому, що 3 3 8».

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

а) «6 ділиться на 3, і 10 більше ніж 5»;

10

Соседние файлы в предмете Дискретная математика