válaszokat algoritmusok
Az intuitív fogalma egy algoritmus. Tulajdonságok algoritmusok.
Az algoritmus egy határozott lépések sorozata megoldani egy adott problémát.
Az ilyen tulajdonságok a következők:
• Felbontás (diszkontinuitás külön-külön) - az algoritmus képviselje a folyamat a probléma megoldása, mint a következetes végrehajtása egyszerű (vagy korábban megadott) lépés. Minden tevékenység, feltéve, hogy az algoritmus végrehajtása csak a kivégzés után véget ért az előző.
• Bizonyosság - minden szabály algoritmus legyen világos, egyértelmű és nem hagy önkény. Köszönhetően az ingatlan az algoritmus mechanikus, és nem igényel semmilyen további utasításokat vagy információt a feladathoz.
• Hatékonyság (természetesen) - az algoritmus kell vezetnie a probléma megoldása véges számú lépésben.
• Helyi - megoldási algoritmus kidolgozása, általános jelleggel, hogy van, azt kell alkalmazni egy bizonyos osztály a problémák, csak abban különböznek az eredeti adatokat. Így az eredeti adatokat lehet kiválasztani a régió úgynevezett régió Az algoritmus alkalmazhatósága.
Hozzászólás gép. Leírás, célok, példák. A megfogalmazás l.
Adjon gép (MT) - elvont számítástechnikai gép, javasolt Emilem Leonom Post (született Emil Leon Post.), Amely eltér a Turing-gép nagyobb egyszerűség. Mindkét gép algoritmikusan „egyenértékű”, és az volt a célja, hogy tisztázza a „algoritmus”. 1936-ban, amerikai matematikus Emil Hozzászólás cikket írta le a rendszer algoritmikus egyszerűség és meg tudja állapítani, hogy ez vagy az a probléma algoritmikusan megoldható. Ha a feladat egy algoritmikus megoldás, akkor is képviselteti formájában parancsok sorozatának a Post gép.
Ezenkívül a két szám triviális - elég, hogy 1 közéjük, és törölje a két jobboldali „1” Q. A program áll, kivonva az egymást követő változások legbaloldalibb „1” a sorozat „1” a kép jobb és Q „1” a sorozat „1” a kép P. a kocsi elején a program telepítve az legbaloldalibb „1” Q:
2. Az 1., 3., - ha a cella üres, menjen az 1. lépésre, ha nem, a 3
3. 0 - távolítsa el a címkét
5. 4, 6 - ha a cella üres, folytassa a 4. lépéssel, ha nem, a 6
6. 0 - távolítsa el a címkét
8. 9, 1 - ha a cella üres, ugorjon a 9., ha nem, 1
Megjegyzendő, hogy az csapat számát nem határozták meg, ha az átalakulás zajlik a sorrendben következő sorban (az egyszerűség kedvéért a szöveg). A 6. sor hurok, ha Q> P.
Definíció Egy Turing-gép. Használata a Turing-gép a szavakat.
Turing-gép (MT) - abstraktny Szereplő (elméleti számítógép). Alan Turing ajánlottak 1936 hivatalossá fogalma algoritmus.
Turing-gép egy kiterjesztése egy véges automatát, és a szerint Church tézise - Turing. képes szimulálni előadók (azáltal átmeneti szabályok), bármilyen módon megvalósító számítási lépés eljárás, amelyben minden egyes lépés kellően elemi számítás.
Turing-gép egy külső ábécé A = kódot, amely a kazettára rögzített gép, és a belső állapotokat az ábécé Q =, ahol Q1 - kezdeti állapotban, q0 - végleges. A gép működését határozza meg a program (funkcionális blokkvázlat). A program áll parancsokat. Minden csapat T (i, j) (i = 1, 2, ..., m; J = 0, 1, ..., n) egy kifejezése az alábbi típusok:
Építése a Turing-gép. A kompozíciók a Turing-gépek.
3. példa Próbáljuk össze egy autó Tyurin-n, ahol n egységek egymás után, hogy hagyja a szalagon rögzített egység n-2, rögzített egy sorban, ha n> 2, és a munka örökre, ha n = 0, vagy n = 1. A külső kétrészes szett ábécé take-CIÓ a =. A számos szükséges belső állapotok fogják meghatározni a programozási folyamatot. Úgy gondoljuk, hogy a gép kezdődik a szabványos kezdeti polo zheniya, azaz amikor az állam Q1 megkérdezett szélsőjobboldali edi matematika IZP felvételre. Kezdjük azzal, hogy törli az elsőt, ha rendelkezésre áll, folytassa a következő Ferris elhagyta a cellát, és törli egységet, ha meg van írva a sejtben. Minden ilyen átmeneti gépet beköltözik egy új belső állapot, mert különben el fog veszni az összes egység rögzített egy sorban. Itt vannak a parancsok, az alábbi lépésekkel: q11 q20L; q21 q30L. A gép olyan állapotban van, q3 nyílik a harmadik a jobb a sejt. ahol a szó van írva (n egység). Megváltoztatása nélkül a tartalom vizsgált sejtben, az autó kell maradnia-novitsya, azaz megy a végső állapot q0, független-mo a sejt tartalmát. Az alábbi parancsokat: q30 q00; q31 Q01. Most már csak úgy a helyzetet, amikor kazettára történő felvétel-on csak egy egység vagy rögzített hang. Ha a szalagon rögzített egy légtérben található, az első lépés után (előadó Coma nem q11 q20L) gép lesz olyan állapotban a Q2 és tartsa be a jobb második cellában, amelyben rögzített 0. Vey-állapot, amely esetben a gép kell futtatni örökre . Ezt úgy lehet elérni, például a következő parancsot: q20 q20P teljesítő, hogy lépésről lépésre. a gép mozog a len-e korlátlan joga (vagy stretching szalag fölött kiolvasott vezető feje jobbról balra). Végül, ha a szalag nem rögzített minden egység a gép, azzal a feltétellel, és azok Rabo tolvaj örökre. Ebben az esetben a kiindulási állapotban q1 vizsgált cella tartalmát 0, és az örök munka a gép el van látva a következő parancsot: q10 q10P.
Kiszámítható Turing funkciót. Megfelelő funkciót kiszámíthatóság a Turing-gép.
Turing tézis (fő hipotézise az algoritmusok elmélete). Turing-gép és a modern számítógépek.
Turing tézis: Class függvények algoritmikusan kiszámítható tekintetében semmilyen funkciót (vagy funkciók az osztály), az osztály a részleges funkciók tekintetében rekurzív része (rendre, viszonyítva a rendszer).
Turing tézis következik Church tézisét.
Eredete rekurzív függvények.
(Végétől recursio - visszatérő)
A név rendelni az egyik leggyakoribb változatai általános koncepcióját a számtani algoritmus finomítás, azaz ilyen algoritmus, érvényes bemeneti adatok, amelyek képviselik a rendszer természetes számok és az esetleges eredmények felhasználása természetes számok. Rekurzív függvények kerültek be az 30-es években. 20. Kleene. viszont alapul Gödel kutatás. Herbrand J. és munkatársai. Matematikusok.
Minden rekurzív függvény meghatározza a végső egyenletrendszert pontosan az a fajta, azzal jellemezve, abban az értelemben, hogy annak értékei alkalmazásával számítjuk ki ezt a rendszert az egyenletrendszert pontos formálás szabályok, sőt, úgy, hogy végül a értékek kiszámítására egy előzetesen meghatározott függvény a rekurzív algoritmus egy adott típusú kapunk.
Rekurzív függvények parciális függvények, azaz a. E. funkciók, nem feltétlenül mindenhol definiált. Ennek hangsúlyozása valójában, gyakran szinonimájaként használják a „részleges rekurzív függvények.” Rekurzív függvények meghatározott minden érték az érvek, az úgynevezett rekurzív függvények.
Alapfogalmak az elmélet rekurzív függvények és az egyház tézisét.
Church tézisét. algoritmikusan osztály (vagy gépi) kiszámítható részleges numerikus funkciók azonosak az osztály részleges rekurzív függvények. Más szóval, a számítási funkció, kiszámítható az általános értelemben vett, a lényege egy rekurzív függvény. Volt.
részleges számítási funkció, kiszámítható az általános értelemben azokat a részleges rekurzív függvény. Ez nem egy szigorú definíciót, kiírjuk a szintet a dolgozat (nem bizonyított, de nem cáfolta)
primitív rekurzív függvények - rekurzív függvények nyert eredeti funkcióit eredményeként véges számú kérelem puszta szuperpozíció szereplők és primitív rekurzió. Ők alkotják a saját részét az osztály általános rekurzív függvények. A jól ismert tétel Kleene normál forma rekurzív függvény említhetjük ilyen specifikus rekurzív primitív függvények egy változó U és Tn n + 2 változó, hogy minden rekurzív függvény φ OTN változók és bármely egész szám X 1. xn egyenlőség φ (x 1 xn) ≅ U (y), gdeu a legkisebb száma Z olyan, hogy T n (φ x 1. xn, z.) = 0 (ahol φ jelentése az úgynevezett Godel számú funkciót φ .. - olyan szám, amely hatékonyan szerkesztjük az egyenletrendszert meghatározó funkció φ). E tételből, különösen azt jelenti, hogy egy rekurzív függvény n változók lehet kialakítani egyetemes rekurzív függvény a változók n +1, t. E. A rekurzív funktsiyaF n, hogy minden egyes, a rekurzív függvény φ n változók és bármely természetes szám x 1 x n tart feltételes egyenlőség
Nézzük rámutatnak számos jól ismert számítási műveleteket primitív rekurzív.
A funkció hozzáadásának két egész szám () lehet tekinteni, mint egy primitív rekurzív függvény a két változó, amelyek alkalmazásával kapott primitív rekurzió mıveleteihez és. amelyek közül a második kapunk helyettesítjük az alapvető funkciókat az alapvető funkció S:
Computability Turing primitív rekurzív függvények.
Ackermann függvény - egy egyszerű példát mindenütt meghatározott számolható függvény. ami nem primitív rekurzív. Ez úgy két nem negatív egész paraméterként és visszatér egy egész. jelezték. Ez a funkció nagyon gyorsan fejlődő, például száma olyan nagy, hogy a számjegyek száma a jogot ez a szám meghaladja a atomok száma a megfigyelhető univerzumban.
minimálisra csökken a kezelési Legyen f (x1, ... .xn). Tartozik a részinformációval aritmetikai funkciók (ChAF). Tegyük fel, hogy van valamilyen mechanizmus annak kiszámításához, a függvény értéke nincs meghatározva pontosan akkor, ha ez a mechanizmus működik a végtelenségig anélkül, hogy bármilyen határozott eredményt. Mi fix semmilyen értéke x1. xn-1 az első n-1 érvek az f függvény, és megvizsgálja az egyenlet: f (. x1 xn-1, y) = xn g y (természetes szám) Ez az egyenlet alapján kerül meghatározásra a fent említett „mechanizmus” egymás után érték f ( x1. xn-1, y) az y = 0,1,2. A legkisebb érték egy, amelyre a turn f (x1. Xn-1, a) = xn. jelöli μy (f (x1 xn-1, y) = xn.) A leírt eljárás megtalálása μy expresszió (f (x1 xn-1, y) = xn.) továbbra is a végtelenségig az alábbi esetekben:
Minden ilyen esetben, a értéke μy expressziós (f (x1. Xn-1, y) = xn) nem definiált. Ellenkező esetben, a folyamat befejeződik leírt, és megadja a legkisebb egyenlet megoldása y = a f (x1. Xn-1, y) = xn .. Ez a megoldás, mint az említett, majd vyrazheniyaμy értéket (f (x1. Xn-1, y) = xn). Például, a különbség f (x, y) = xy összhangban az említett értelemben szimbólum μ, minden x, y, van: f (x, y) = xy = μz (y + z = x) értékek kiszámítása során az f függvény ( x, y) = xy ebben az esetben kerül sor, két forgatókönyvet.
Rekurzív része és egy rekurzív függvény.
Rekurzió módszer az úgynevezett referencia funkciót, amelyben a függvény meghatározott értékek tetszőleges argumentum értékek vannak kifejezve ismert módon keresztül függvény értékei definiálja a kisebb értékek a érveket. Tekintsük a egyenletet f (x) = g (x), ahol f (x) és g (x) bizonyos funkciókat. Amikor azt mondjuk, hogy ez az egyenlet egyenlet, az azt jelenti, hogy az egyenlet kezelik határozatlan mondat, néhány x értéke igaz, más hamis. Definíció. A funkció általános rekurzív, ha úgy értelmezzük, egy sor egyenletek egy bizonyos típusú.
Definíció. Egy részleges f függvény egy részlegesen rekurzív, ha lehet beszerezni egyszerű funkciókat O, S, UMN véges műveletek száma a szubsztitúció, primitív rekurzió és minimalizálása. Meghatározása az említett fő közvetlenül következő tulajdonságok relatív rekurzív függvények.
Minden részleges funkcióval, viszonylag primitív rekurzív rendszer funkcióit σ, és egy részlegesen rekurzív otnositeno σ. Különösen az összes primitív rekurzív függvények parciális rekurzív.
Az osztály részleges rekurzív függvények szélesebb, mint az osztály primitív rekurzív függvények, hiszen az összes primitív rekurzív függvények meghatározása mindenhol, és azok között a részleges rekurzív függvények és funkciók nem mindenhol megtalálhatók meghatározott, például sehol nem definiált függvény
szubsztitúciók műveletek, primitív rekurzió és minimalizálási előállított funkciók, részleges rekurzív képest σ rendszer, eredményezhet egy funkciót, ismét részleges rekurzív képest vizeletmintákban a ö.
Definíció. Részleges arifmiticheskaya f függvény egy részlegesen rekurzív, ha lehet beszerezni egyszerű funkciókat O, S, Umnkonechnym műveletek száma a szubsztitúció, primitív rekurzió iminimizatsii.