online kép - Fájl  tube fájl feltöltés file feltöltés - adja hozzá a fájlokat online fedezze fel a legújabb online dokumentumok Kapcsolat
   
 

Letöltheto dokumentumok, programok, törvények, tervezetek, javaslatok, egyéb hasznos információk, receptek - Fájl kiterjesztések - fajltube.com

 

Online dokumentumok - kep
   

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

matematika

Fájl küldése e-mail Esszé Projekt

egyéb tételek

 
Relaciós algebra, relaciós teljesség
Konverzió A Szamrendszerek Között
Pénzügyi szamítasok
Vektorok. Szakaszok a koordinatasíkon
Hatvanyozas
Minimum követelmények matematikaból
A szamok rezgései
LINEÁRIS ALGEBRA
Halmazok
 
 


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=x1Ľxm és y=y1Ľyn szövegek konkatenációjának vagy összekapcsolásának nevezzük és multiplikatíve jelöljük az   x*y=x1Ľxmy1Ľyn   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|=0,   |xy|=|x|+|y|. Az n hosszúságú szövegeket n-gramoknak nevezzük (n=1, 2, 3 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 V1 és V2 két tetszöleges, nem feltétlenül különbözö ábécé. A V1*-ot V2*-ra képezö függvényeket szövegfüggvényeknek nevezzük. Egy f :V1*®V2* szövegfüggvény  müvelettartó (vagy homomorfizmus), ha f(xy)= f(x)f(y) minden x,yÎV1* esetén. Az f szövegfüggvény hossztartó, ha |f(x)|=|x| minden xÎV1* szöveg esetén. Az f szövegfüggvény kezdöszelet-tartó, ha f(xy)= f(x)z minden x,yÎV1* esetén valamilyen zÎV2*-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) ł 0,

-      d(x,y) = 0 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:         A0  =  ,  és  An = An -1 * A,  ha  n > 0,

-      pozitív lezárás:     A+ = A1 + A2 + A3 + Ľ

-      teljes lezárás:        A* = A0 + A1 + A2 + Ľ

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 x0, x1,Ľ, xn sorozata (n>0), hogy x=x0, y=xn, és minden i=1,Ľ,n-re xi-1Ţxi 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 LW nyelvet, az ún. W által generált nyelvet:

LW =.

Természetesen  Ax Ě LW  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 = * |  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=(VN , VT , S, H) négyest generatív nyelvtannak nevezzük, ahol

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

-      VT  az ún. terminális szimbólumok ábécéje, VN  és VT  diszjunkt halmazok,

-      S Î VN  ún. kezdö szimbólum,

-      H Ě (V* - VT *) ´ V*  ún. helyettesítési szabályok véges halmaza, ahol = VN  Č VT .

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

LG =.

Itt VN  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 VT* -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,H1) 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.

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

Az (x,y)ÎH1 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 x0, x1,Ľ, xn sorozata (n>0), hogy x=x0, y=xn, és minden i=1,Ľ,n-re xi-1Ţxi 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, a0, AF, 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
            a0
Ď A a gép kezdöállapota
            AF
Í A a gép végállapotainak halmaza
           
m: ( A- AF) x X ® 2AxXx mozgásfüggvény   (B:bal; J:jobb; H:helyben)
Ha M az a
Î A-AF á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.

Találat: 1299