Основні вимоги до алгоритмів.

1) Будь – який алгоритм застосовується до початкових даних і видає результати. У технічних термінах це означає, що алгоритм має входи і виходи. Крім того під час роботи алгоритму з’являються проміжні результати, що використовуються далі. Таким чином алгоритм має справу з початковими, проміжними та вихідними даними.

Треба уточнити поняття даних, тобто які вимоги мають задовольняти об’єкти, щоб з ними могли працювати алгоритми. До алгоритмічних об’єктів відносяться: числа, вектори, матриці суміжності, формули,… Набір елементарних об’єктів утворюють скінченний алфавіт початкових символів (цифр, літер, тощо), з яких будуються інші об’єкти.

2) Дані для розміщення потребують пам’яті. Пам’ять вважається однорідною і дискретною, тобто складається з однакових комірок, причому кожна комірка може містити один символ алфавіту даних. Таким чином одиниці даних і пам’ять узгоджено. При цьому пам’ять може бути нескінченою.

3) Виконавцем алгоритму може виступати людина або технічний пристрій (ЕОМ).

 

Властивості алгоритмів.

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

1) Детермінованість: визначення кроків алгоритму: після кожного кроку зазначається, який крок слід робити далі або дається команда зупинки, після чого робота алгоритму вважається закінченою. Ця властивість означає, що застосування алгоритму до тих самих даних має привести до одного і того ж результату.

2) Масовість: алгоритм може бути використаний для розв’язання цілого класу задач одного типу з різними початковими даними (квадратні рівняння з різними коефіцієнтами).

3) Результативність: це значить, що після виконання певної кількості кроків робота алгоритму повинна зупинитись із вказівкою того, що вважати результатом.

4) Зрозумілість: алгоритм має бути зрозумілим конкретному виконавцю, який повинен виконати кожну команду у строгій відповідності з її призначенням.

5) Дискретність: можливість розбиття алгоритму на скінченну кількість етапів, причому результати попереднього етапу є вхідними для наступного.

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

Потрібно розрізняти:

- опис алгоритму (інструкцію чи програму);

- механізм реалізації алгоритму (ЕОМ), який містить засоби запуску, зупинки, реалізації елементарних кроків, видачі результатів та забезпечення детермінованості, тобто керування ходом обчислення;

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

Способи опису алгоритмів: словесний, табличний, графічний, псевдокод,…

Алгоритм для ЕОМ найзручніше зображати графічно у вигляді схем.

Схеми алгоритмів складаються з:

- символів, що мають задане значення;

- короткого пояснювального тексту;

- сполучних ліній.

Схема програми складається з:

ü символів процесу, які показують фактичні операції оброблення даних (включаючи символи, що визначають шлях, якого варто дотримуватись з урахуванням логічних умов);

ü лінійних символів, що показують потік керування;

ü спеціальних символів, які використовують для полегшення написання та читання програми.

Основні типи процесів оброблення інформації:

o лінійний: оброблення інформації здійснюється послідовно, одна дія за іншою і кожний етап алгоритму виконується тільки один раз;

o розгалужувальний: інформація обробляється по одному із двох можливих шляхів, тобто ті чи інші дії виконуються залежно від деякої умови;

o циклічний: дії оброблення інформації потрібно виконати багаторазово.

 

 

Машина Тьюринга.

Машина Тьюринга (МТ)– це математична модель пристрою, який породжує обчислювальні процеси. Її використовують для теоретичного уточнення поняття алгоритму та його дослідження. Названо цю модель ім’ям англійського математика А.Тьюринга, який запровадив її в 1936р.

У кожній МТ є три частини:

1) стрічка поділена на комірки;

2) пристрій керування (ПК);

3) головка читання – запису (Г).

 

Г

 

Із кожною МТ пов’язано два скінченних алфавіти:

1) алфавіт зовнішніх символів А;

2) алфавіт внутрішніх станів

З різними МТ можна пов’язувати різні алфавіти.

Алфавіт зовнішніх символів А часто називають зовнішнім, а його елементи – буквами. Один символ алфавіту А називають порожнім: L (). Усі інші букви алфавіту А називають не порожніми. Комірку, у яку записано букву L називають порожньою.

МТ працює у часі, який вважають дискретним, його моменти занумеровано: 1, 2,…У кожний момент часу стрічка містить скінченну кількість комірок. Головка пересувається вздовж стрічки, у кожний момент часу вона перебуває над певною коміркою стрічки, зчитує букву записану у цій комірці. У наступний момент головка залишається над цією ж коміркою (позначають Н) або пересувається на одну комірку вправо (П), або пересувається на одну комірку вліво (Л).

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

Алфавіт внутрішніх станів - це внутрішня пам’ять. На відміну від нескінченної зовнішньої пам’яті на стрічці, вона скінченна. Елемент - називають заключним внутрішнім станом, - початковим внутрішнім станом. Пересування головки вздовж стрічки залежить від зчитаної букви та внутрішнього стану машини.

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

1) змінює букву зчитану в момент часу зі стрічки, на нову букву (або );

2) пересуває головку в одному з напрямків Н, П, Л;

3) змінює внутрішній стан машини в момент часу на новий стан , в якому машина перебуватиме в момент часу (може бути ).

Таку дію пристрою керування називають командою і записують , де

- внутрішній стан машини в даний момент;

- буква на стрічці, зчитувана в цей момент;

- буква, на, яку змінюється буква (або );

D - напрямок пересування головки: Н, П, Л;

- внутрішній стан машини в наступний момент часу.

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

Робота МТ – це послідовність кроків одного за другим без пропусків, починаючи з першого. Роботу МТ повністю визначено, якщо в початковий момент задано:

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

2) положення головки Г;

3) внутрішній стан машини.

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

Зазвичай у початковий момент часу внутрішній стан машини - , а головка перебуває над першою зліва коміркою стрічки.

 

L

Наприклад: початкова конфігурація така: L , початковий стан .

Якщо в роботі МТ в момент часу виконається команда, права частина якої, містить символ , то в такий момент роботу машини вважають завершеною; тоді говорять, що машина застосована до слова в початковій конфігурації. Якщо ж у роботі машини в жодний момент не зустрічається заключний стан, то процес обчислень буде нескінченним. У такому разі говорять, що машина не застосована до слова в початковій конфігурації.

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

 

1. Поняття алгоритму.

2. Етапи розв’язування задачі на ЕОМ.

3. Вимоги до алгоритмів. (*)

4. Властивості алгоритмів. (*)

5. Типи процесів оброблення інформації. (*)

6. Принцип роботи машини Тьюринга, його складові. (**)

 

Література:

Ю.В. Нікольський, В.В.Пасічник, Ю.М. Щербина. Дискретна математика. Підручник для вищих навчальних закладів. Київ. 2007р. розділ 9.

 

 

Розділ 7. Контрольні завдання.

 

1. Множини А, В, С – підмножини множини дійсних чисел R.

Знайти: , , , , ,

 

Варіант	Множини
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

 

 

2. Накреслити діаграму Ейлера для трьох множин A, B, C, які утворюють множину F і позначте штриховкою її ділянку.

 

Варіант	Множина
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

 

3. За допомогою таблиць істинності довести правильність рівносильності.

 

Варіант	Рівносильність
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

 

 

 

4. Провести логічні перетворення функції f. Одержати:

1) попередню форму;

2) ДНФ;

3) ДДНФ, область істинності;

4) КНФ;

5) ДКНФ, область хибності.

 

Варіант	Функція

 

5. Для функцій задані номери наборів, на яких вона дорівнює одиниці. Мінімізувати цю функцію методом Квайна.

 

Варіант	Номери наборів
	3, 6, 7, 9, 10, 11, 15
	2, 3, 5, 7, 11, 14, 15
	0, 1, 4, 10, 11, 12, 15
	2, 3, 6, 8, 9, 13, 14
	2, 3, 5, 7, 10, 11, 15
	0, 3, 5, 7, 10, 14, 15
	0, 2, 5, 8, 13, 14, 15
	0, 3, 5, 7, 8, 11, 12
	1, 2, 3, 7, 11, 12, 15
	0, 1, 2, 3, 6, 8, 15
	2, 3, 5, 6, 10, 12, 13
	0, 1, 3, 5, 6, 7, 11
	1, 2, 3, 4, 6, 7, 11
	0, 2, 3, 5, 6, 7, 11
	1, 2, 3, 4, 6, 7, 15
	0, 2, 3, 5, 6, 7, 15
	2, 3, 4, 7, 8, 9, 12
	1, 4, 5, 9, 10, 11, 13
	0, 3, 6, 7, 8, 10, 12
	6, 9, 10, 11, 12, 14, 15
	7, 8, 10, 11, 13, 14, 15
	2, 7, 9, 10, 11, 14, 15
	3, 6, 10, 11, 13, 14, 15
	0, 1, 2, 3, 4, 7, 8
	1, 3, 6, 7, 10, 11, 15
	1, 2, 3, 5, 8, 9, 11
	0, 1, 3, 9, 10, 11, 15
	3, 4, 5, 7, 10, 13, 15
	4, 5, 6, 11, 12, 13, 15
	1, 5, 6, 7, 11, 13, 15

 

 

Зразки розв’язання.

 

1.Множини А, В, С – підмножини множини дійсних чисел R. Знайти: , , , , , , якщо .

Розв’язання:

2. Накреслити діаграму Ейлера для трьох множин A, B, C, які утворюють множину F і позначте штриховкою її ділянку, якщо

 

3. За допомогою таблиць істинності довести правильність рівносильності.

 

 

4. Провести логічні перетворення функції . Одержати:

1) попередню форму;

2) ДНФ;

3) ДДНФ, область істинності;

4) КНФ;

5) ДКНФ, область хибності.

 

Розв’язання:

1) - попередня форма;

2) -ДНФ;

3) - ДДНФ;

Область істинності: 110, 100, 001, 000, 111;

4)

- КНФ

5)

- ДКНФ;

Область хибності: 010, 101, 011.

5. Для функцій задані номери наборів, на яких вона дорівнює одиниці. Мінімізувати цю функцію методом Квайна на наборах 7, 8, 10, 11, 13, 14, 15.

Подамо функцію в ДДНФ:

Виконаємо всі можливі неповні склеювання першого члена, потім другого, третього і т. д.

Проведемо всі можливі операції поглинання конституент одиниці і результат запишемо у таблицю (перше склеювання)

№ п/п	Номер склеюваної конституенти одиниці	Імпліканта	Склеювана змінна
1.	1-7
2.	2-3
3.	3-4
4.	3-6
5.	4-7
6.	5-7
7.	6-7

 

З таблиці видно, що всі конституенти одиниці поглинаються імплікантами, отриманими після склеювання. В результаті отримуємо таку функцію:

Проведемо друге склеювання конституент одиниці:

 

№ п/п	Номер склеюваної конституенти одиниці	Імпліканта	Склеювана змінна
1.	3-7
2.	4-5

 

 

- скорочена ДНФ

 

Будуємо імплікантну матрицю для одержаної функції F.

 

№п/п	Проста імпліканта	Конституента
				×	×