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

kontrolnye / Дискретка / МВ до СРС дискретна математика

.doc
Скачиваний:
38
Добавлен:
27.02.2016
Размер:
69.12 Кб
Скачать

Міністерство освіти і науки України

Сумський державний університет

КОНОТОПСЬКИЙ ІНСТИТУТ

МЕТОДИЧНІ ВКАЗІВКИ

до організації самостійної роботи студентів

з дисципліни "Дискретна математика"

для студентів спеціальності

«Електронні прилади та пристрої»

заочної форми навчання

2010

Методичні вказівки до організації самостійної роботи студентів з дисципліни "Дискретна математика" для студентів спеціальності «Електронні прилади та пристрої» заочної форми навчання / Укладач Матвієнко М.П.

Кафедра математики і інформатики КІ СумДУ

Вступ

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

Література основна: [1].

Питання для самоконтролю.

  1. Що вивчає дискретна математика?

  2. З яких розділів складається дискретна математика?

  3. На яких теоретичних розділах знань базується вивчення дискретної математики?

  4. В яких галузях промисловості може застосовуватись дискретна математика?

Тема 1 Арифметичні основи операційних автоматів

Системи числення. Позиційні та непозиційні. Алфавіт, основа, діапазон. Машинно-орієнтовані системи числення. Двійкові, двійково-десяткові, вісімкові, шістнадцяткові. Методи переводу цілих і дробових чисел з однієї системи числення в іншу. Арифметичні операції у двійковій системі числення – додавання, віднімання, множення і ділення. Представлення додатних і від’ємних чисел у прямому коді.

Література основна: [1], част. 4.

Література додаткова: [11]

Питання для самоконтролю.

  1. Які існують системи числення?

  2. Чим відрізняється позиційна система числення від непозиційної?

  3. Що таке алфавіт? основа? діапазон?

  4. Які існують машинно-орієнтовані системи числення?

  5. Як записуються числа у двійковій, двійково-десятковій, вісімковій, шістнадцятковій системах?

  6. Які існують методи переводу цілих і дробових чисел з однієї системи числення в іншу?

  7. Правила виконання арифметичних операцій у двійковій системі числення?

  8. Як представляються додатні і від’ємні числа у прямому коді?

Тема 2.1 Теорія множин

Множини. Способи їх завдання. Підмножини. Відношення включення та його властивості. Булеві операції над множинами. Основні закони алгебри множин. Перетин множин. Декартовий добуток множин. Нечіткі множини. Реалізація множин в ЕОМ.

Література основна: [1], [2], [3],

Література додаткова: [9].

Питання для самоконтролю.

  1. Що таке множина?

  2. Які бувають множини?

  3. Поняття належності – неналежності множин.

  4. Як можна задати множини?

  5. Що таке підмножина завданої множини?

  6. Що таке декартовий добуток двох множин?

  7. Які є булеві операції над множинами?

  8. Скільки є основних законів алгебри множин?

  9. Що називається властивістю операції включення?

  10. Що таке потужність множини?

Тема 2.2 Теорія відношень

Основні поняття теорії відношень. Бінарні відношення та способи їх задання. Функціональні відношення та способи їх задання. Операції над відношеннями. Композиція відношень. Обернене відношення. Ядро. Властивості відношень. Відношення еквівалентності. Відношення порядку. Відношення рівнопотужності. Реалізація відношень в ЕОМ.

Література основна: [1], [3], [5],

Література додаткова: [9].

Питання для самоконтролю.

  1. Що таке відношення?

  2. Які є способи завдання бінарних відношень?

  3. Що таке бінарне відношення?

  4. Які бувають відношення?

  5. Що таке композиція відношень?

  6. Що таке обернене відношення?

  7. Що таке ядро?

  8. Які є властивості відношень?

  9. Що таке відношення порядку?

  10. Що таке відношення еквівалентності?

  11. Що таке відношення рівнопотужності?

Тема 3-4 Математична логіка

Логічні функції та їх властивості. Розкладання функції по змінним. Принцип двоїстості булевих функцій. Функціонально-повні системи. Метод Квайна. Метод Мак-Класкі. Методи доведення у логіці Буля. Диз’юнктивні і кон’юнктивні нормальні форми.

Література основна: [1], [2],

Література додаткова: [9].

Питання для самоконтролю.

  1. Що таке логічна функція?

  2. Що таке принцип двоїстості булевих функцій?

  3. Які є властивості логічних функцій?

  4. По якій кількості змінних можна розкласти логічну функцію?

  5. Яка сутність методу Квайна? методу Мак-Класкі? методу Вейча? методу Карно?

  6. Що є спільним і яка різниця між цими методами?

  7. Які є методи доведення рівнянь у логіці Буля?

  8. Що таке ДДНФ, як вона відрізняється від ДНФ?

  9. Що таке ДКНФ, як вона відрізняється від КНФ?

Тема 5.1 Автомати, способи їх задання. Математичне перетворення автоматів

Автомати Мілі, Мура. Часткові автомати. С-автомати та їх побудова. Алгоритм переходу від автомату Мілі до автомату Мура і навпаки. Закони функціонування автоматів. Умови автоматності. Теореми детермінізації.

Література основна: [7], [8],

Література додаткова: [10], [11].

Питання для самоконтролю

  1. Що таке кінцевий автомат?

  2. Які бувають автомати?

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

  4. Що таке автомат Мілі? автомат Мура? С-автомат?

  5. Яка умова переходу від автомату Мілі до автомату Мура?

  6. Яка умова переходу від автомату Мура до автомату Мілі?

  7. Що таке частковий автомат?

  8. Що таке події в автоматах?

  9. Які є умови автоматності?

Тема 5.2 Ізоморфізм і еквівалентність автоматів

Ізоморфізм і еквівалентність автоматів. К-еквівалентність автоматів. Розпізнання автоматів. Основні умови визначення, умови еквівалентності, знаходження еквівалентних автоматів. Сильнозв'язані автомати. Розпізнавання сильнозв'язаних автоматів.

Література основна: [7], [8],

Література додаткова: [10], [11].

Питання для самоконтролю

  1. Що таке еквівалентність автоматів?

  2. Що таке К-еквівалентність автоматів?

  3. Що таке ізоморфізм автоматів?

  4. Як відбувається розпізнавання автоматів?

  5. Які бувають автомати?

  6. Що таке сильнозв'язні автомати?

  7. Що таке розпізнавання автоматів, в тому числі і сильнозв'язних?

  8. Який є алгоритм знаходження еквівалентних автоматів?

  9. Записати кроки дії алгоритму Мілі по знаходженню еквівалентного автомату.

Тема 5.3 Представлення подій в автоматах.

Алгебра регулярних подій, їх джерела

Регулярні події. Алгебра регулярних подій. Закони еквівалентного перетворювання регулярних виразів. Джерела. Операції над джерелами. Детермінізація джерел. Теорема детермінізації джерел. Побудова графів регулярних виразів. Алгоритм синтезу автоматів по графам регулярних виразів. Система правил, що визначають типи регулярних виразів, графи яких повинні мати пусті стрілки.

Література основна: [7], [8],

Література додаткова: [10], [11].

Питання для самоконтролю

  1. Що таке регулярні події?

  2. Що таке джерело?

  3. З чого складається алгебра регулярних подій?

  4. Які є алфавіти подій?

  5. Які бувають операції над джерелами?

  6. В чому виражається теорема детермінізації для джерел?

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

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

  9. Які є закони еквівалентного перетворювання регулярних виразів?

Тема 5.4 Комбінаційні, паралельні і послідовні автомати

Комбінаційні автомати. Властивості автоматів з кінцевою пам’яттю. Паралельні і послідовні автомати. Знаходження мінімальних форм комбінаційних і паралельних автоматів..

Література основна: [5], [7], [8],

Література додаткова: [9], [10], [11].

Питання для самоконтролю

  1. Що таке комбінаційний автомат?

  2. Які є властивості комбінаційних автоматів?

  3. Що таке паралельний автомат?

  4. Що таке послідовний автомат?

  5. Яка різниця між цими автоматами?

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

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

  8. Що таке кодування автомату?

  9. Де можуть застосовуватись паралельні і послідовні автомати?

Список рекомендованої літератури

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

  1. Борисенко О.А. Дискретна математика. Підручник – Суми: Університетська книга. 2008. – 255 с.

  2. Борисенко О.А. Лекції з дискретної математики (множник і логіка). Навчальний посібник. – Суми. Видавництво СумДУ, 1999. – 111 с.

  3. Бардаков Ю. Дискретна математика. – К., 2002.

  4. Бондаренко М. Комп’ютерна дискретна математика. – Харків, 2004. – 480 с.

  5. Горбатов В.А. Основы дискретной математики. Учебное пособие для студентов вузов. М.:ВШ, 1986. – 311 с.

  6. Яблонский Введение в теорию графов. – М.: Мир, 1997. – 208 с.

  7. Гилл А. Введение в теорию конечных автоматов. – М.: Наука, 1996. – 371 с.

  8. Баранов С.И. Синтез микропрограммных автоматов. – Л.: Энергия, 1979. – 231 с.

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

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

  2. Савельев А.Я. Прикладная теория цифровых автоматов. Учеб. для вузов по спец. ЭВМ. – М.: ВШ, 1987. – 375 с.

  3. Лапа В.Г. Математические основы кибернетики. – К.: ВШ, 1971. – 418 с.