Дискретна математика

Спеціальність: Комп'ютерні науки
Код дисципліни: 6.122.00.O.007
Кількість кредитів: 5.00
Кафедра: Інформаційні системи та мережі
Лектор: к.т.н., доцент Висоцька Вікторія Анатоліївна
Семестр: 1 семестр
Форма навчання: денна
Результати навчання: • основи математичної логіки і теорії множин, • елементи комбінаторного аналізу, • основи теорії відношень, • основи теорії графів та дерев, • основи теорії кодування, • булеві функції, • мови, граматики та автомати, • основи теорії алгоритмів, • основи теорії кодування.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: • Алгоритмізація та програмування, Чисельні методи, Теорія прийняття рішень, Об’єктно-орієнтоване програмування, Організація баз даних та знань, Інтелектуальний аналіз даних, Методи та системи штучного інтелекту.
Короткий зміст навчальної програми: Логіка та методи доведення. Множини та відношення. Елементи комбінаторного аналізу. Графи. Дерева. Булеві функції. Мови, граматики та автомати. Основи теорії алгоритмів. Основи теорії кодування. Комбінаторні задачі та складність обчислень.
Методи та критерії оцінювання: • Поточний контроль (45%): письмові звіти з лабораторних робіт, усне опитування • Підсумковий контроль (55%, екзаменаційний контроль): тестування (45%), усна компонента (10%)
Рекомендована література: • Нікольський Ю.В. Дискретна математика / Ю.В. Нікольський, В.В. Пасічник, Ю.М. Щербина. – Львів.: Видавництво "Магнолія-2006", 2011. – 432 с. • Емеличев В.А. Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. – М., Наука. – 1990. • Капітонова Ю.В. Основи дискретної математики / Ю.В. Капітонова, С.Л. Кривий, О.А. Летичевський, Г.М. Луцький, М.К. Печурін. – К.: Наукова думка, 2002. – 580 с. • Кузнецов О.П. Дискретная математика для інженера / О.П.Кузнецов, Г.М.Адельсон-Вельский. – М.: Энергоатомиздат. – 1988. • Липский В. Комбинаторика для программистов / В.Липский. – М.: Мир. – 1988. • Яблонский С.В. Введение в дискретную математику: 2-е изд. / С.В.Яблонский. – М., Наука. – 1986. • Гаврилов Г.П. Сборник задач по дискретной математике / Г.П. Гаврилов, А.А. Сапоженко. – М.: Наука. – 1977.

Дискретна математика

Спеціальність: Комп'ютерні науки
Код дисципліни: 6.122.00.O.006
Кількість кредитів: 5.00
Кафедра: Автоматизовані системи управління
Лектор: к.т.н., доц. Зербіно Дмитро Дмитрович
Семестр: 1 семестр
Форма навчання: денна
Результати навчання: - Засвоїти основи логічного мислення та теорії формальних систем; - Знати принципи розв’язку довільних задач за допомогою комп’ютера; - Вміти розкласти складну задачу на елементарні обчислювальні моделі; - Вміти проаналізувати задачу засобами формального логічного мислення, та виявити суперечки, надлишковість та повноту.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: - пререквізит: Загальний курс математики для шкіл
Короткий зміст навчальної програми: Теорія множин. Квантори. Решітки. Основні поняття комбінаторного числення. Дискретні функції. Кодові послідовності. Відображення. Ізоморфізм. Дискретні алгебри. Несуперечливі системи. Теорія логічного висновку. Логічна інтерпретація. Теорія предикатів. Силогізми. Максимально сумісні і мінімально несумісні підмножини. Поняття суперечки, повноти, надлишковості, двоїстості. Нормальні форми. Слабо визначені дискретні функції. Модальна логіка. Відношення та властивості. Двійкове та негабінарне кодування. Теорія графів. Логіка і графи. Граматики і графи. Використання графів. Групи. Утворюючі елементи. Перестановки. Числові кільця. Неповторні коди. Функції Уолша. Дискретні автомати. Клітинні автомати.
Методи та критерії оцінювання: - Поточний контроль (70%): електронні звіти працюючих програм по виконаних завданнях з лабораторних робіт, виконана розрахункова робота, позитивні результати поточного комп’ютерного тестування - Підсумковий контроль (30 %): екзамен.
Рекомендована література: - Ralph P.Grimaldi. Discrete and Combinatorial Mathematics. Boston/San Francisco/New York. – Addison Wesley, 2004. - Капітонова Ю.В., Кривий С.Л., Летичевський О.А. Основи дискретної математики. Підручник. – К.: Наукова думка, 2002.– 580 с. - Навчальні матеріали Львівської політехніки (Методички).
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою: вул. Карпінського, 2/4, І-й н.к., кімн. 112 E-mail: nolimits@lpnu.ua Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).

Дискретна математика

Спеціальність: Комп'ютерні науки
Код дисципліни: 6.122.00.O.008
Кількість кредитів: 5.00
Кафедра: Системи штучного інтелекту
Лектор: Мельникова Н.І.
Семестр: 1 семестр
Форма навчання: денна
Результати навчання: знати: - основні поняття, закони та теореми логіки висловлювань, теорії множин, комбінаторного аналізу та теорії графів; - методи перевірки логічних функцій на тавтологію, протиріччя, еквівалентність; - методи розв’язування комбінаторних задач на сполучення, розміщення та перестановки з повтореннями і без; - методи розв’язування комбінаторних задач з використанням принципу Діріхле та принципу включення-виключення; - методи розв’язування лінійних рекурентних рівнянь зі сталими коефіцієнтами; - основні поняття про твірні функції; - види графів та способи їх задання; - методи перевірки графів на ізоморфізм, зв'язність, дводольність, планарність, гомеоморфність, існування Ейлерових та Гамільтонових циклів; - основні властивості дерев; вміти: - знаходити таблиці і значення істинності заданих логічних функцій; - перевіряти логічні функції на відповідність заданим таблицям істинності; - спрощувати логічні функції за допомогою еквівалентних перетворень; - зводити логічні функції до нормальних форм; - обраховувати декартів добуток множин, будувати діаграми Ейлера, працювати з бітовими рядками; - розв’язувати комбінаторні задачі на сполучення, розміщення та перестановки з повтореннями і без; - розв’язувати комбінаторні задачі з використанням принципу Діріхле та принципу включення-виключення; - розв’язувати лінійні рекурентні рівняння зі сталими коефіцієнтами; - генерувати у лексикографічному порядку перестановки, сполучення, розміщення; - використовувати твірні функції при розв’язуванні комбінаторних задач та рекурентних рівнянь; - задавати графи на комп’ютері; - розв’язувати задачу пошуку найкоротшого шляху, розфарбовування графа, обходу графа, перевірки графа на - відповідність заданим критеріям; - розв’язувати задачу обходу дерева; - будувати бінарне дерево пошуку та дерево прийняття рішень; - розв’язувати задачі з використанням бектрекінгу; - використовувати статистичні методи при обробці емпіричних результатів; - виконувати основні математичні операції та уміння застосовувати їх для практичних задач.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Алгоритмізація та програмування, ч1 Математичний аналіз
Короткий зміст навчальної програми: Логіка та методи доведення Множини та відношення Графи Дерева Булеві функції
Методи та критерії оцінювання: лабораторні роботи - 30 практичні роботи - 5 розрахункова робота - 10 письмова компонента - 45 усна компонента – 10
Рекомендована література: Нікольський Ю.В. Дискретна математика. Ю.В.Нікольський, В.В.Пасічник, Ю.М. Щербина. Львів, Магнолія Плюс, 2005, 2006 (1-е видання), 2007 (2-е видання, виправлене й доповнене), 2008 (3-є видання, виправлене й доповнене). Журавчак Л.М. Практикум з комп’ютерної дискретної математики: навч. посібник / Л.М. Журавчак, Н.І. Мельникова, П. В. Сердюк. – Львів : Видавництво Львівської політехніки, 2019. – 279 с Журавчак Л. М. Дискретна математика для програмістів. Навчальний посібник. Львів : Видавництво Львівської політехніки, 2019. 420 с. Rosen, Kenneth H. Discrete mathematics and its applications / Kenneth H. Rosen. — 7th ed. p. cm. Includes index. ISBN 0–07–338309–0 1. Mathematics. 2. Computer science—Mathematics. I. Title. QA39.3.R67 2012 511–dc22 Капітонова Ю.В. Основи дискретної математики. Ю.В. Капітонова, С.Л. Кривий, О.А. Летичевський, М.К. Печурін. К., Наукова думка, 2002.