Навчальний посібник для студентів математичних факультетів педагогічних університетів, 224 сторінки. Передмова. Цей навчальний посібник створено на основі спецкурсу «Вступ до дискретної математики», який один із авторів викладав протягом кількох років для магістрантів математичного факультету МПГУ імені В.І.Леніна. Поява такого курсу була зумовлена сучасною потребою — у часи стрімкого розвитку дискретної математики випускник педагогічного університету часто не володіє її базовими поняттями. Зі стандартними курсами з інформатики та обчислювальної техніки ситуація не змінюється, оскільки вони більше зосереджені на технічних аспектах, ніж на фундаментальних концепціях. Звісно, під час відбору матеріалу автори стикнулися з чималими труднощами. На їхню думку, існуючі університетські курси з дискретної математики не підходять для майбутніх учителів. «Неможливо охопити необмежене!» — саме цим принципом керувалися автори при формуванні програми. Посібник складається з чотирьох розділів. Перший розділ присвячено булевим функціям і функціям k-значної логіки. Відомо, що вони є основою моделювання цифрових керуючих пристроїв, і розділ дискретної математики, що їх описує, давно став класикою. При написанні цієї частини автори переважно керувалися підручником С.В.Яблонського «Вступ до дискретної математики». Другий розділ — елементи комбинаторики. Тут автори з широкого кола питань зупинилися на теорії породжувальних функцій і рекурентних співвідношеннях. Такий вибір обґрунтований тим, що випускник математичного факультету педагогічного інституту вже володіє базовими поняттями теорії степеневих рядів і елементарної комбинаторики, тому ці теми логічно продовжують раніше вивчений матеріал. Крім того, вони є найопрацьованішими та мають широкі застосування. Третій розділ присвячено теорії графів. Тут не потрібно особливих пояснень — ця галузь є зручним інструментом для формулювання задач найрізноманітнішого характеру, від електротехніки до соціології й різних математичних головоломок, а також сприяє розвитку формального мислення. Четвертий розділ розглядає алгоритми на графах. Мета авторів — з одного боку, ознайомити з основними ідеями, закладеними у добре відомі комбинаторні алгоритми, для чого графи є зручним мовним засобом, а з іншого — дати уявлення про складність алгоритмів. Виникнення теорії складності вважається одним із головних здобутків розвитку дискретної математики та інформатики після створення дескриптивної теорії алгоритмів і обчислювальних машин. На жаль, наразі питання теорії складності часто виключені з обов’язкової програми педагогічних вузів (частково через те, що її поняття ще не сформувалися у цілісну систему). Проте ці питання дуже важливі для засвоєння понять ефективних алгоритмів і методів їх побудови. Ідея, що покращення характеристик обчислювальних машин (швидкодії, обсягу пам’яті) є універсальним рішенням усіх проблем, є помилковою. Значно ефективніше — підвищувати самі алгоритми. Водночас слід усвідомлювати, що існує великий клас задач (насамперед, так звані NP-складні), для яких створення ефективних алгоритмів залишається дуже складним. У книзі — 4 розділи (тематики): **Зміст:** - Конечні функції. - Булеві функції: основні способи їх подання, формули, реалізація формулами, принцип дуальності, розкладання по змінних, поліном Жегалкина, повнота та замкнутість. - Функції k-значної логіки. - Ітеративні алгебри Поста. - Елементи комбинаторики: породжувальні функції та їх застосування, теорія формальних степеневих рядів, основний принцип теорії породжувальних функцій, прості породжувальні функції, числові характеристики основних комбинаторних об’єктів. - Рекурентні співвідношення: основні поняття, лінійні рекурентні рівняння з постійними та змінними коефіцієнтами, числа Каталана, числа Стірлінга другого роду. - Конечні графи: основні поняття, зв’язні графи, обходи графа, дерева, планарні графи та їх розмальовки. - Алгоритми на графах: поняття складності алгоритму, задачі покриття, жадібний алгоритм, задача про мінімальне остовне дерево та її узагальнення, теорема Радо-Едмондса, задача про найкоротший шлях, метод динамічного програмування, задача про максимальний потік, деякі застосування задачі про максимальний потік, пошук максимального паросочення у двочастковому графі. - Системи різних представлень. - Організація руху у динамічних мережах. - Оптимальний підбір інтенсивностей виконання робіт. - Труднощі при розв’язанні задач. **Список літератури.**