Розділ 3 Елементи теорії графів. Елементи теорії алгоритмів.

Тема 4. Елементи теорії графів

1. Означення графа. Зображення графів

2. Способи завдання графа: матрицею інцидентності, списком ребер, матрицею суміжності.

2. Ізоморфізм графів.

3. Елементи графів.

4. Маршрути в графах: ланцюги, цикли.

5. Ейлерові графи. Необхідні та достатні умови наявності в графі ейлерова цикла (теорема Ейлера).

6. Досяжність і зв’язність. Компоненти зв’язності.

7. Операції над графами.

8. Види графів. Графи без циклів: дерева і ліс. Дерево з коренем.

Приклад. Орграф заданий матрицею суміжності , яка подана у блочному вигляді. Треба:

1. намалювати орграф;

2. знайти матрицю інцидентності ;

3. знайти всі шляхи довжини 2 і 3;

4. знайти степені вершин , , , ;

5. знайти компоненти зв’язаності та сильної зв’язаності;

6. побудувати граф конденсації графа ;

7. визначити тип зв’язаності графа .

1. ; 6. ;

2. ; 7. ;

3. ; 8. ;

4. ; 9. ;

5. ; 10. .

Блоки матриці суміжності:

; ;

; .

Тема 5. Елементи теорії алгоритмів

1. Інтуїтивне означення алгоритму. Приклади алгоритмів. Блок-схеми алгоритмів.

2. Проблема уточнення поняття алгоритму. Машина Тьюрінга.

3. Функції, обчислюванні за Тьюрінгом. Теза Тьюрінга.

4. Універсальна машина Тьюрінга.

5. Приклад числової функції, яка не є обчислюванною за Тьюрінгом.

6. Алгоритмічно нерозв'язувані проблеми.

Приклад. За заданою машиною Тьюрінга :

і початковою конфігурацією знайти заключну конфігурацію

1. ; 6. ;

2. ; 7. ;

3. ; 8. ;

4. ; 9.

5. ; 10.

4. Рекомендації до організації самостійної роботи

Кафедра вищої математики ДУІКТ пропонує кожному студенту врахувати наступні рекомендації:

1. Враховуючи свої індивідуальні особливості та можливості, обчислити реальний час для самостійної роботи у семестрі та частину цього часу на вивчення дискретної математики. Для якісного засвоєння навчальної програми семестру студенту-заочнику потрібно біля 80 академічних годин.

2. Придбати зошит на 48-96 сторінок і оформити його титульний лист так:

Робочий зошит

З дискретної математики на 3 семестр

студента (студентки) 2 курсу, групи ________,

факультету Інформаційної безпеки

_________________________________

^{(прізвище, ім’я, по-батькові)}

залікова книжка № __________

Зошит

початий ______ закінчений ________

перевірений викладачем ________ __________________

^{(підпис) (прізвище та ініціали)}

Дата _______

3. Для вивчення матеріалу певного розділу програми студенту потрібно:

а) уважно прочитати матеріал у рекомендованих підручниках, ознайомитись із змістом екзаменаційних завдань відповідного розділу, щоб визначити основу розділу та його типові приклади;

б) в робочому зошиті записати стислі відповіді на усі завдання розділу, що вивчається, з обов’язковим розв’язуванням заданих прикладів ( – номер варіанту, який визначається за останньою цифрою номера залікової книжки: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10).

4. Коли виникають труднощі у відповідях на теоретичні завдання або при розв’язуванні прикладів, треба відповідний матеріал знову знайти у підручнику (або в додатковій літературі), ознайомитися повторно, більш уважно і, при необхідності, з викладачем на консультації.

Зауваження 1. Для виконання третьої рекомендації студенту потрібно 7-10 астрономічних годин. Доцільно цю роботу виконати в один день.

Зауваження 2. Кожному студенту буде дозволено під час семестрового екзамену користуватись лише своїм власноруч написаним робочим зошитом.