ДМ_МУ_САМ РАБ

4.Чи є у транспортній мережі петлі?

5.Чи можна використовувати алгоритм Дейкстри, якщо дуги графа мають від’ємну вагу?

6.Надайте формальний опис алгоритму Дейкстри побудови найкоротших шляхів із вершин.

7.Опишіть алгоритм Флойда пошуку найкоротших шляхів між всіма парами вершин графа.

8.Чим відрізняється алгоритм Флойда і алгоритм Данцига пошуку найкоротших шляхів у графі?

9.Порівняйте роботу алгоритмів Флойда і Данцига пошуку найкоротших шляхів у графі.

4.8.24 Тема 13 «Течії у мережах»

Вивчення теми 13 «Течії у мережах» пов’язане із розглядом таких питань

[1-5, 7, 9-11, 13-16, 19-23]: модель зваженого графу, кожній дузі якого приписана течія деякої речовини; задача про максимальну течію; теорема про максимальну течію і мінімальний розріз; теорема Форда-Фалкерсона; алгоритм Форда-Фалкерсона, його реалізація.

Основними поняттями і визначеннями теми «Течії у мережах», які надаються в [1-5, 7, 9-10, 14-16, 19-20, 22], є: зважений граф; мережа; течія;

пропускна здатність (місткість) дуги; джерело; стік; проміжний вузол; чиста течія; течія за дугою; переріз; пропускна здатність перерізу.

4.8.25 Контрольні запитання

1.Який граф називається мережею?

2.Поясніть поняття «пропускна здатність (місткість) дуги графа».

3.Що являє собою течія у мережі?

4.Як можна зобразити течії у неорієнтованих графах?

5.Які вершини називаються джерелом, стоком, проміжними вершинами?

6.Надайте загальну постановку задачі про максимальну течію.

7.Охарактеризуйте використання теореми про максимальну течію і мінімальний розріз.

8.Для розв’язання яких задач використовується алгоритм Форда-

Фалкерсона?

61

4.9Змістовий модуль 9 «Елементи теорії формальних граматик»

4.9.1Основні положення теорії формальних граматик

Вивчення змістового модуля «Елементи теорії формальних граматик» пов’язане із розглядом таких питань [1, 2, 4, 16, 20, 22]: задача формалізації мов та перекладу. перетворення рядків символів; задання мов за допомогою граматик; типи граматик; проблеми, які розв’язуються для граматик як засобів опису мови; регулярні вирази і мови; дерева виводів; стратегії виводів; побудова граматики мови програмування.

Основними поняттями і визначеннями змістового модуля «Елементи теорії формальних граматик», які надаються в [1, 2, 4, 16, 20, 22], є: алфавіт;

рядок; символ; під алфавіт; поширення алфавіту; порожній рядок; довжина рядку; конкатенація рядків; підрядок; граматика; мова, що розпізнає і породжує граматики; термінальні символи; нетермінальні символи; початковий символ; вивід рядків; форма Бекуса-Наура; ієрархія Хомського; граматика загального вигляду; контекстно-залежна граматика; контенстно-вільна граматика; право лінійна граматика; ліво лінійна граматика; регулярні граматики; скінченні мови; регулярний вираз; регулярна мова; дерево виводу; стратегії виводу; алфавіт мови програмування; службові слова; ідентифікатори; оператори.

4.9.2 Контрольні запитання

1.В яких випадках для роботи ЕОМ необхідний розв’язок задачі перекладу з однієї мови на іншу?

2.Для чого розв’язується задача формального задання мов?

3.Чим відрізняється процес перекладу в літературі від перекладів, що виконується при роботі ЕОМ?

4.Наведіть приклади алфавітному зображення у повсякденному житті: а) неперервної інформації; б) дискретної інформації.

5.Дайте визначення алфавітного способу задання інформації, алфавіту,

рядку.

6.Дайте визначення операції конкатенації рядків.

7.Дайте визначення мови.

8.Чому для того, щоб описати мову, необхідно застосовувати спеціальені формальні системи (наприклад, граматики)?

9.Дайте визначення граматики та її складових.

10.Які граматики є тими, що розпізнають, і які тими, що породжують?

62

11.Яким чином граматики, що породжують, визначають мову?

12.Для чого застосовується форма Бекуса-Наура?

13.Визначте ієрархію Хомського для граматик.

14.Який тип мов породжує кожний з типів граматик?

15.Дайте визначення регулярного виразу.

16.Як зв’язані регулярні граматики, регулярні вирази і регулярні мови?

17.Як визначається пріоритет операцій у регулярних виразах?

18.Що таке вивід у граматиці?

19.Що таке дерево виіводу?

20.Символи якого алфавіту є листями дерева виводу?

21.Які стратегії виводу у граматиках ви знаєте?

22.Що складає алфавіт мови програмування?

23.Що таке ідентифікатор, оператор, умовний оператор, оператор циклу?

24.Який принцип побудови граматики мови програмування?

4.10Змістовий модуль 10 «Елементи теорії скінченних автоматів»

4.10.1Основні положення теорії скінченних автоматів

Вивчення змістового модуля «Елементи теорії скінченних автоматів» пов’язане із розглядом таких питань [1, 2, 4, 16, 20, 22]: загальна характеристика автоматів; схема автомата і характеристика її складових частин; робота автоматів, яка складається з послідовності тактів; автомати, що використовуються для визначення мови (розпізнавачі); зв’язок різних видів розпізнавачей та граматик; характеристика мов з ієрархії Хомського; скінченні автомати; способи завдання скінченних автоматів (завдання автомату за допомогою таблиці та за допомогою діаграми станів); автомати Мили і Мура; відповідність скінченного розпізнавача регулярній граматиці і регулярному виразу; автомати з магазинною пам’яттю; розпізнавання рядків автоматом; мова, що визначається автоматом; машина Тьюринга; тезис Черча-Тьюринга; лінійно-обмежені автомати.

Основними поняттями і визначеннями змістового модуля «Елементи теорії скінченних автоматів», які надаються в [1, 2, 4, 16, 20, 22], є: автомат; схема автомата; вхідна стрічка; керуючий пристрій зі скінченною пам’яттю; робоча пам’ять автомата; вхідна голівка; односторонній автомат; тільки читаючий автомат; читаючий автомат; пишучий автомат; такт роботи автомата; початкова конфігурація автомата; заключна конфігурація автомата; детермінований автомат; недетермінований автомат; розпізнавач; мова, що визначена розпізнавачем; скінченний автомат; автомат з виходом і без виходу; стан автомату; вхідні символи автомата; вихідні символи автомата; функція переходів; початковий стан автомату; завершальний стан автомату; діаграма

63

станів; автомат Мілі; автомат Мура; приклади автоматів Мілі і Мура; регулярна мова; контекстно-вільна мова; контекстно-залежна мова; автомат з магазинною пам’яттю (МП-автомат); машина Тьюринга, її схема; лінійно-обмежений автомат.

4.10.2 Контрольні запитання

1.Для дослідження яких питань використовуються автомати?

2.Зобразіть схему автомата і назвіть складові частини автомата.

3.Поясніть принцип дії і побудову кожної частини автомата.

4.Що включає такт роботи автомата?

5.Візначте поняття конфігурації автомата. Що таке початкова і кінцева конфігурації автомата?

6.Чим відрізняються детермінований і недетермінований скінченні автомати?

7.Яку задачу розв’язують автомати, що називаються розпізавачами?

8.Яким чином визначається, що автомат допускає вхідний рядок?

9.Що таке мова, визначена розпізнавачем?

10.Як зв’язані різні види розпізнавачей та граматик?

11.Зобразіть схему скінченного автомата та опишіть його пристрій.

12.Дайте визначення скінченного автомата, його складових.

13.Чим відрізняються скінченні автомати з виходом і без виходу?

14.Дайте визначення автоматів Мілі і Мура.

15.Яким чином функціонують скінченні розпізнавачі?

16.Який вид мов визначається скінченними автоматами? За допомогою яких формальних систем, крім скінченних автоматів, можна задати цей вид мов?

17.Зобразіть схему автомата з магазинною пам’яттю.

18.Дайте визначення автомата з магазинною пам’яттю.

19.Який вид мов можна розпізнавати за допомогою МП-автомата?

20.Сформулюйте тезис Черча-Тьюринга.

21.Які мови можна розпізнавати за допомогою машини Тьюринга?

22.Зобразіть схему машини Тьюринга.

23.Що зображує лінійно-обмежений автомат, і які мови він визначає?

64

5 ОСНОВНІ РЕКОМЕНДАЦІЇ З ОРГАНІЗАЦІЇ САМОСТІЙНОЇ РОБОТИ

Теоретичні й практичні матеріали дисципліни «Дискретна математика» запропоновано вивчати в порядку проходження їх у конспекті лекцій, методичних вказівках з практичних занять та самостійної роботи студентів.

Методичні вказівки до вивчення дисципліни «Дискретна математика» містять список літератури (підручники, навчальні посібники й монографії), а

також її характеристики, якими можна скористатися для уточнення матеріалу, що викладається, або, за бажанням, для більш глибокого вивчення деяких теоретичних положень і практичних прикладів.

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

Контрольні завдання з розділів дисципліни, а також приклади розв’язання цих завдань можна знайти в літературі [20-23], а, за бажанням, у літературі, яка наведена у методичних вказівках.

Контроль та самоконтроль вивчення матеріалів дисципліни «Дискретна математика» повинен виконуватися таким чином:

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

студент повинен скласти приклади, які пояснюють положення кожної теми змістового модуля;

студент повинен виконувати завдання, які наведено в методичних вказівках до практичних занять з дисципліни «Дискретна математика».

65

Електронне навчальне видання

МЕТОДИЧНІ ВКАЗІВКИ до самостійної роботи з дисципліни

«ДИСКРЕТНА МАТЕМАТИКА»

для студентів усіх форм навчання напряму 6.050101 – Комп’ютерні науки

Упорядники:	ВАСИЛЬЦОВА Наталія Володимирівна
	ЧАЛА Лариса Ернестівна

Відповідальний випусковий

В.М. Левикін

66