Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Застосування формул включень і виключень та розбиття для розв’язування задач в дискретній математиці
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Менеджмент
Кафедра:
Кафедра програмного забезпечення
Інформація про роботу
Рік:
2004
Тип роботи:
Курсова робота
Предмет:
Основи дискретної математики
Частина тексту файла (без зображень, графіків і формул):
Інститут менеджменту та економіки „Галицька Академія”
Кафедра програмного забезпечення та штучного інтелекту
КУРСОВА РОБОТА
з дисципліни: “Основи дискретної математики”
Тема – Застосування формул включень і виключень та розбиття для розв’язування задач в дискретній математиці.
ПОЯСНЮВАЛЬНА ЗАПИСКА
КР.ПЗ- 21. 00. 00. 000. ПЗ
Студент групи ПЗ-04-1 __________ (Кайданська Н.В)
(підпис)
Допускається до захисту
Керівник курсового проекту
Доцент (Плотніков В. Г.)
(посада) (підпис) (дата) (розшифровка підпису)
м. Івано-Франківськ
2004
Анотація
В курсовій роботі проаналізовані основні поняття і властивості формул включень і виключень та розбиття і розв’язання певних типів задач.
Summary
In the term paper there are the analysed basic concepts and properties of formulas inclusions and deenergizings and decision and unbind certain type of tasks.
ЗМІСТ
Вступ
1. Розбиття. ...................................................................................................
2. Поліномна формула.
3. Формула включень і виключень. .....................................................
4. Розв’язування задач на розбиття................................................
5. Застосування формули включень і виключень для
розв’язування задач.........................................................................
Висновки..................................................................................
Перелік використаних літературних джерел........................
Вступ
Комбінаторика – це наука, основним завданням якої є перерахунок і перелічення елементів у скінчених множинах. Якщо в задачі визначається, скільки елементів, які належать заданій скінченій множині, мають деяку властивість або заданий набір властивостей, то ця задача називається задачею перерахунку. В інших випадках для яких-небудь цілей треба вилучити всі елементи множини, які задовольняють задані властивості. Такі задачі називаються задачами перелічення.
Зустрічаються також задачі, коли на початковій скінченій множині елементів означено деяку цільову функцію, причому інтерес становлять елементи множини, що забезпечують мінімальне (або максимальне) значення цієї функції. У цьому разі маємо окремий випадок задачі оптимізації. Тут під її розв’язком у сильному значенні розуміють знаходження сукупності всіх елементів, які забезпечують мінімальне (або максимальне) значення цільової функції, а під розв’язком у слабкому значенні – відшукання довільного елемента, що забезпечує мінімальне (або максимальне) значення цільової функції. Іноді цікавляться лише мінімальним (або максимальним) значенням функції.
Усі зазначені задачі пов’язані одна з одною. Так, при розв’язуванні задач оптимізації припускається, що в розпорядженні є метод перелічення елементів початкової множини (яка, як правило, є сукупністю елементів деякої великої множини, що задовольняє задану властивість), а для того щоб оцінити ефективність методів перелічення або оптимізації, часто доцільно розв’язувати задачу перерахунку елементів (у початковій множині або в деяких її підмножинах.
Розбиття.
Сукупність множин А1, А2, ..., Аn називається розбиттям множини А, якщо:
n
1.U Аі = А
i=1
2.Аі∩Аj = ( (i(j.
Підрахуємо число розбиттів скінченої множини Х, де (Х(= n, на k підмножин Х1,Х2,..., Хn(k(1), де
k
(ni = n, таких, що кожне Хі містить ni елементів, тобто,
i=1
k
U Хі = Х, Хі∩Хj = Ø при i ≠ j, │Xi│= ni, i=1,2,…,k. (1.1)
i=1
Нехай для деяких номерів і матимемо Хі = Ø. Число зазначених розбиттів при фіксованих ni позначимо через Cnⁿ1···ⁿk .
У цьому випадку набір підмножин множини Х у розбитті є впорядкованим (тобто Х1,...,Хk – впорядкована послідовність множин). Нижче, крім того, розглядається випадок, коли набір підмножин у розбитті не є впорядкованим.
Твердження 1. Справджується рівність Сnⁿ1···ⁿk =
Очевидно, кожну з множин Хі можна розглядати як сполучення без повторень.
Для утворення сполучення, що відповідає множині Х1, можуть бути використані всі елементи множини Х, тобто множина Х1 може бути вибрана Сnⁿ1 способами. Після вибору Х1 множина Х2 може бути вибрана Сⁿn-n1 способами (оскільки Х2 є підмножиною множини Х- Х1 та(Х-Х1 (= n-n1), і для будь-якого і, де 2≤і≤к, після вибору множин Х1,...,Хі-1 множина Хі може бути вибрана Сⁿn-n1-…ni-1 способами. Проте тоді за правилом добутку вибір упорядкованої послідовності множин Х1,...,Хk, які задовольняють умову що Х→У дорівнює Р(n,r), можна здійснити Сnⁿ1 Cⁿ2n-n1 …Cⁿn-n1-…nk-1 способами.
Використовуючи цей вираз і зробивши необхідні скорочення, дістанемо дане твердження. k
Твердження 2. Число Сnⁿ1···ⁿk, де ni ≥0, ∑ ni = n, дорівнює числу Pn
i=1
(n1, n2,…,nk) перестановок n елементів зі специфікацією{n1, n2,…nk}, серед елементів яких міститься n1 елементів першого типу, n2 елементів другого типу і т.д. аж до nk елементів k –го типу.
Кожній перестановці зазначеного типу поставимо у відповідність розбиття множини Х = {1,2,…,n} номерів елементів у вибірці на підмножини Х1,...,Хк, де Хі – множина номерів елементів і-го типу у вибірці. Очевидно виконується рівність :Х→У дорівнює Р (n,r).
Підрахуємо тепер, скількома способами можна розбити множину Х, де |Х| = n,на підмножини, серед яких для кожного і = 1,2,...,n
n
існують m(0 підмножин з і елементами, де (іті= n. При цьому, на
і=1 відміну від розглянутого вище випадку, тут набір підмножин у розбитті не є впорядкованим ( тобто порядок підмножин у розбитті не є суттєвим). Так, розбиття множини Х = {1,2,3,4,5}вигляду
{1,3}, {4}, {2,5};
{4}, {2,5}, {1,3};
{2,5}, {4}, {1,3}
вважаються однаковими. Позначимо число невпорядкованих розбиттів множини Х через N (m1,…,mn).
Твердження3. Справджується рівність N(m1,…mn) = _______n!________. m1!…mn!(1!)ⁿ1…(n!)ⁿ k.
Зазначимо, що кожне з невпорядкованих розбиттв, розглянутих при визначенні величини N(m1,…,mn), можна, нумеруючи множини в цьому розбитті, привести m1!…mn! способами до впорядкованих розбиттів вигляду
Х1,...,Хm1, Xm1+1,…, Xm1+m2,…, Xm1+…+mn-1+1,…, Xm1+…+mn, (1.2)
де
|X1| = … = |Xm1| = 1; |Xm1+1| = … = |Xm1+m2| =
(1.3)
=2;…;|Xm1+…+mn-1+1| = … = |Xm1+…+mn| = n.
При цьому об'єднання попарно пересічних множин розбиття, що утворюється таким чином, вигляду (1.2), (1.3) для всіх невпорядкованих розбиттів, які розглядаються, дає сукупність усіх розбиттів вигляду (1.2), (1.3), а отже, за правилом суми, використовуючи твердження 1, маємо
___n!______ = Σm1!…mn! = N(m1,…,mn)m1!…mn! (де підсумовування
(1!)ⁿ1…(n!)ⁿk
проводиться за всіма невпорядкованими розбиттями,що розглядаються), звідки випливає правильність твердження 3.
Поліномна формула.
Визначимо коефіцієнти функції (х1+...хк)ⁿ = Σ cn1,…,nk x1ⁿ1…xkⁿk, яку
n1+…nk=n
вище було названо поліно мною, де підсумовування проводиться за всіма розв’язками рівняння n1 + …nk = n у цілих невід’ємних числах.
Твердження 4. Справджується рівність cn1,…,nk=Cnⁿ1···ⁿk = _____n!___.
n1!…nk!
Уведемо позначення співмножників виразу (х1+ х2 +...+хк)ⁿ. Позначимо аі = (х1 + х2 +... +хк), і = 1,2,...,n. Тоді {х1 + х2 + ...+хк}ⁿ. Нехай А = {a1, a2,…,an}. Перерахуємо всі одночлени після перемноження а1 а2...аn, в яких х1 зустрічається n1 разів х2- n2 разів,...,хк-nк разів, тобто одночлени вигляду
х1ⁿ1...хкⁿк, (1.4)
де n1+…+nk = n.
Розглянемо будь-який з таких одночленів. Для кожного і({1,2,...k} позначимо через Аі таку підмножину множини А, що в цей одночлен увійдуть змінні хі з тих і тільки тих співмножників, які перераховано в Аі. Цим самим одночлену поставлено у відповідність розбиття множини А на підмножини А1,...,Ак такі, що
k
(Аі( = ni, i = 1,…,k, U Ai = A, Ai∩Aj = Ø при i≠j. (1.5)
i=1
Очевидно, зазначена відповідність між одночленами (1.4) і розбиттями (1.5) є взаємно однозначною. Проте тоді кількість одночленів вигляду (1.4) становить
Cn1,…,nk = Cnⁿ1’···’ⁿk =
Формула включень і виключень.
Нехай Х1, Х2 – дві скінченні множини. Якщо Х1∩Х2 = (, то(Х1 (Х2(= (Х1(+(Х2(. Нехай тепер Х1(Х2 ((. Тоді в (Х1(+ (Х2( кожний елемент з Х1(Х2 буде врахований двічі, що треба виправити.
Тому
(Х1(Х2(= (Х1(+(Х2(((Х1(Х2(, (1.6)
тобто кількість елементів в обєднанні множин виражено через кількість елементів у їх перерізі. Маємо відповідну формулу для довільного числа множин, яка називається формулою включень і виключень.
Твердження 5. Нехай Хі – скінченні множини,і = 1,2,...,n, n(2. Тоді
(Х1(...(Хn(= ((X1(+…+(Xn() – ((X1(X2(+(X1(X3(+…+
+(Xn-1( Xn() +((X1(X2( X3(+…+(Xn-2(Xn-1(Xn() +…+(-1)ⁿ+¹ (
((X1(…(Xn(. (1.7)
Доведення проведемо методом індукції за n. При n = 2 формула (1.7) збігається з (1.7). припустимо, що формула, яка доводиться, є правильною для випадку n-1 підмножин, де n(3. доведемо її правильність для n підмножин. Розіб’ємо множини Х1,...,Хn на на дві групи: Х1,..., Хn-1; Xn. Тоді згідно з (1.6) маємо:
(Х1(...(Хn(= ((X1(…(Xn-1)(Xn( = (X1(…(Xn-1(+ (Xn(-
(1.8)
-((X1(…(Xn-1)(Xn(= (X1(…(Xn-1(+(Xn(-(A1(…(An-1(,
де Аі = Хі(Хn, і = 1,...,n-1.
Використовуючи індуктивне припущення, знаходимо:
(Х1(…(Xn-1(= ((X1(+…+(Xn-1() – ((X1(X2(+…+(Xn-2(n-1() +
+((X1(X2(X3(+…+(Xn-3(Xn-2(Xn-1() - …+(-1)ⁿ(X1(…(Xn-1(;
(A1(…(An-1(=((A1(+…+(An-1() - ((A1(A2(+(A1(A3(+…
+(An-2(An-1()+…+(-1)ⁿ(A1(…(An-1(=((X1(Xn(+…+(Xn-1(Xn() –
((X1(X2(Xn(+(X1(X3(Xn(+…+(Xn-2(Xn-1(Xn()+…+(-1)ⁿ(
((X1(…(Xn(.
Із (1.8), ураховуючи останні рівності, дістаємо (1.7).
Наслідок 1. Нехай Х – скінченна множина, Х1,...,Хn – підмножини Х. Тоді
(Х – (Х1(...(Хn)(=(X(- ((X1(+…+(Xn() + ((X1(X2(+…+
+(Xn-1(Xn() -…+(-1)ⁿ(X1(…(Xn(. (1.9)
Справді,
(Х – (Х1(...(Хn)( ( (X1(…(Xn) = X;
(X – (X1(…(Xn)(((X1(…(Xn) = (,
звідки
(X – (X1(…(Xn)(+(X1(…(Xn(=(X(,
а, отже
(X – (X1(…(Xn)(=(X(-(X1(…(Xn(. (1.10)
Для здобуття (1.9) залишається тільки у (1.10) застосувати формулу (1.7).
Наведемо ще одну (найпоширенішу) форму запису формули включень і виключень. Нехай Х – скінченна множина, що складається з N елементів; (1,...,(n; - деякі властивості (одномісні предикати,
визначені на Х), які можуть мати або не мати елементи з Х. Позначимо через ( і ({1,2,…,n}Хі = {х(Х((і (х)} множину елементів в Х, що мають властивість (і. Позначимо також через N ( (i1,…,(ik) = (Xi1(…(Xik(= ({x(X((i1 (x)(…( (ik (x)}(кількість елементів в Х, які мають одночасно властивості (і1,..., (ік( N0 = (Х – (Х1(...(Хn(- кількість елементів в Х, що не мають жодної з властивостей (1,..., (n. Тоді за формулою (1.9) дістанемо:
N0 = N – S1 + S2 - …+ (-1)ⁿ Sn,
де (1.11)
Sk = ∑ N((i1,…,(ik), k = 1,2,…,n.
1≤i1<…<ik≤n
Приклад 1. Нехай n=3, тобто задано три властивості (1, (2, (3. Тоді за формулою (1.11):
N0 = N – N((1) – N((2) – N((3) + N((1, (2) +
(1.12)
+ N((1, (3) + N((2, (3) – N((1, (2, (3).
Приклад 2. Застосовуючи формулу включень і виключень, задачу визначення кількості цілочислових розв’язків системи
x1 + x2 +… +xn = r, ai≤xi≤bi, i =1,2,…,n, (1.13)
де аi, bi, r – цілі числа; ai≤ bi, i = 1,2,…,n, легко звести до сукупності задач визначення кількості цілочислових розв’язків систем вигляду:
x1 + x2 +…+xn = r, xi≥ai, i= 1,2,…,n, (1.14)
де n≥1, аі – цілі числа.
Для цього слід скористатися властивостями (і(х): “хі(bi + 1”, де х= (х1,...,хn), i =1,2,…,n, а за початкову множину Х узяти сукупність цілочислових розв’язків х системи (1.14). Тоді N0, що визначається за формулою (1.11), і виражатиме кількість цілочислових розв’язків системи (1.13).
Розв’язування задач на розбиття.
Задача 1. У студентській групі, яка складається з 25 осіб, при виборі старости за висунену кандидатуру проголосували 12 чоловік, проти – 10, утрималися – 3. Скількома способами могло бути проведене таке голосування?
Розв’язування. Нехай Х – множина студентів у групі; Х2 – множина студентів, які проголосували проти; Х3 – множина студентів, які утрималися від голосування. Тоді (Х(= 25,(Х1(= 12,(Х2(= 10,(Х3(= 3, Х = Х1(Х2(Х3, Хі(Хj =( при i(j, а отже, шукане число дорівнює С25¹²·¹º·³. Використовуючи твердження 1, знаходимо
С25¹²·¹º·³ = 1 487 285 800.
Задача 2. Скількома способами можна розфарбувати квадрат, поділений на дев'ять частин.(рис.1), чотирма кольорами таким чином, щоб у перший колір були забарвлені 3 частини, у другий – 2, у третій – 3, у четвертий – 1?
1
2
3
4
5
6
7
8
9
Розв’язування. Нехай Х – множина кольорів, де |Х| = =4. Тоді кожне розфарбування, що розглядається як послідовність кольорів, в які забарвлюються пронумеровані частини квадрата, є перестановкою 9 елементів зі специфікацією. При цьому нас цікавлять
Рис. 1
перестановки із заданою комбінацією елементів (3 елементи – перший колір, 2 – другий, 3 – третій, 1 – четвертий). Проте тоді, використовуючи твердження 2, дістаємо, що шукане число
С9³·²·³·¹ =
Задача 3. Скількома способами з групи в 25 чоловік можна сформувати 5 коаліцій по 5 чоловік?
Розв’язування. Нехай Х – множина людей у групі, mi – число
коаліцій по і чоловік, де і = 1,2,...,25. Тоді за умовою задачі |Х| = 25, m5 = 5. mi = 0, i({1,2,…,25}\{5}, а отже, шукане число дорівнюватиме N (0,0,0,0,5,0,...,0), де завдяки твердженню 3
N(0,0,0,0,5,0,…,0) = = ===.
Задача 4. Скількома способами можна задати відношення еквівалентності на множині Х= {1,2,...,25} із трьома класами еквівалентності?
Розв’язування. Використовуючи той факт, що множина класів еквівалентності є розбиттям множини Х дістаємо , що шукане число визначається за формулою:
Σ N(m1,…,m25) = Σ
m1+2m2 +…+25m25 = 25 m1+2m2+…+25m25 = 25
m1+m2+…+m25 = 3 m1+m2+…+m25 = 3
де m1 + 2m2 +…+25m25 = 25, m1 + m2 + …+m25 = 3 – множина всіх розв’язків цієї системи рівнянь у цілих невід'ємних числах (наприклад, m1 = 1. m12 = 2, mi = 0, i ≠ 1, i ≠12 – один із таких розв'язків).
Застосування формули включень і виключень
для розв’язування задач.
Задача 1. Нехай Х = { 0,1,...,10}; (1(х): ”х – парне”; (2(х): “х(6”; (3(х): “2(х(8”. Підрахувати кількість N0 елементів в Х, що не мають властивостей (1, (2, (3.
Розв’язування. Використовуючи формулу (1.12), знаходимо N0 = 11 – 6 – 4 – 5 + 2 + 2 + 1 – 0 =1 (неважко бачити, що єдиним елементом в Х, який не має властивостей (1, (2, (3, є число 1).
Задача 2. Визначити кількість тризначних чисел, в яких сума цифр дорівнює 20.
Розв’язування. Якщо через х1, х2, х3 позначити відповідно першу, другу та третю цифри в довільному тризначному числі а = х1( 10² + х2· 10 + х3, то для розв’язання задачі досить визначити кількість цілочислових розв’язків системи
х1 + х2 + х3 = 20, 1≤х1≤9, 0≤х2≤9, 0≤х3≤9. (1.15)
Нехай Х – цілочислових розв’язків х = (х1, х2, х3) системи
х1 + х2 + х3 = 20, х1≥1, х2≥0, х3≥0;
N – кількість елементів в Х. Уведемо такі три властивості:
(1(х): “х1(10”; (2(х): “х2(10”; (3(х): “х3(10”.
Використовуючи формулу включень і виключень (1.12) для підрахунку кількості цілочислових розв’язків системи вигляду (1.14), визначимо кількість N0 цілочислових розв’язків системи (1.15):
N0 = F (3, 20 – 1) – F (3, 20 – 10) – F(3, 20 – 10 – 1) – F(3, 20 – 10 – 1) +
+
+ F(3, 20 – 10 – 10) + F(3, 20 – 10 –10) + 0 – 0 = 210 – 66 – 110 + 2 = 36.
Задача 3. (Задача про безладдя). Задано n різних предметів а1, а2,…,аn та n різних кліток b1,b2,…,bn. Скількома способами можна розмістити предмети по клітках так, щоб жоден предмет аі не потрапив у клітку bi?
Розв’язування.Як початкову множину Х візьмемо сукупність всіляких розміщень предметів по клітках. Тоді N = (X( = n!. Уведемо властивості а1: “аі знаходиться в клітці bi”, і = 1,2,...,n. Число N((i1,…,(ik) розміщень, при якому предмет аіv знаходиться в клітці biv, v = 1,…,ki, дорівнює (n - - k)!. Однак тоді
Sk = ( N((i1,…,(ik) = Ckⁿ(k - n)! =
1(i(…(ik (n
Використовуючи формулу включень і виключень (1.11), знаходимо, що кількість N0 розміщень, при якому жодна з властивостей не виконується (тобто жоден із предметів аі не потрапив у клітку bi), становить
n k n k n k
N +∑ (-1) Sk = n! + ∑ (-1) +=== n! ∑ (-1) .
k=1 k=1 k=0
Висновки.
В даній курсовій роботі, я розглянула основні поняття і властивості формул включень і виключень та розбиття, проаналізувала основні приклади й означення. Розглянула різні типи задач та їх розв’язування. Я переконалася, що розв’язування задач в комбінаториці є набагато простішим при використанні даних формул і зводиться до простих обчислень.
Список використаних літературних джерел.
1. Міхайленко В.М., Федоренко Н.Д., Демченко В.В.
Дискретна математика: Підручник. – К., Вид-во Європ.
ун-ту, 2003. – 319с. – Бібліогр.: с. 318.
2. Бардачов Ю. М. та ін.
Дискретна математика: Підручник / Ю. М. Бардачов, Н. А.
Соколова, В. Є. Ходаков; За ред. В. Є. Ходакові. К.: Вища шк.., 2002. 287 с.: іл..
Такий граф, в якому вершинам відповідають кроки, а ребрам переходи між ними, називається схемою алгоритму. Його вершини можуть бути двох типів: вершини, з яких виходить одне ребро(їх називають операторами), і вершини, з яких виходять два ребра(їх називають логічними умовами, або предикатами). Крім того, існують єдиний оператор кінця, з якого не виходить жодного ребра, та єдиний оператор початку. Важливою особливістю схеми є те, що зв’язки, які вона описує, не залежать від того, чи є кроки елементарними або самостійними алгоритмами, як кажуть у програмуванні, блоками. Можливість розблокувати алгоритм добре відома у програмуванні й вона там широко використовується: великий алгоритм поділяється на блоки, які можна роздати для програмування різним особам. Для певного блока неважливо, яку будову мають інші блоки; для програмування блока досить знати, де знаходиться вся початкова інформація, яка форма її подання, що має робити блок і куди записати результат.
Схеми не містять відомостей ні про дані, ні про пам’ять, ні про набір елементарних кроків, який використовується. Зокрема треба мати на увазі, що коли в схемі не має циклів, це не означає, що немає циклів в алгоритмі(вони можуть бути в якому-небуть неелементарному блоці).
По суті схеми це не мова, а засіб, хоча дуже зручний для однієї мети опису детермінізму алгоритму. Корисно ввести одне уточнення: умови, тобто точки розгалуження, можуть бути не тільки двозначними, а й багатозначними; важливо, щоб правильною була лише одна з можливих відповідей(наприклад, оператор CASE в Паскалі).
Виявляється, що будь-який логічний алгоритм можна досить простими методами звести до числового. Тому теорію числових алгоритмів можна вважати універсальним апаратом для дослідження всіх алгоритмічних проблем.
Алгоритмічні моделі, що розглядаються в цьому розділі, претендують на право вважатися формалізацією поняття “алгоритм”.
Це означає, що вони мають бути універсальними, тобто допускати опис будь-яких алгоритмів. Тому може виникнути природне заперечення підходу, який пропонується: чи не приведе вибір конкретних засобів до втрати загальності формалізації? Якщо мати на увазі основну мету при створені теорії алгоритмів універсальність і пов’язану з нею можливість говорити в межах якої-небудь моделі про властивості алгоритмів узагалі, то ця суперечність знімається так
По-перше, доводиться звідність одних моделей до інших, тобто показується, що кожний алгоритм, описаний засобом однієї моделі, може бути описаний засобами іншої. По-друге, завдяки взаємній звідності моделей в теорії алгоритмів удалося виробити інваріантну відносно моделей систему понять, що дає змогу говорити про властивості алгоритмів незалежно від того, яку формалізацію алгоритму вибрано. Ця система понять ґрунтується на понятті обчислювальної функції, тобто функції, для обчислення якої існує алгоритм.
Однак хоча загальність формалізації у конкретній моделі не втрачається, різний вибір початкових засобів приводить до моделей різного типу. Можна виділити три основних типи універсальних алгоритмічних моделей, які різняться початковими евристичними міркуваннями щодо того, що таке алгоритм. Перший тип зв’язує поняття алгоритму з найтрадиційнішими поняттями математики обчисленнями та числовими функціями. Найбільш розвинена й вивчена модель цього типу рекурсивні функції є історично першою формалізацією поняття алгоритму. Другий тип грунтується на уявлені про алгоритм як про деякий детермінований пристрій, здатний виконувати в кожний окремий момент лише дуже примітивні операції. Таке уявлення не залишає сумнівів в однозначності алгоритму й елементарності його кроків. Крім того, евристика цих моделей близька до ЕОМ, а отже, до інженерної індустрії. Основною теоретичною моделлю цього типу є машина Тюрінга.
Робота машини відбувається в дискретному часі. На кожному кроці кареткою(за різними джерелами головкою або пристроєм звернення до стрічки) розглядається єдина комірка, а символ , який зчитується, замінюється іншим (i=j означає, що символ не змінюється) залежно від стану машини у заданий тактовий момент із множини її можливих станів. Крім того, виробляється наступний стан машини, і команда, яка керує переміщенням по стрічці, підготовлює чергову комірку для розгляду на наступному кроці. Таких команд у МТ три: R розглядати сусідню праворуч комірку;
L розглядати сусідню ліворуч комірку та E продовжувати розглядати колишню комірку. Очевидно, що є істотним, чи рухається
каретка вздовж стрічки, чи каретка є нерухомою, а рухається кожного разу на один крок саме стрічка
Нехай МТ може знаходитися тільки у скінченому числі різних
.
внутрішніх станів і в будь-який момент часу чергова операція є функцією поточного внутрішнього стану машини та скінченого виразу, зафіксованого на стрічці. Відповідно до наведеного вище означення, можна формально визначити МТ в такий спосіб:
Q (t+1)=(Q(t), A(t)) ; R(t+1)=(Q(t), A(t)) ;
D(t+1)=(Q(t) , A(t)),
Де , , деякі функції, що пов’язують попередній стан і попередній вихідний(який розглядається) символ. Функція визначає зміну стану, а функціявихідне значення записує в комірку, що розглядається: операція запису може містити вилучення символу, який знаходився раніше в комірці. Функція просто повідомляє, куди саме рухається стрічка.
Описувана машина є скінченною, але її можна вважати актуально нескінченною у тому розумінні, що після досягнення будь-якого кінця стрічки завжди може бути додана нова комірка. При цьому, звичайно, у будь-який конкретний момент часу довжина стрічки залишається скінченою.
Формальний математичний опис МТ дано у працях А. М. Тюрінга, Е. Л. Поста, С. К. Клині [7], Дейвіса, Арбиба [11] та М. Мін
ського [4]. Використовувані в цих працях різні системи позначень еквівалентні одна одній.
Повний стан машини, за яким однозначно можна визначити її подальшу поведінку, визначається внутрішнім станом машини, станом стрічки(тобто словом, записаним на ній) та положенням каретки на стрічці. Перед початком роботи на стрічку наносять початкове слово і задають початкові умови, тобто зазначать першу комірку, яка розглядається, та початковий стан. Після пуску машини процес перетворення інформації відбувається автоматично.
Постає питання про функції, для яких існує МТ, що їх обчислює. Щодо МТ можна сказати, що ця функція визначається поведінкою машини. Аргумент з’являється на стрічці до початку обчислення, а значення функції для цього аргументу те, яке залишається на стрічці, коли обчислення закінчено. Скористуємось спеціальним командуванням натуральних чисел в алфавіті, що складається з одного символу одиниці: кожне натуральне число n подається (n +1) символом 1, тобто числа 0, 1, 2,....кодуємо словами 1, 11, 111,... .
Універсальна машина Тюрінга
Суттєвий факт, який було доведено за допомогою МТ, це те, що існує така МТ, яка за певними початковими значеннями обчислює будь-яку задану функцію, що є обчислюваною за Тюрінгом. Як зазначено вище, систему команд для МТ можна інтерпретувати також як опис роботи конкретного механізму і як програму, тобто сукупність розпоряджень, які однозначно приводять до результату. Розбираючи приклади, читач мимоволі вибирає другу інтерпретацію, виступаючи в ролі механізму, який здатний відтворити роботу будь-якої МТ.
Упевненість у тому, що користувачі все це будуть робити однаково(якщо не нароблять помилок, що, до речі, передбачається при роботі МТ), це, по суті, упевненість в існуванні алгоритму відтворення роботи МТ за заданою програмою, тобто системою команд. Справді, словесний опис такого алгоритму дати не важко.
Як уже зазначалося у питанні основні означення, словесний опис алгоритму може бути неточним і потребувати формалізації. Оскільки як такою формалізацією поняття алгоритму розглядається МТ, природно поставити задачу побудови такої МТ, яка реалізує описаний алгоритм відтворення. Для МТ, що обчислює функцію однієї змінної, формулювання цієї задачі таке: побудувати МТ U, яка обчислює функцію двох змінних, причому U ( , a)= T(a) для якої-небуть машини Т із системою команд , якщо Т(а) визначено(тобто машина U(,а
20.06.2013 02:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора