Відповіді дискретна математика
1. Що називається об'єднанням, перетином, різницею, симетричної різницею множин, доповненням множини?
2. Що таке ін'єкційних, сюр'ектівное, биективное відображення? (З прикладами)
Що ви знаєте про потужності множин двійкових наборів і про потужність безлічі всіх підмножин даної множини?
4. Що таке правило твори? (З прикладом)
5. Що таке перестановки і що ви знаєте про число перестановок? (З прикладами)
6. Що таке розміщення і що ви знаєте про число розміщень? (З прикладом)
7. Що таке поєднання і що ви знаєте про число поєднань? (З прикладом)
8. Що таке перестановки і що ви знаєте про їх числі?
9. Що таке рефлексивне, симетричне, транзитивне відношення, відношення еквівалентності і яке його основна властивість?
11. Що таке відношення строгого порядку, несуворого порядку?
12. У чому полягає числове порівняння двійкових наборів і як порівняти виконавчі набори по Парето?
Об'єднання - таке мн-во, елементами якого явл всі елементи множини А і В
Перетин - таке мн-во, елементи якого одночасно * входять в А і в В
Різниця А і В - таке мн-во, елементи якого належать А, але не належать В
Симетрична різниця - таке мн-во, в яке входять тільки
елементи мн-ва А і тільки елементи мн-ва B
Доповнення мн-ва - різниця універсального і заданого мн-ва
Відображення називають ін'єкційних. якщо різні елементи мн-ва А переходять в різні елементи мн-ва В.
Відображення називають сюр'ектівним. якщо кожен елемент мн-ва В має свій прообраз в мн-ве А.
Відображення биективно, коли воно ін'єкційних і сюр'ектівно.
Мн-у всіх двійкових наборів довжини п позначається Bin. Для будь-якого n - card =.
Мн-у всіх подмн-в даного мн-ва А позначається
Декартових твором мн-в А і В називається мн-во всіх пар (а, Ь), де а прин А, b прин В. обозн АхВ.
Перестановка - упорядкований набір чисел (1,2. П), зазвичай трактований як біекція на безлічі, яка числу i ставить у відповідність i-й елемент з набору, п різних предметів можна переставити п! різними
Нехай є п різних предметів, з яких потрібно вибрати клетук, причому порядок вибору істотний.
Нехай з n різних предметів потрібно вибрати до штук, але
порядок вибору НЕ істотний.
Іноді серед переставляються предметів є однакові. Нехай є kl однакових предметів 1-го типу, к2 предметів 2-го типу. предметів m-го типу, а всього n = kl + k2 +. + Предметів.
=
Будь-яке подмн-під Г декартова твори АХА називається відношенням на мн-ве А.
тобто Г-це мн-во деяких пар, що знаходяться в даному відношенні, обозн аГЬ
Відношення називається рефлексивним, якщо Ага для всіх а прин А. тобто кожен елемент знаходиться в цьому відношенні сам із собою
Отнош називається антирефлексивне. якщо ага ніколи не виконується.
Отнош називається симетричним, якщо аГЬ => ЬГа (для всіх)
Отнош називається антисиметричних, якщо аГЬ і ЬГа одночасно неможливо.
Отнош називається асиметричним, якщо аГЬ, ЬГа => а = Ь
Отнош називається транзитивним, якщо аГЬ, ЬГс => АГС
Якщо відношення рефлексивно, симетрично і транзитивній, то воно наз. відношенням еквівалентності.
Основне св-во. Якщо на мн-ве А задано відношення еквівалентності, то мн-во розпадається на об'єднання непересічних класів еквівалентності, в кожному з яких всі елементи еквівалентні один одному.
Отнош Г називається відношенням строгого порядку, якщо воно антирефлексивне, антисиметрично і транзитивне.
Отнош Г називається відношенням нестрогого порядку, якщо воно рефлексивно, асиметрично і транзитивне.
Числове порівняння двійкових наборів полягає в порівнянні з першим біту
Очевидно, з таким ставленням це мн-во лінійно (цілком) упорядковано, тобто будь-які набори можемо порівняти як числа.
Порівняння по Парето - порівняння за всіма бітам
12.Что таке орграф, граф, вершина, дуга, ребро, шлях, ланцюг, контур, цикл?
13. Як алгоритм рішення задачі про найкоротший шлях в невиважені графі?
15.Что таке «Ейлерова Ланцюг» (цикл) У будь графів існують?
16.Формула Ейлера. Для яких об'єктів вона вірна?
17.Як виглядають непланарние графи №1 і №2,1 та 2 типу, і в чому полягає теорема Куратовского-Понтрягіна?
18.Что таке хроматичної число графів? Що ви знаєте про його величиною?
19.Что таке хроматична величина?
орграф - мультіграф, ребрах якого присвоєно напрямок '
Граф - сукупність непорожньої безлічі вершин і вузлів Вершина - точка, де сходяться і виходять дуги і ребра
Дуга - орієнтоване ребро
Ребро - єднальна двох вершин в графі
Шлях - послідовність ребер або дуг, де кінець одного (однієї-) служить початком іншого (іншої), (крім останньої)
Ланцюг це шлях в неорграфе
Контур - замкнутий шлях в орграфе
Цикл - замкнута ланцюг в графі
Алгоритм для невиваженого графа
1) Вершини А дамо індекс Про
2) Всім вершин, суміжних з А, дамо індекс 1
3) Всім вершин, суміжних з 1, дамо індекс 2.
Процес зупиняється, коли вершина В отримає певний індекс n (n - довжина найкоротшого шляху)
4) Побудуємо цей шлях, повертаючись з вершини В у вершину А
5) Серед вершин, суміжних з В, обов'язково знайдеться вершина С з індексом (n-1)
Повертаємося в С і продовжуємо процес. Рівно через п кроків ми прийдемо в вершину індексу 0, тобто в вершину А.
Алгоритм длявзвешенного графа
1) Вершини А дамо індекс 0, а всім іншим + °°
2) Будемо послідовно перебирати всі пари суміжних вершин «х» і «у». Кожен раз перевіряємо нерівність
Якщо воно виконується, то зменшуємо індекс індекс, замінивши його на3) Процес зупиняється, коли жоден з індексів можна зменшити. Побудуємо шлях з цією сумою, повертаючись з В в А. Серед всіх суміжних з В вершин, є С, де
4) Повертаємося в С, повторюємо процес, а через деякий час прийдемо в вершину з індексом 0 (вершина А).
Ейлерова ланцюг графа - ланцюг, яка содержітвсе ребра по одному разу.
Ейлером цикл графа - цикл графа, що проходить через кожне ребро графа рівно по одному разу.
Зв'язний граф має незамкненою ейлеровой ланцюгом <=> дві його вершини мають непарну ступінь.
Зв'язний граф має незамкнутим ейлеровим циклом Про все його вершини мають парну ступінь.
В + Г-Р = 2 Виконується для плоского зв'язного графа, де В - вершина, Г - грань, Р - ребро. Також підходить для багатогранників в просторі (при відображенні втрачається розтягнута грань і виходить нескінченна грань)
В + Г-Р = К + 1<- Если граф плоский, но не связный. Где К - число связных компонентов, К+1 — Эйлерова характеристика графов.
20. Що таке матриця суміжності орграфа? яким св-вом має матриця суміжності неорграфа?
21. Як будується код Харари?
22. Що називається деревом, ордеревом, і як вони пов'язані між собою?
23. Як будується префіксний код бінарного ордерева?
24. Як будується код Прюфера?
25. Які 3 способи обходу бінарного дерева ви знаєте? (З прикладом> = 10 верш)
26.Что називається атомом, списком і як пов'язані дерева зі списком?
27. Як пов'язані число вершин? (З прикладом)
Нехай дано орграф з п пронумерованими вершинами. Матриця А, розміром пхп, заповнених числами: 1, якщо сущ дуга з i-ї вершини в j- ю; 0- якщо немає, називається матрицею суміжності.
Для неорграфа матр суміжності симетрична щодо головної діагоналі
1) довільно нумеруем вершини, состалял трикутник матр суміжності
2) маємо його у вигляді двійковій рядки
3) міняємо нумерацію вершин іншими двоіче числами, найбільше - код Харари, а відповідна йому нумерація - канонічна.
Дерево - зв'язний граф, який не має циклів.
Ордерево - оргаф, у якого сущетвует вершина х0 така, що
в х0 не входить жодна дуга
в інші - єдина
не має контурів
Якщо в ордереве перетворити дуги в ребра, (прибрати стрілки), то отримаємо дерево
Префіксний кол бінарного ордерева
Нумеруємо все вершини крім кореня, лівому корені О, правому -1, потім лівому, що виходить від лівого 00, правому-01, і навпаки (що виходить від правого -10 і 11). У підсумку - префіксний код (вважаються всі висячі вершини зліва направо)
Нехай дано дерево з п пронумерованими вершинами. Список вершин: 1,2,3. п
Зліва направо шукаємо першу висячу вершину (al). Її видаляємо зі списку і з дерева, а єдину суміжну з нею вершину (И) заносимо в новий список, майбутній список Прюфера. Цей процес повторюємо (п-2) рази. В кінці отримуємо список
Способи обходу бінарного ордерева
1) прямий (корінь, ліве, потім праве піддерево, КЛП)
2) зворотний (ліве піддерево, корінь, праве, ЛКП)
3) кінцевий (ліве піддерево, праве, потім корінь, ЛПК)
Атом - літери, що утворюють послідовність (будь-неподільний об'єкт)
Список - послідовність атомів, елементів і списків, колективна коми і укладена в загальні дужки.
Кожним атомам або списками відповідає загальна безіменна вершина, нащадками якої вони є, тоді кожному списку можна буде зіставити дерево.
Кожному бінарним ордереву можна зіставити список висячих
вершин. Глибина списку збігається з глибиною дерева.
Глибина - максимальне число вкладених один в одного дужок
n = - число вершин через глибину
k = - глибина через число вершин
глибина дерева - число рівнів. Збігається з глибиною списку