рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Основна

Основна - Конспект, раздел Математика, ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ 1. Мелихов А.н. Ориентированные Графы И Конечные Автоматы. – М.: Наука, 1971....

1. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.40-59, 64-70.

2. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.199-201.

3. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. - С.19-22.

Додаткова

4. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. - С.68-72.

5. Горбатов В.А. Основы дискретной математики. – М.: Высш.шк., 1986. - С.89-94.

Для практичних занять

6. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2001. – С.45-47.

7. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1973. - С.101-111.


Лекція 17. Характеристики графів. Представлення в ЕОМ

– Конец работы –

Эта тема принадлежит разделу:

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

О М Мартинюк... ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ КОНСПЕКТ ЛЕКЦІЙ для студентів очної та заочної... Затверджено на засіданні вченої ради ОНПУ протокол від...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Основна

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Дистрибутивність
4. AÈÆ=A; AÈU=U;AÇÆ=Æ; AÇU=A;`Æ=U; `U=Æ; властивості границь 5.

М1-M2-¼-Mn=-{Mі|1 £ і £ n }={m| існує і єдино і, де 1£і£n, таке, що mÎMі}.
Ці визначення узагальнюються на випадок, коли множини Мі задані як елементи деякої сім'ї множин М и потрібно виконання деякої додаткової умови В: È{Mі|Mі

Контрольні запитання
1. Що є множина, фактор-множина, порожня множина і універсум? 2. Які способи завдання множин існують? 3. Які операції діють над множинами? 4. Як м

Основна
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.- С.19-26. 2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатом-издат, 1987. - С.24-44.

Основна
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.23, 24. 2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987. - С.28-34.

Основна
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.33, 38. 2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987. - С.44-51.

Основна
1. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987. - С.48-62. 2. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.33-41.

Основна
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.33-38. 2. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990. с.35-46. 3. Глушков В.М., Ц

Контрольні запитання
1. Що є перестановкою для n-арних відношень і які окремі випадки перестановок існують? 2. Які властивості мають обернення n-арного відношення? 3. Як виконується о

Основна
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.33-38. 2. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990. - С.43-46. 3. Глушков В.М.,

Лема. Суперпозиція скрізь визначених функціональних відношень також є скрізь визначеним функціональним відношенням.
Нехай j - бінарне відношення на множинах А, В. Визначення. Відношення j називається відображенням множини А у В, якщо - функціонально й скрізь визначено, тобто для будь-якого а&Icir

Лема. Відображення j множини А на множину В – взаємно однозначне (бієктивне), якщо воно також ін’єктивне.
Зокрема, взаємно однозначним відображенням А на А є діагональне відношення dА, що часто називають тотожним відображенням А в себе. Теорема. Відображення j множини А на множину В

Контрольні запитання
1. Що є проекцією, перерізом, об’єднанням і фактор-множиною для n-арних відношень? 2. Які n-арні відношення є функціональними, ін’єктивними? 3. Які n-арні відноше

Основна
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.35-38. 2. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990. - с.43-46. 3. Глушков В.М.,

Контрольні запитання
1. Які властивості має відношення еквівалентності? 2. Якій зв’язок між розбивками і відношенням еквівалентності? 3. Що є фактор-множиною А/rА, і суміжн

Основна
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.42-47. 2. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990. - С.46-64. 3. Глушков В.М.,

Підстановки
Визначення. Підстановкою множини А називається біекція на А (біективна відповідність на А). Число різних підстановок для скінченних множин можна легко обчислити. Нехай ½A&f

Функціонали
Нехай е множини А, В, С і [В®С] - множина функцій з В у С. Визначення. Функція f:A®[B®C] називається функціоналом, тобто для будь-якого аÎA f(a) - функція - f(a):B®C, для будь

Функції, що зберігають алгебраїчні властивості
Існують функції, що зберігають алгебраїчні властивості і структури. Визначення. Нехай X і U - множині, а rx і rу – деякі відношення на них і нехай f:X®U - таке

Загальні визначення операцій
Деякі функції використовують при введенні позначень. Визначення. Операцією над множиною S називається функція f: Sn®S, де nÎN і є два важливих моменти операції: а) однозна

Контрольні запитання
1. Як визначають транзитивне і рефлексивне замикання? 2. У чому суть методу Варшалла? 3. Яка підмножина А¢ множини А називається замкнутою щодо відповідності

Основна
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.47-49. 2. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990. - С.64-68. 3. Глушков В.М.,

Внутрішній закон композиції
  10.2.1. Властивості внутрішнього закону Операції на множині S можуть мати деякі загальні властивості, які звичайно виражаються співвідношеннями між елементами з S:

Контрольні запитання
1. Що розуміють під знаком операції, операндами, оперторами й результатом операції? 2. Що називають законом композиції? 3. У чому розходження між зовнішнім й внут

Список літератури
Основна 1. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.137-141. 2. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. - С.6-

Групи підстановок і кільце множин
  11.2.1. Групи підстановок Розгляд деяких систем можна почати із групи підстановок, загального опису яких наводився раніше. Групова операція задається внутрішнім законом ком

Теорема Кели. Усяка кінцева група порядку n може бути представлена групою підстановок n-го ступеня її елементів.
Приклад. Групі третього порядку із груповою операцією, заданою табл. 11.8, відповідає група підстановок {а1 а2, а3}, Таблиця 11.8

Контрольні запитання
1. Що розуміють під групою? Що розуміють під абелевой групою? 2. Що розуміють під кільцем? Які кільця можливі? 3. Що додає до кільця тіло, поле? 4

Список літератури
Основна 1. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975ю - С.141-152. 2. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. - С.6-

Вибірка елементів
Визначення. Вибірка r елементів називається r-перестановкою, якщо враховується порядок проходження, r-сполученням, якщо беруться до уваги тільки елементи без урахування порядку. Приклад. Н

Правило суми і добутку
Найбільше застосовуються при доказах у комбінаториці два правила. Правило суми. Якщо об'єкт a може бути обраний p способами, а об'єкт b - іншими q способами, то вибір “або a, або b” може б

Перестановки
Визначимо число r-перестановок з n різних елементів без повторень. Перестановки. Перший член перестановки можна вибрати з n елементів n способами – елементи не повинні повторюватися, в

Сполучення
Визначимо число r-сполучень з n різних елементів. r-сполучення з n різних елементів: З кожного такого сполучення можна утворити r! перестановок, тому число r-сполучень з n різних елеме

Рекурентні співвідношення
Підрахунок числа перестановок і співвідношень можна визначити за допомогою рекурентних співвідношень, що важливі у комбінаториці. Рекурентні співвідношення. Множину r-перестановок з

Біном Ньютона
Поставимо у відповідність кожному об'єкту з множини {} двочлени вигляду 1+

Контрольні запитання
1. Що є r-перестановкою? 2. Що є r-сполученням? 3. Що таке специфікація та сімейство представників? 4. У чому полягає правило суми і добутку?

Основна
1. Новиков Ф.А. Дискретна математика для программистов. – СПб.: Питер, 2001. - С.135-156. 2. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.169-174. 3. И

Поліноміальні твірні функції
Добуток (1+породжує r-сполучення, в яких кожен елемент із множини об'єктів {

Експонентні твірні функції
Скориставшись залежністю між числами r-сполучень і r-перестановок з різних елементів для сполучень, можна записати

Принцип включення і виключення
Дотепер мова йшла про підрахунок числа підмножин, що утворяться шляхом вибірки об'єктів з деякої множині відповідно до умов, що визначають їхню кількість, упорядкованість і повторюваність. Не менше

Розбивки
Розбивки. Набір цілих позитивних чисел називається розбивкою числа п, якщо п =

Контрольні запитання
1. Що називають поліноміальною твірною функцією? 2. Що є більш загальним – біном Ньютона чи енумератор? 3. Що таке експоненціальна твірна функція?

Основна
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.148-157. 2. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.174-182. 3.

Основні визначення
Графи є зручною формою представлення структур обчислювальних систем і процесів, що у них відбуваються. Визначення. Множина вершин Х, що зв'язані між собою множиною ребер V, називається гра

Способи представлення графів
Перший конструктивний спосіб, як відзначалося, - завдання графу G у вигляді двійки G=<X, Г>. За допомогою цього способу не можна задати мультиграф і псевдограф. Більш складний

Контрольні запитання
1. Як за допомогою двійок визначається граф, чи є таке визначення конструктивним, що дає можливість побудувати граф? 2. Що є неорієнтованим і орієнтованим графами?

Основна
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. - С.9-19. 2. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер,

Зважені (відзначені) графи
Якщо ребрам (дугам) графу приписані деякі ваги (мітки), то такі графи називаються зваженими (відзначеними). Вага дуги чи ребра може означати довжину, пропускну здатність, напругу чи

Контрольні запитання
1. Що є маршрутом, довжиною маршруту? 2. Що є ланцюгом, простим ланцюгом, циклом, простим циклом? 3. Яка різниця між ейлеревим та гамільтоновим циклами?

Основна
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. - С.22-26, 133-148, 191-207. 2. Кук Л., Бейз Г. Компьютерная математика. – М.: На

Операції над графами
Нехай задані два орграфи G =<X, Г>, H = <Y, P>. Визначення. Об'єднанням Q = GÈH називається граф Q = <A, S> такий, що A = XÈY, а S = ГÈР.

Контрольні запитання
1. Що є об'єднанням графів, яка різниця цієї операції зі звичайним множинним об’єднанням? 2. Які властивості має об'єднання? 3. Що є перетинанням графів, яка різн

Ступінь вершин
Для неорієнтованого графу число ребер, що зв'язані з вершиною хі, називається ступенем вершини G(хі), причому петля враховується двічі. Для орієнтованого графу

Цикломатичне число
Нехай G = <X, V>- неорієнтований граф, у якому |X| = n, |V| = m і r – число компонентів зв’язності (тобто зв'язних підграфів графу G). Визначення. Цикломатичним числом графу н

Хроматичне число
Нехай р – деяке натуральне число. Визначення. Граф називається р-хроматичним, якщо його вершини можна розфарбувати “р” різними кольорами так, щоб ніякі дві суміжні вершини не були розфарбо

Множина внутрішньої стійкості
Визначення. Множина SÍX графу G =<X, Г> називається внутрішньостійкою, якщо ніякі дві вершини з S не суміжні, тобто для будь-якого xiÎS має місце Г(xi)&Cced

Множина зовнішньої стійкості
Визначення. Множина TÌX графу G = <X, Г> називається зовнішньо стійкою, якщо будь-яка вершина, що не належить Т, з'єднана ребрами з вершинами з Т, тобто " xi &

Множина зовнішньої стійкості
Визначення. Множина TÌX графу G = <X, Г> називається зовнішньо стійкою, якщо будь-яка вершина, що не належить Т, з'єднана ребрами з вершинами з Т, тобто " xi &

Контрольні запитання
1. Що є ступенем вершини графу, напівступенем заходу і напівступенем виходу вершини орграфу? 2. Як визначається цикломатичне число? 3. Якій граф є p-хроматичним,

Основна
1. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.40-70. 2. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.201-206.

Абстрактний автомат
Поняття абстрактного автомата використовується для опису процесу функціонування дискретних систем. Абстрактний автомат є математичною моделлю функціонування дискретних пристроїв (ДУ).

Табличний спосіб
Автомат Мілі задається таблицями входів і виходів Приклад. Функція переходів автомата Мілі d:S´X®S. Таблиця 18.1 X S

Графічний спосіб
Автомат задається у вигляді орієнтованого графу, вершини якого відповідають станам, а дуги – переходам з одного стану в інший. Дві вершини графу si і sr з'єднуються д

Розширення функцій d і l
Функції d і l розширюються на множину пар вигляду “стан, вхідне слово в алфавіті Х”. Нехай р = <х1,x2,…xr> - вхідне слово довжини “r”. Функцією заключного

Контрольні запитання
1. Що є абстрактним автоматом, у якому часі функціонує автомат? 2. Яка різниця між скрізь визначеним і частковим автоматом? 3. Що є скінченним та нескінченним авт

Основна
18.1. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.154-182. 18.2. Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. - С.33-41, 74

Синхронні й асинхронні автомати
Стан si автомата А називається стійким, якщо зі стану d(sh, xj) = si при будь-яких xj випливає співвідношення d(si, xj

Асинхронні автомати, що тактуються
Визначення. Асинхронні автомати, що тактуються, задовольняють умові: a) вхідний алфавіт Х автомата А розбивається на дві підмножини X’={х'1, х'2,…x’m

Перетворення автомата Мура в автомат Мілі
Побудова автомата Мілі виконується на підставі запізнення реакції автомата Мура у порівнянні з автоматом Мілі. Нехай заданий автомат Мура АA = (SA, XA, Y

Перетворення автомата Мілі в автомат Мура
Нехай заданий автомат Мілі AА = (SА, XА, YА, dА, lА, {s0А}). Еквівалентний йому автомат Мура AВ = (SВ

Сполучена модель автоматів – С-автомат
Визначення. Під абстрактним С-автоматом розуміється математична модель дискретного пристрою, що задається вісімкою вигляду С = (S, X, Y, U, d, l1, l2, {s0

Контрольні запитання
1. Що є стійким станом автомата? 2. Якій автомат Мура є синхронним, а якій асинхронним? 3. Що є стійким виходом автомата Мілі? 4. Якій автомат Міл

Основна
1. Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. - С.33-41, 74-82, 118-132. 2. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.1

Основна
1. Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. - С.33-41, 74-82, 118-132. 2. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.1

Основна
1. Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. - С.33-41, 74-82, 118-132. 2. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.1

Основна
1. Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. - С.33-41, 74-82, 118-132. 2. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.1

Основна
1. Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. - С.33-41, 74-82, 118-132. 2. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.1

Контрольні запитання
1. Яке з’єднання автоматів є рівнобіжним, які ще рівнобіжні з’єднання можна визначити? 2. Що є початковим станом і як визначаються функції переходів та виходів рівнобіжного з’єдн

Основна
1. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.227-305. 2. Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. - С.33-41, 74-82, 1

Мережі автоматів
Мережа автоматів – це математична модель, що описує спільну роботу сукупності n автоматів. Мережа автоматів узагальнює всі можливі способи з'єднання автоматів. Визначення. Мережа автоматів

Еквівалентні автомати мережі
Для мережі з n компонентних автоматів можна побудувати еквівалентний автомат А мережі  

Основна
21.1. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.305-335. 21.2. Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. - С.33-41; 74

Контрольні запитання
1. Що є відмінною рисою логічних функцій? 2. Яка функція є k-значною? 3. Що таке однорідна функція? 4. Що називається булевою функцією?

Основна
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.79-85. 2. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.504-522. 3. Го

Нормальні форми
Визначення. Диз'юнктивна нормальна форма (ДНФ) - це диз'юнкція кінцевого числа різних членів, кожний з яких являє собою кон'юнкцію кінцевого числа окремих змінних чи їхніх заперечень, що входять у

Контрольні запитання
1. Що є табличним способом завдання булевих функцій? 2. Що таке ДНФ і КНФ, СДНФ і СКНФ? 3. Яка різниця між мінтермом і макстермом? 4. Що є “консті

Основна
1. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математика в задачах и примерах. – К.: Учебно-методический кабинет высшего образования, 1992. - С.116

Х1×х2=ù(`х1Ú`х2).
Звідси випливає, що булеві функції виконуються через заперечення і кон’юнкцію чи заперечення і диз'юнкцію. Якщо в булевій формулі змінні зв'язані тільки одним типом операції (диз'юнкції чи

Контрольні запитання
1. Що називається булевою алгеброю, основною множиною та сигнатурою булевої алгебри? 2. Які десять основних тотожностей існують? 3. Які шість теорем розкладення і

Основна
24.1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.81-88. 24.2. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979. - С.10-19. 24

Контрольні запитання
1. Що називається алгеброю Жегалкіна, що є основною множиною та сигнатурою алгебри Жегалкіна? 2. Які вісім основних тотожностей алгебри Жегалкіна існують? 3. Як п

Основна
1. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математика в задачах и примерах. – К.: Учебно-методический кабинет высшего образования, 1992. - С.137

Jn-1=(jn-1×xi)Ú(jn-1×`xi).
На n-вимірному кубі це відповідає заміні двох вершин, що відрізняються значенням одної змінної, ребром, що з'єднує ці вершини. Говорять, що ребро покриває інцидентні йому вершини. Таким чино

Контрольні запитання
1. Як установлюється відповідність n-вимірного куба формулі булевої функції? 2. Що зіставляється конституенті одиниці або нуля у n-вимірному кубі? 3. Що зіставляє

Основна
1. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.550-564. 2. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математ

Ахі)Ú (a`xi)=a
Множині конституент «1» відповідає сукупність 0-кубів К0, операції склеювання відповідає об'єднання двох 0-кубів, що відрізняються тільки однією координатою. Результатом такого об'єднанн

Контрольні запитання
1. Що є комплексом кубів К(у) та як його побудувати? 2. Які змінні називаються зв'язаними, а Які вільними, як позначають у кубі зв'язані та вільні змінні? 3. Чи є

Основна
1. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.550-564. 2. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математ

Контрольні запитання
1. Що змінює модифікація методу Квайна-МакКласкі у методі Квайна? 2. Як у методі Квайна-МакКласкі розбити множини кубів на класи? 3. Що є частково визначеною функ

Основна
1. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.550-564. 2. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математ

Нтервальне представлення в матричній формі
Інтервал у булевому просторі визначається як упорядкована сукупність наборів, задана мінімальним «Мін» і максимальним «Макс» наборами. [«Мін», «Макс»] – безліч наборів К, для яких «Мін»£К&pou

Спрощення ДНФ за матричною формою Закревського
Перший крок побудови максимальних інтервалів для заданого елемента матричної форми заснований на використанні симетрії матриці в коді Грея. Із цією метою виділяються осі симетрії й зони їхньої дії.

Контрольні запитання
1. Що таке послідовний позиційний код і код Грея? 2. Як будується матрична двовимірна форма? 3. Що розуміється під інтервалом? 4. Що називають зов

Список літератури
Основна 1. Закревский А.Д. Логический синтез каскадных схем. – М.: Наука, 1991. – С.100-123. Додаткова 2. Новоселов В.Г., Скатков А.В. Прикладная математика

Формулювання алгоритму побудови максимальних інтервалів для точки
Крок 1. Будується множина Хmпвп для заданої точки. Змінні цієї множини беруть участь у граничному переборі. Точка «m» - це поточний інтервал. Крок 2. Методом гранично

Алгоритм для ДНФ
1. Для кожного елемента mÎM1 розраховується число k сусідніх елементів множини M1ÈMх. 2. Вибирається елемент mÎM1 з меншим зн

Контрольні запитання
1. Які дії припускає перший крок алгоритму побудови максимальних інтервалів для заданої точки? 2. Які дії припускає другий крок алгоритму побудови максимальних інтервалів для зад

Список літератури
Основна 1. Закревский А.Д. Логический синтез каскадных схем, – М.: Наука, 1991. – С.123-130. 2. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.555

Лекція 31. Мінімізація систем булевих функцій
Вступ Лекція має за мету дати базові методи мінімізації систем булевих функцій. Розглянуто основні визначення, зокрема нове поняття ярлика кон’юнкції, показана необхідність спіль

Основні визначення
У більшості додатків використовуються не окремі булеві функції, а системи вигляду f1(x1,x2,…,xn) f2

Використання системи булевих функцій для синтезу КС
Обчислювальна техніка будується на мікросхемах, алгоритми роботи яких описуються булевими функціями. Сукупність застосовуваних при проектуванні конкретного пристрою мікросхем визначає елементний ба

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

Нтуїтивний метод спрощення системи ДНФ за матричною формою
Метод Барті-Полянського громіздкий для ручної мінімізації булевих функцій. Ґрунтуючись на матричному представленні системи булевих функцій і максимальних інтервалів методу Закревського, можна знахо

Контрольні запитання
1. Що називається найкоротшою й мінімальною ДНФ системи булевих функцій? 2. Що позначають ярлики кон'юнкцій булевих функцій? 3. Що називається простою імплікантою

Список літератури
Основна 1. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математика в задачах и примерах. – К.: Учебно-методический кабинет высшего об

Лекція 32. Інтервальні форми та їхні перетворення
Вступ Лекція має за мету дати базові інтервальних форм і їхніх перетворень. Розглянуто системи повністю й неповністю визначених булевих функцій, представлені їхні алфавіти, навед

Нтервальне представлення в ЕОМ
ЕОМ обробляє інформацію в цифровій формі, тому векторне інтервальне представлення систем булевих функцій найбільше природно для проектування дискретних систем. Системи булевих функцій задають списк

Основні операції над інтервальним представленням
Крім склеювання й поглинання, використаних дотепер для наборів векторного інтервального представлення, є ряд операцій, пов'язаних з інтерпретацією інтервалів, як сукупностей елементів булева просто

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

Список літератури
Основна 1. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математика в задачах и примерах. – К.: Учебно-методический кабинет высшего об

Лекція 33. Використання інтервальних операцій
Вступ Лекція має за мету показати можнасті використання операцій при перетвореннях інтервального представлення. Розглянуто перевірку покриття інтервалу об'єднанням інтервалів, ро

Використання операцій інтервального представлення
33.1.1. Покриття інтервалу об'єднанням інтервалів операцієй віднімання Для використання операції «#» здійснюється віднімання з вихідного інтервалу елементів об'єднання інтервалів. Якщо піс

Використання операцій інтервального представлення
33.1.1. Покриття інтервалу об'єднанням інтервалів операцієй віднімання Для використання операції «#» здійснюється віднімання з вихідного інтервалу елементів об'єднання інтервалів. Якщо піс

Контрольні запитання
1. Як виконується перевірка покриття інтервалу об'єднанням інтервалів на основі операції віднімання? 2. У чому посягає процедура розширення інтервалу в заданому об'єднанні інтерв

Лекція 34. Булеві рівняння й нерівності
Вступ Лекція має за мету дати базові методи розв’язання систем булевих рівнянь і нерівностей. Розглянуто основні визначення, зокрема, нове поняття булевих рівняннь й нерівностей,

Булеві рівняння
Визначення. Нехай f(x1, x2, …, xk) і g(x1, x2, …, xk) — дві булеві функції від k змінних, представлені, наприклад, за

Булеві нерівності
Визначення. Нехай f(x1, x2, …, xk) і g(x1, x2, …, xk) — дві булеві функції від k змінних, представлені за допомогою двох булевих

Спільні системи нерівностей і рівнянь
Можна розглянути як самий загальний випадок спільну систему з m булевих нерівностей й n булевих рівнянь: f1(x1, x2, …, xk) £ g1

Контрольні запитання
1. Що називають булевым рівнянням? 2. Яка властивість й як використовується при розв’язанні булевых рівнянь?Як використовується ця властивість? 3. Що є розв’язанн

Лекція 35. Булеві різниця, похідні й диференціали
Вступ Лекція має за мету надати основні поняття булевих різниці, похідних й диференціалів. Розглянуто визначення булевих різниці, приватної й повної похідній, визначення орієнтов

Властивості булевой різниці
Нехай задані вектор значень аргументів X = (х1, x2,..., хi,...,xn) і булева функція y = F(Х) = F(х1, x2,..., хi,...,x

Тотожності булевой різниці
1. d(Х)/dхi = d`F(Х)/dхi 2. d(Х)/dхi = d(Х)/d`хi 3. d(d(Х)/dхj)/dхi = d

Методи знаходження булевой різниці
Раніше для знаходження булевой різниці використалися наслідки, що випливають із визначення поняття булевой різниці. Якщо функція F(Х) складна, потрібні додаткові перетворення. У тому числі можна да

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

Булеві похідні й диференціали
Визначення. Частковою булевою похідною df(x)/dxi функції f(x) від змінних х0, х1, .. ., хi, ..., хп по змінній хi є сума додаван

Контрольні питання
1. Що є булевою різницею? 2. Які властивості має булева різниця? 3. Чім відрізняються карти Карно і Хсиао Скотта для булевої різниці? 4. Що є подв

Список літератури
Основна 1. Селлерс Ф. Методы обнаружения ошибок в работе ЭВМ. – М.: Мир, 1974. - С.32-41. Додаткова 2. Бохман Д., Постхоф Х. Двоичные динамические системы.

Контрольні запитання
1. Що є предикатом, чи є предикат булевою функцією, від кількох аргументів може бути предикат? 2. Що є предметними змінними та предметними постійними, яка між ними різниця?

Основна
1. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.608-621. 2. Горбатов В.А. Основы дискретной математики. – М.: Высш.шк., 1986. - С.78-81. 3. Новиков Ф.А

Основна
1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 2. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001

Додаткова
13. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учебное пособие. – М.: Лаборатория Базовых Знаний, 2001. 14. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-

Для практичних занять
20. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів заочної форми навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2001.

ТЕОРІЯ МНОЖИН І АЛГЕБРАЇЧНИХ СИСТЕМ4
Лекція 1. Основні поняття теорії множин 4 1.1. Основні поняття і завдання множин 4 1.2. Операції над множинами. Формули. Тотожності 5 1.3. Доказ тотожностей. Булева алгеб

ГРАФИ78
Лекція 14. Визначення і представлення графів 78 14.1. Основні визначення 78 14.2. Способи представлення графів 81 Лекція 15. Визначення графів. Зважені графи 86

СКІНЧЕННІ АВТОМАТИ101
Лекція 18. Функціонування абстрактного автомата 101 18.1. Абстрактний автомат 101 18.2. Способи завдання автоматів 102 18.2.1. Табличний спосіб 102 18.2.2. Графі

Лекція 22. Булеві функції 123
22.1. Логічні функції 123 22.2. Булеві функції 123 22.3. Логічні формули 125 Лекція 23. Завдання булевих функцій. Приведення формул 127 23.1. Способи завдання бу

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги