Az algoritmus matematikai fogalma - Formalis rendszerek. Markov-féle normal algoritmus. Turing gép. Turing-gépek megallasi problémaja. Algoritmikusan eldönthetetlen problémak. Algoritmus bonyolultsaga

Az algoritmus matematikai fogalma
Formális rendszerek. Markov-féle normál algoritmus. Turing gép. Turing-gépek megállási problémája. Algoritmikusan eldönthetetlen problémák. Algoritmus bonyolultsága

Algoritmus:elöre megtervezett elemi lépések olyan sorozata,amely véges, teljes, egyértelmü és determinisztikus. Véges számú lépésben, véges idö alatt erednyényt szolgáltat (véges). Nem egyedi probléma megoldására készül, hanem azonos jellegü feladatok megoldására (teljes). Adott problémaosztályból akárhogy választok ki egy konkrét problémát az algoritmus mindegyikre müködik (egyértelmü). Ugyanazon induló adatokkal az algoritmus ugyanazt az eredményt szolgáltatja (determinisztikus).
Az algoritmus megadási módjai:
- élöbeszéd: elmondom hogy néz ki az algoritmus ( hosszú, nem elég precíz)
- formalizált élöbeszéd vagy mondatszerü leírás: az algoritmust lépésenként adom meg, a lépéseket sorszámozom, a lépéseken belül minimális formalizmust alkalma zok pl. ha .. akkor (egyértelmüek a lépések)
- folyamatábrán: (Neumann alkalmazta) algoritmus képi, ábrázolása síkban. ( a prob léma, hogy normális méretü feladatoknál áttekinthetetlen)
- metenyelvi leírás: jól definiált formalizmus van, ami szavakkal és egyéb szimbólu mokkal dolgozik
- adott program, ami leírja az algoritmust
- absztrakt matematikai eszközökkel: pl. Turing-gép
Alapfogalmak

Szimbólumoknak nevezett elemek véges, nem üres halmazát ábécének nevezzük. Legyen V egy ábécé. A V ábécé szimbólumaiból alkotott véges sorozatokat - beleértve az üres sorozatot is - a V ábécé fölötti szövegeknek (röviden szövegeknek) nevezzük. A V ábécé fölötti összes szövegek halmazát V*-gal jelöljük. Szokás a szimbólumot betünek, a szöveget szónak, mondatnak, sztringnek is nevezni. Az üres szöveget l-val jelöljük.

Szövegek közötti müvelet: az x x₁ x_m és y y₁ y_n szövegek konkatenációjának vagy összekapcsolásának nevezzük és multiplikatíve jelöljük az   x y x₁ x_my₁ y_n szöveget. A szorzásjelet rendszerint elha­gyjuk. A konkatenáció asszociatív müvelet, azaz x y z x y z így a zárójelek el is hagyhatók. l a müvelet egységeleme. V* a konkatenáció müveletével egy egységelemes félcsoportot alkot, melyet V-feletti szabad monoidnak nevezzük.

A szöveg hosszának nevezzük a szöveget alkotó szimbólumsorozat elemeinek a számát. Az   x szöveg hosszát x -vel jelöljük.   l xy x y . Az n hosszúságú szövegeket n-gramoknak nevezzük (n esetén render monogram, digram, trigram az elnevezés). V beágyazható V*-ba ún. természetes módon, azaz V minden elemének kölcsönösen egyértelmüen megfeleltethetö az ebböl a szimbólumból álló monogram.

Azt mondjuk, hogy az y szöveg része az x-nek, ha léteznek olyan u,v V* szövegek, hogy x uyv. Az x szöveg n hosszúságú részszövegeit az x n-gramjainak nevezzük

Legyen V₁ és V₂ két tetszöleges, nem feltétlenül különbözö ábécé. A V₁*-ot V₂*-ra képezö függvényeket szövegfüggvényeknek nevezzük. Egy f V₁* V₂* szövegfüggvény müvelettartó (vagy homomorfizmus), ha f xy = f x f y minden x,y V₁* esetén. Az f szövegfüggvény hossztartó, ha f x x minden x V₁* szöveg esetén. Az f szövegfüggvény kezdöszelet-tartó, ha f xy = f x z minden x,y V₁* esetén valamilyen z V₂*-re.

V*-ot önmagára leképezö függvények a fej, törzs és szövegtükrözö szövegfüggvények: definíció szerint fej x l, ha x=l, egyébként fej x = x elsö monogramja. A törzs x definíció szerint az a szöveg, amelyre az x= fej x törzs x egyenlöség teljesül. A tükörkép x az a szöveg, amelynek szimbólumai fordított sorrendben rendre egyenlöek x szimbólumaival. A fej és törzs függvények kezdöszelettartóak, a tükörkép szöveg­függvény hossztartó.

Két szöveg távolságának nevezzük azon elemi szövegmüveletek minimális számát, amelyek alkalmazásával az egyik szövegböl a másikat megkapjuk. Elemi szövegmüveleteken általában azon szövegkorrekciókat étünk, amelyek a jellegzetes gépelési hibák kijavítására szolgálnak. Ezek:

egy szimbólum beszúrása egy adott helyre

egy adott helyen lévö szimbólum törlése

egy adott helyen lévö szimbólum másikra való kicserélése

egy adott helyen lévö két szomszédos szimbólum felcserélése.

Elemi szövegmüveleteknek szokás tekinteni csak az elsö kettöt, az elsö hármat vagy mind a négyet. Így háromféle szövegtávolság-fogalomhoz juthatunk. Ezek mindegyike rendelkezik a szokásos távolságtulajdonságokkal, azaz d x,y -vel jelölve az x és y szöve­gek távolságát:

d x,y

d x,y pontosan akkor, ha x y,

d x,y d y,x

d x,z d x,y d y,z (háromszög-egyenlötlenség)

minden x, y, z V*-ra

Legyen V egy ábécé. A V* részhalmazait V feletti nyelveknek, röviden nyelvek­nek nevezzük. Nyelvek között az alábbi müveleteket definiáljuk:

összeadás:             A B A B   (halmazunió),

szorzás:                 A B (algebrai szorzás),

hatványozás:         A⁰ , és Aⁿ A^{n -1} A, ha n >

pozitív lezárás:     A A¹ A² A³

teljes lezárás:        A* A⁰ A¹ A²

Az összeadás kommutatív és asszociatív, a zéruselem az üres halmaz mint nyelv (neve: üres nyelv). A szorzás asszociatív, az egységelem a nyelv. A két müvelet együtt disztributív. Az A nyelv teljes lezártja pontosan azoknak a szövegeknek a halmaza, azaz nyelve, amelyek az A tetszöleges számú - akár 0 - elemének a konkatenációjával elöállít­ható. V-nek mint a monogramok nyelvének a teljes lezártja, V* egyenlö lesz a V feletti szövegek teljes halmazával, V*-gal, így a két egybeesö jelölés ugyanazt a fogalmat jelöli. Végesnek nevezünk egy nyelvet, ha elemeinek a száma véges. A fenti müveletek közül az összeadást, a szorzást és a teljes lezárást reguláris müveleteknek nevezzük. Regulárisnak nevezünk egy nyelvet, ha az véges, vagy véges nyelvekböl véges számú reguláris müve­lettel elöállítható.

Reguláris kifejezések

Legyen V egy tetszöleges ábécé. Ekkor azt mondjuk, hogy

a V-böl alkotott reguláris kifejezés, és az üres nyelvet jelöli,

l szintén V-böl alkotott reguláris kifejezés, és a nyelvet jelöli,

tetszöleges a V szimbólumra a reguláris kifejezés, amely az nyelvet jelöli.

ha p és q V-böl alkotott reguláris kifejezések, amelyek a P, ill. a Q nyelveket jelölik, akkor p q pq és p szintén V-böl alkotott reguláris kifejezések, és az általuk jelölt nyelvek rendre P+Q, PQ, ill. P*,

csak azt a kifejezést nevezzük reguláris kifejezésnek, ami az elöbbi szabályok véges sokszori alklamazásával hozható létre.

Ez utóbbi ellenére megengedjük a zárójelek szokásos elhagyását, azaz a müveletek között precedenciát definiálunk: a legmagasabb rendü müvelet a *, a legalacsonyabb a +, és két müvelet végrehajtásának a sorrendjét zárójelek híján ez a precedencia szabja meg.

Formális rendszerek

Formális rendszer: Az F V,H kettest formális rendszernek nevezzük, ahol

V egy ábécé,

H V* V* ún. helyettesítési szabályok véges halmaza.

H tekinthetö egy V* feletti binér relációnak is: az x,y H jele x y, és azt mondjuk, hogy az x szöveg helyettesíthetö az y-nal. x-et nevezzük a helyettesítési szabály bal oldalának, y-t a jobb oldalnak. Azt mondjuk, hogy x-böl közvetlenül levezethetö y, ha x egy részletét egy helyettesítési szabály szerint helyettesítve y-t kapunk, azaz léteznek olyan u, v, w, z szövegek, hogy x uvw, y uzw és v z. A közvetlen levezethetöség jele:

Azt mondjuk, hogy x-böl y legalább egy lépésben levezethetö, ha van szövegeknek olyan x₀, x₁, , x_n sorozata (n>0), hogy x x , y x_n, és minden i ,n-re x_i-1 x_i teljesül. Jele x y. x-böl y több lépesben levezethetö, ha x y, vagy x y. Ennek jele x y

Szóproblémának nevezik azt a kérdést, hogy egy adott F formális rendszerben egy adott x V* szövegböl vajon levezethetö-e egy adott y V* szöveg, vagy sem. A szóprobléma algoritmikusan nem eldönthetö probléma.

Néhány speciális típusú formális rendszer

Generatív rendszer: a formális rendszer felhasználása nyelvek generálására. A W= V,Ax,H) hármast generatív rendszernek nevezzük, ahol

V egy ábécé,

Ax V* ún. axiómák véges halmaza,

H V* V* ún. helyettesítési szabályok véges halmaza.

W-hez hozzárendelünk egy V fölötti L_W nyelvet, az ún. W által generált nyelvet:

L_W

Természetesen Ax L_W teljesül minden W generatív rendszerben. Sajnos a generatív rendszer kifejezö ereje általában nem elégséges. Már az olyan egyszerü nyelvet, mint az L  x tükörkép x nyelvet sem lehet megadni generatív rendszerrel. Szükség lenne ún. segédszimbólumokra, amelyek a levezetések közbülsö lépéseiben vannak jelen, az utolsó helyettesítéssel minden segédszimbólum eltünik a szövegböl, de csak ebben az utolsó lépesben válik a szöveg segédszimbólumoktól mentessé. Így jutunk el a generatív nyelvtan fogalmához.

Chomsky-féle generatív nyelvtan: A G= V_N , V_T , S, H) négyest generatív nyelvtannak nevezzük, ahol

V_N az ún. nemterminális szimbólumok ábécéje,

V_T az ún. terminális szimbólumok ábécéje, V_N és V_T diszjunkt halmazok,

S V_N ún. kezdö szimbólum,

H V* V_T V* ún. helyettesítési szabályok véges halmaza, ahol V   V_N   V_T .

G-hez hozzárendelünk egy V_T fölötti L_G nyelvet, az ún. G nyelvtan által generált nyelvet:

L_G

Itt V_N játssza a segéd ábécé szerepét, S pedig egymagában mint egy monogram az axiómák szerepét. Azt a szövegsorozatot, amelynek elsö eleme S, utolsó eleme x, és a második elemtöl kezdve minden elem az elözöböl közvetlenül levezethetö, az x leveze­tésének nevezzük. Azzal, hogy a bal oldal nem állhat csupa terminálisokból, elértük, hogy az x-levezetésében x-et kivéve a levezetés minden eleme tartalmaz legalább egy nemter­minális szimbólumot. Az S-böl levezethetö szövegeket mondatformának, azt a mondat­formát, amely csak terminális szimbólumokból áll, mondatnak nevezzük. Az, hogy egy V_T* -beli szöveg mondat-e, levezetés keresésével dönthetö el. Ez az ún. szintaktikai elemzés feladata. Két nyelvtant ekvivalensnek mondunk, ha az általuk generált nyelvek megegyeznek.

Markov-algoritmus

A formális rendszer algoritmusként is alkalmazható, olyan algoritmusként, amely adott bemenö szöveghez valamilyen eredmény szöveget állít elö: a bemenö szöveget kezdeti szövegnek tekintve egymás után helyettesítéseket végzünk egészen addig, amíg el nem akadunk, azaz már nincs mit helyettesíteni. Egy ilyen algoritmus lépései nem egyértelmüek, nem egyértelmü az algoritmus következö lépése, ha több helyettesítési szabályt is alkalmazhatunk, de akkor sem, ha egy szabály bal oldala többször elöfordul az alakuló szövegben. Ennek érdekében teljes rendezést vezetünk be a szabályok halmazán, és mindig csak az elsö alkalmazható szabállyal végzünk helyettesítést, és mindig csak a bal oldal elsö elöfordulása helyettesíthetö. Ilyen típusú algoritmussal azonban már egy olyan egyszerü feladatot sem lehet megoldani, hogy egy csupa a-kból álló bemenö szöveget eggyel hosszabbítsunk meg, az algoritmus ugyanis ahogy elvégezte ezt a feladatot, rögtön kezdi újból a már meghosszabbított szövegen, nem tudja befejezni a müködést. Lehetövé kell még tenni azt is, hogy ne csak akkor fejezödhessen be a helyettesítések sora, ha már nincs mit helyettesíteni, hanem ebböl a célból kitüntetett ún. záróhelyettesítések végrehajtása után is. Az M V,H,H₁ hármast Markov-féle normál algoritmusnak nevezzük, ahol

V egy ábécé,

H V* V* ún. helyettesítési szabályok véges, rendezett halmaza.

H₁ H ún. záróhelyettesítési szabályok halmaza.

Az x,y H₁ záróhejettesítést x y-nal jelöljük.

. Azt mondjuk, hogy M alapján x-böl közvetlenül levezethetö y, ha léteznek olyan u, v, w, z szövegek, hogy x uvw, y uzw, v z, ez utóbbi az elsö olyan szabály, amelynek bal oldala része x-nek, és ha x svt valamilyen s- és t-re, akkor u része s-nek. A közvetlen levezethetöség jele: . A közvetlen levezetést záró közvetlen levezetésnek nevezzük, ha benne a helyettesítés záróhelyettesítés. Azt mondjuk, hogy M alapján x-böl y legalább egy lépésben levezethetö, ha van szövegeknek olyan x₀, x₁, , x_n sorozata (n>0), hogy x x , y x_n, és minden i ,n-re x_i-1 x_i teljesül. Jele x y. Azt mondjuk, hogy M alapján x-böl y levezethetö, ha x y, vagy x y. Ennek jele x y. A definícióból közvetlenül adódik, hogy ha x-böl y levezethetö, akkor a levezetése egyértelmü. Azt mondjuk, hogy az M Markov-algoritmus az x bemenö szöveghez az y eredményt állítja elö, ha M alapján x-böl y levezethetö, és

- a levezetésben szereplö közvetlen levezetések egyike sem záró közvetlen levezetés és y a szabályok bal oldalainak egyikét sem tartalmazza, vagy

- a levezetésben szereplö közvetlen levezetések egyike sem záró közvetlen levezetés, kivéve az utolsót, amely záró közvetlen levezetés.

Turing-gép

Turing-gép:egy végtelen szalagmemóriával és egy író-olvasó fejjel ellátott véges automata. Kezdetben a Turing-gép egy specifikált kezdöállapotban van és a szalagon egy véges hosszúságú startszó helyezkedik el. Feltesszük, hogy a statrszó nem tartalmaz üres szimbólumokat. Müködésének kezdetekor a Turing-gép író-olzasó feje a startszó elsö jelén áll ( illetve üres startszó esetén az író-olvasó fej alatt az üres szimbólum áll). A Turing-gép egy operációja az író-olvasó fej alatti szimbólum olvasásából, ezen jel felülírásából, belsö állapot változtatásából és a fej négyzettel (azaz egy szimbólumpozicióval) balra, jobbra mozgatásából, avagy a fej helybenmaradásábóláll. Amennyiben a Turing-gép elér egy végállapotot, megáll.
M = ( x, J, A, a₀, A_F, m)
x a szalagábécé
d x üres jel (mely nem azonos a szalagábécé üres szavával)
A a gép belsö állapotainak a halmaza
a₀ A a gép kezdöállapota
A_F A a gép végállapotainak halmaza
m: ( A- A_F) x X 2^AxXx mozgásfüggvény   (B:bal; J:jobb; H:helyben)
Ha M az a A-A_F állapotában van és x X az író-olvasó fej alatti jel, akkor m (a, x) szolgáltatja a gép operáció utáni új állapotát, a mozgás irányát, a szalagjelet felülíró új szimbólumot.
A Turing-gép megállási problémája: Nincs olyan algoritmus, amely tetszöleges Turing-gépröl és inputból eldöntené, hogy megáll-e erre az inputra. Nincs olyan algoritmus, mely tetszöleges M Turing-gép leírását és input szavának kódolt (W) alakját inputként megkapva eldönti, hogy ( M) megáll-e a tekintett Turing-gép erre az inputra.

Algoritmikusan eldönthetetlen problémák

Ezek a problémák a Turing-gép megállási problémájára vezethetök vissza.
P L(G) probléma az általános 0-típusú grammatikák esetében eldönthetetlen. Tetszöleges P szóról és tetszöleges 0-típusú G grammatikáról véges sok lépésben nem lehet eldönteni, hogy P L(G) teljesül-e.
Algoritmikusan eldönthetetlen, hogy egy 1-típusú nyelv üres-e.

Algoritmikusan eldönthetetlen, hogy egy 1-típusú nyelv végtelen-e.

Algoritmus bonyolultsága

Egy véges sok elemböl álló matematikai konstrukciönak, például egy formális grammatikának vagy egy véges automatának a bonyolultságát mérhetjük a benne szereplö alkotórészek (például a helyettesítési szabályok vagy állapotok) számával. Egy Turing-gép bonyolultságát is mérhetjük az utasításainak számával. Ebböl nem tudhatjuk meg, hogy milyen gyorsan dolgozik, mennyi memóriát használ. Szükség van olyan méröszámokra, amelyekkel a végrehajtási idöt és a felhasznált memóriaterületet a bemenö adatok függvényében tudjuk kifejezni. A Turing-gép vonatkozásában a végrehajtási idöt a lépésszámmal, a felhasznált memóriaterületet a szalagon felhasznált mezöknek a számával azonosítjuk.
Egy Turing-gépet t(n) idöbonyolultságúnak mondunk, ha minden legfeljebb n-hosszúságú bemenö szóra legfeljebb t(n) lépést hajt végre.Hasonlóképpen l(n) szalagbonyolultságúnak mondunk egy Turing-gépet, ha az minden legfeljebb n-hosszúságú bemenö szóra legfeljebb l(n) mezöt használ fel a szalagján.
Egy tetszöleges feladatot T(n) idöbonyolultságúnak nevezünk, ha van olyan t(n) idöbonyolultságú Turing-gép, amely ezt a feladatot megoldja, és t(n) T(n), hacsak n elég nagy. Hasonlóképpen egy tetszöleges feladatot L(n) szalagbonyolultságúnak nevezünk, ha van olyan l(n) szalagbonyolultságú Turing-gép, amely ezt a feladatot megoldja, és l(n) L(n), hacsak n elég nagy.