SZÖVETSÉGI OKTATÁSI ÜGYNÖKSÉG ÁLLAMI SZAKMAI FELSŐOKTATÁSI INTÉZMÉNY "VORONEZI ÁLLAMI EGYETEM" T.K. Katsaran, L.N. Stroeva TURING GÉP ÉS REKURSÍV FUNKCIÓK Tankönyv egyetemek számára Voronyezsi Állami Egyetem Kiadói és Nyomdai Központja 2008 Jóváhagyta a PMM karának Tudományos és Módszertani Tanácsa 2008. május 25-én, 9. számú jegyzőkönyv Lektor A műszaki tudományok doktora, Prof. Műveletekkutatási Matematikai Módszerek Tanszék T.M. Ledeneva A tankönyv a Voronyezsi Állami Egyetem Mechanikai Matematikai Karának Nemlineáris Oszcillációk Tanszékén készült. A VSU Alkalmazott Matematika és Matematika Karának, a VSU Starooskolsky és Liskinsky ágának 1. éves hallgatóinak ajánlott. A 010500 szakterülethez – Alkalmazott matematika és számítástechnika BEVEZETÉS Az „algoritmus” szó az algoritmus szóból ered – a 8–9. században (783–850) élt üzbég matematikus és csillagász, Muhammad ben Musa al- nevének latin írásmódja. Khwarizmi. Khorezm (a mai Üzbegisztán városa) legnagyobb matematikusát ezen a néven ismerték a középkori Európában. „Az indiai számolásról” című könyvében megfogalmazta a természetes számok arab számokkal történő írásának szabályait és a velük való művelet szabályait. Aztán az algoritmus fogalmát tágabb értelemben kezdték használni, és nem csak a matematikában. Mind a matematikusok, mind a gyakorló szakemberek számára fontos az algoritmus fogalma. Így azt mondhatjuk, hogy az algoritmus egy precíz előírás egy bizonyos műveleti rendszer meghatározott sorrendben történő végrehajtására az összes azonos típusú probléma megoldására, meghatározva egy olyan műveletsort, amely biztosítja a kívánt eredmény elérését a kiindulási adatokból. Vegye figyelembe, hogy ez nem az „algoritmus” fogalom meghatározása, hanem csak leírása, intuitív jelentése. Az algoritmus megtervezhető úgy, hogy akár egy személy, akár egy automatikus eszköz hajtsa végre. Ez az algoritmus gondolata matematikai szempontból nem szigorú, mivel olyan fogalmakat használ, mint a „pontos utasítások” és a „kezdeti adatok”, amelyek általában nincsenek szigorúan meghatározva. Bármely algoritmus jellemzője, hogy képes megoldani egy bizonyos osztályú problémákat. Ez lehet például egy algoritmus lineáris egyenletrendszerek megoldására, a legrövidebb út megtalálására egy gráfban stb. Egy algoritmus létrehozása, még a legegyszerűbb is, kreatív folyamat. Kizárólag élőlények számára elérhető, és sokáig azt hitték, hogy csak az emberek számára. Egy másik dolog egy létező algoritmus megvalósítása. Olyan alanyra, tárgyra lehet rábízni, aki nem köteles a dolog lényegében elmélyülni, esetleg nem is képes megérteni. Az ilyen alanyt vagy tárgyat általában formális előadónak nevezik. A formális teljesítményre példa az automata mosógép, amely szigorúan elvégzi a neki előírt műveleteket, még akkor is, ha elfelejtetted beletenni a port. Az ember formális előadóként is felléphet, de mindenekelőtt a különféle automata eszközök, köztük a számítógép is formális előadók. Minden algoritmus egy nagyon konkrét előadót szem előtt tartva jön létre. Azokat a tevékenységeket, amelyeket az előadó végrehajthat, megengedett cselekedeteinek nevezzük. A megengedett műveletek halmaza végrehajtói parancsok rendszerét alkotja. Az algoritmusnak csak azokat a műveleteket kell tartalmaznia, amelyek egy adott előadó számára megengedettek. Ezért az algoritmusok több általános tulajdonságát általában úgy fogalmazzák meg, hogy megkülönböztessék az algoritmusokat a többi utasítástól. Az algoritmusnak a következő tulajdonságokkal kell rendelkeznie. Diszkrétség (szakadás, elkülönültség) – az algoritmusnak a probléma megoldásának folyamatát egyszerű (vagy korábban meghatározott) lépések egymás utáni végrehajtásaként kell ábrázolnia. Az algoritmus által biztosított minden egyes művelet csak az előző végrehajtása után kerül végrehajtásra. Bizonyosság – az algoritmus minden szabályának világosnak, egyértelműnek kell lennie, és nem hagyhat teret az önkényességnek. Ennek a tulajdonságnak köszönhetően az algoritmus végrehajtása mechanikus jellegű, és nem igényel további utasításokat vagy információkat a megoldandó problémáról. Hatékonyság (végesség) – az algoritmusnak véges számú lépésben kell a probléma megoldásához vezetnie. 4 Masszívitás - a probléma megoldására szolgáló algoritmust általános formában fejlesztették ki, azaz alkalmazhatónak kell lennie egy bizonyos problémaosztályra, amelyek csak a kezdeti adatokban különböznek egymástól. Ebben az esetben a kiindulási adatokat egy bizonyos területről lehet kiválasztani, amelyet az algoritmus alkalmazhatósági területének nevezünk. Az algoritmuselmélet a matematikának egy olyan ága, amely az algoritmusok általános tulajdonságait vizsgálja. Az algoritmusoknak vannak kvalitatív és metrikus elméletei. Az algoritmusok kvalitatív elméletének fő problémája egy meghatározott tulajdonságokkal rendelkező algoritmus felépítésének problémája. Ezt a problémát algoritmikus problémának nevezzük. Az algoritmusok metrikus elmélete az algoritmusokat komplexitásuk szempontjából vizsgálja. Az algoritmuselméletnek ezt az ágát algoritmikus komplexitáselméletnek is nevezik. Egyes problémák megoldásának keresése során sokáig tartott a megfelelő algoritmus megtalálása. Példák az ilyen problémákra: a) jelöljön meg egy módszert, amely szerint bármely predikátumképletre véges számú műveletben megtudhatja, hogy az azonosan igaz-e vagy sem; b) a Diofantusz egyenlet (egy egész együtthatós algebrai egyenlet) egész számokban megoldható? Mivel ezeknek a problémáknak a megoldására nem lehetett algoritmust találni, felmerült az a feltételezés, hogy ilyen algoritmusok egyáltalán nem léteznek, ami bebizonyosodott: az első feladatot A. Church, a másodikat Yu.V. Matiyasevics és G.V. Csudnovszkij. Ezt elvileg lehetetlen egy algoritmus intuitív koncepciójával bizonyítani. Ezért megkísérelték megadni az algoritmus fogalmának pontos matematikai definícióját. A huszadik század harmincas éveinek közepén S.K. Kleene, A.A. Markov, E. Post, A. Turing, A. Church és mások különféle matematikai definíciókat 5 javasoltak az algoritmus fogalmára. Ezt követően bebizonyosodott, hogy ezek a különböző formális matematikai definíciók bizonyos értelemben egyenértékűek: ugyanazt a függvényhalmazt számítják ki. Ez azt sugallja, hogy az algoritmus intuitív koncepciójának fő jellemzőit helyesen rögzítik ezek a definíciók. Ezután megvizsgáljuk az A. Turing által javasolt algoritmus matematikai finomítását, amelyet Turing-gépnek nevezünk. 6 1. TURING GÉP § 1. A Turing-gép matematikai modellje A Turing-gép létrehozásának ötlete, amelyet A. Turing angol matematikus javasolt a 20. század harmincas éveiben, azzal a kísérlettel függ össze, hogy egy az algoritmus fogalmának pontos matematikai meghatározása. A Turing-gép (MT) egy idealizált digitális számítógép matematikai modellje. A Turing-gép ugyanaz a matematikai objektum, mint függvény, derivált, integrál, csoport stb. Csakúgy, mint más matematikai fogalmak, a Turing-gép fogalma is az objektív valóságot tükrözi, és bizonyos valós folyamatokat modellez. Az MT algoritmus leírásához kényelmes elképzelni egy eszközt, amely négy részből áll: szalagból, olvasófejből, vezérlőeszközből és belső memóriából. 1. Feltételezzük, hogy a szalag potenciálisan végtelen, cellákra van osztva (egyenlő cellák). Ha szükséges, egy üres cellát csatolunk az első vagy az utolsó cellához, amelyben a szimbólumok találhatók. A gép időben működik, amely diszkrétnek számít, és pillanatai 1, 2, 3, … számmal vannak jelölve. A szalag bármely pillanatban véges számú cellát tartalmaz. Csak egy szimbólum (betű) a külső ábécéből A = (L, a1 , a 2 ,..., a n -1 ), n ³ 2 írható a cellákba diszkrét időpontban. Az üres cellát az L szimbólum jelöli, magát az L szimbólumot pedig üresnek, míg a többi szimbólumot nem üresnek. Ebben az A ábécében az MT-hez eljuttatott információ egy szó (a szimbólumok véges rendezett halmaza) formájában van kódolva. A gép „feldolgozza” a szó formájában bemutatott információkat új szóvá. 2. Az olvasófej (egy bizonyos olvasóelem) úgy mozog a szalag mentén, hogy minden pillanatban pontosan a szalag egy celláját nézze. A fej képes beolvasni egy cella tartalmát, és az A ábécéből új karaktert írhat bele. Egy műveleti ciklusban csak egy cellát tud mozgatni jobbra (R), balra (L) vagy a helyén maradni (N). ). Jelöljük a fej mozgásainak (eltolódásainak) halmazát D = (P, L, N). Ha egy adott pillanatban t a fej a legkülső cellában van, és a hiányzó cellába kerül, akkor egy új üres cella kerül hozzáadásra, amely felett a fej a t + 1 pillanatban lesz. 3. A gép belső memóriája a Q = ( q0 , q1 , q 2 , ..., q m ), m ³ 1 belső állapotok bizonyos véges halmaza. Feltételezzük, hogy a |Q | hatvány ³ 2. A gép két állapota különleges jelentéssel bír: q1 a kezdeti belső állapot (több kezdeti belső állapot lehet), q0 a végállapot vagy a stop állapot (mindig egy végállapot van). Az MT-t minden pillanatban a fej helyzete és a belső állapot jellemzi. Például a cella alatt, amely felett a fej található, megjelenik a gép belső állapota. ¯ a2 a1 L a2 a3 q1 4. A vezérlőkészülék minden t pillanatban az éppen olvasott szalagon lévő szimbólumtól és a gép belső állapotától függően a következő műveleteket hajtja végre: 1) megváltoztatja az ai read szimbólumot. pillanatnyilag t egy új szimbólumra a j (különösen változatlanul hagyja, azaz ai = a j); 2) a fejét a következő irányok egyikébe mozgatja: N, L, R; 3) megváltoztatja a 8 qi gép t pillanatban meglévő belső állapotát egy új q j-re, amelyben a gép t +1 időpontban lesz (lehet, hogy qi = q j). A vezérlőeszköz ilyen műveleteit parancsnak nevezzük, amely a következő formában írható fel: qi ai ® a j D q j , (1) ahol qi a gép pillanatnyi belső állapota; a i – az éppen olvasott szimbólum; a j – a szimbólum, amelyre az a i szimbólum megváltozik (lehet ai = a j); a D szimbólum vagy N, vagy L, vagy P, és a fej mozgási irányát jelzi; q j a gép belső állapota a következő pillanatban (talán qi = q j). A qi ai és a j D q j kifejezéseket ennek a parancsnak a bal és jobb oldalának nevezzük. Azon parancsok száma, amelyekben a bal oldalak páronként elkülönülnek, véges szám, mivel a Q \ (q 0 ) és A halmazok végesek. Nincsenek azonos baloldali parancsok, azaz ha a T gépi program a qi ai ® a j D q j és qt at ® ak D qk kifejezéseket tartalmazza, akkor qi ¹ qt vagy ai ¹ at és D O (P, L, N ). Az összes utasítás halmazát Turing-gép programnak nevezzük. Egy programban a parancsok maximális száma (n + 1) x m, ahol n + 1 = A és m + 1 = Q. Úgy gondolják, hogy a q0 parancs végállapota csak a parancs jobb oldalán, a q1 kezdeti állapot a parancs bal és jobb oldalán egyaránt megjelenhet. Egy parancs végrehajtását lépésnek nevezzük. A Turing-gép számítása (vagy művelete) egymást követő lépések sorozata, kihagyás nélkül, az elsőtől kezdve. Tehát MT adott, ha négy véges halmaz ismeretes: az A külső ábécé, a belső Q ábécé, a fejmozgások D halmaza és a gépi program, amely a parancsok véges halmaza. 9 2. § A Turing-gép működése A gép működését az első (kezdeti) pillanatban teljesen meghatározza a feladat: 1) szavak a szalagon, azaz a szalag celláiba írt szimbólumok sorozata (a szót úgy kapjuk meg, hogy ezeket a szimbólumokat a szalag cellái között balról jobbra olvassuk) ; 2) fejhelyzet; 3) a gép belső állapota. E három feltétel kombinációját (jelenleg) konfigurációnak (jelenleg) nevezzük. Jellemzően a kezdeti pillanatban a gép belső állapota q1, és a fej vagy a szalag első bal vagy első jobb cellája felett van. Egy adott szót a szalagon, amelynek kezdeti állapota q1 és a fej pozíciója az első szó felett van, kezdeti konfigurációnak nevezzük. Ellenkező esetben azt mondjuk, hogy a Turing-gép nem alkalmazható a kezdeti konfiguráció egy szóra sem. Más szóval, a kezdeti pillanatban a konfiguráció a következő formában ábrázolható: egy bizonyos számú cellából álló szalagon minden cellában az A külső ábécé egyik szimbóluma van írva, a fej az első felett helyezkedik el. a szalag bal vagy első jobb oldali cellája és a belső, a gép pozíciója q1. A parancs végrehajtásából eredő szót a szalagon és a fejpozíción végső konfigurációnak nevezzük. Például, ha a kezdeti pillanatban az a1La 2 a1a1 szót írják a szalagra, akkor a kezdeti konfiguráció így fog kinézni: a1 a2 L a1 a1 q1 (a cella alatt, amely felett a fej található, a gép belső állapota van feltüntetve). 10

A „Turing-gép” témakör egy iskolai informatika tanfolyamon

BAN BEN. Falina,
Moszkva

Számos számítástechnikai tankönyvben az algoritmus fogalmának és tulajdonságainak tanulmányozásakor a következő tartalmú kifejezések találhatók: „... sokféleképpen lehet ugyanazt az algoritmust megírni, például szöveg formájában írás, írás. folyamatábra formájában, valamilyen algoritmikus nyelven írva, algoritmus ábrázolása Turing-gép vagy postagép formájában...” Sajnos az ilyen típusú kifejezések az egyetlenek, amelyek Turing-gépet említenek. Kétségtelen, hogy az algoritmusok tanulmányozására fordított órák mennyisége nem teszi lehetővé, hogy ebbe a témakörbe belefoglaljuk az algoritmus Turing-gép formájában történő megírásának módjait is. De ez a téma rendkívül érdekes, fontos és hasznos az iskolások, különösen az informatika iránt érdeklődők számára.

A „Turing-gép” témakör a 8–11. évfolyamon az „Információs folyamatok” témakör részeként tanulható. Információfeldolgozás”, a szabadon választható órákon, a kiegészítő oktatás rendszerében, például a fiatal programozók iskoláiban. A téma tanulmányozását számítógépes támogatás kísérheti, ha a tanár rendelkezik egy „Turing-gép” szoftverszimulátorral. A haladó programozási órákon a tanulók önállóan tudnak Turing-gép programot írni. Ennek a cikknek a részeként egy workshopot ajánlunk Önnek a „Turing-gép” témában. A témával kapcsolatos elméleti anyag nem egyszer jelent meg az Informatikai újság oldalain, például a 3/2004. számban I.N. Falina „Az algoritmusok elméletének elemei”.

A Turing-gép szigorú matematikai konstrukció, matematikai apparátus (hasonlóan például a differenciálegyenletek berendezéséhez), amelyet bizonyos problémák megoldására hoztak létre. Ezt a matematikai berendezést azért nevezték „gépnek”, mert alkotóelemeinek leírását és működését tekintve hasonlít egy számítógéphez. A Turing-gép és a számítógépek közötti alapvető különbség az, hogy a tárolóeszköze egy végtelen szalag: a valódi számítógépekben a tárolóeszköz tetszőleges nagyságú lehet, de végesnek kell lennie. Egy Turing-gépet nem lehet pontosan megvalósítani, mert a szalagja végtelen. Ebben az értelemben minden számítástechnikai gépnél erősebb.

Minden Turing-gép két részből áll:

1)korlátlan körút szalag, sejtekre osztva;

2) gép(Szoftver által vezérelt olvasó/író fej).

Minden Turing-gép társítva van két utolsó ábécé: az A = (a 0, a 1, ..., a m) bemeneti szimbólumok ábécéje és a Q = (q 0, q 1, ..., q p) állapotok ábécéje. (A különböző Turing-gépekhez különböző ábécék rendelhetők AÉs K.) A q 0 állapotot hívjuk passzív. Úgy gondolják, hogy ha a gép ebbe az állapotba kerül, akkor befejezte a munkáját. A q 1 állapotot hívjuk a kezdeti. Ebben az állapotban a gép megkezdi a munkát.

A beviteli szó egyenként, egymást követő cellákban kerül a szalagra. A beviteli szótól balra és jobbra csak üres cellák vannak (az ábécében A mindig tartalmaz egy üres betűt A A 0 azt jelzi, hogy a cella üres).

A gép a szalagon balra vagy jobbra mozoghat, elolvashatja a cellák tartalmát és betűket írhat a cellákba. Az alábbiakban egy Turing-gép sematikus rajza látható, amelynek automatája az első cellát vizsgálja adatokkal.

A gép minden alkalommal csak egy cellát „lát”. Attól függően, hogy melyik betű ai látja, és állapotától függően is qj A gép a következő műveleteket tudja végrehajtani:

• · írjon egy új betűt a megfigyelt cellába;
• · mozgassa a szalagot egy cellával jobbra/balra, vagy maradjon mozdulatlan;
• · új állapotba költözni.

Vagyis egy Turing-gépnek háromféle művelete van. Minden alkalommal a következő párért ( q j, a i) egy Turing-gép egy három műveletből álló parancsot hajt végre bizonyos paraméterekkel.

A Turing-gép program egy táblázat, amelynek minden cellába egy parancsot írnak.

Sejt ( q j, a i) két paraméter határozza meg - az ábécé szimbóluma és a gép állapota. A parancs jelzés: hova kell mozgatni az író/olvasó fejet, milyen karaktert kell írni az aktuális cellába, milyen állapotba kell mennie a gépnek. A gép mozgási irányának jelzésére a három betű egyikét használjuk: „L” (balra), „P” (jobbra) vagy „N” (álló).

Miután a gép végrehajtotta a következő parancsot, állapotba kerül q m(amely adott esetben egybeeshet az előző állapottal q j). A következő parancsot itt kell megtalálni m a táblázat . sora az oszloppal való metszéspontban a l(levél a l műszak után lát a gép).

Egyezzünk meg abban, hogy ha a szalag tartalmaz egy bemeneti szót, akkor a gép az állapot valamelyik cellájával szemben helyezkedik el q 1. Működés közben az automata a program (tábla) egyik cellájából a másikba ugrik, amíg el nem éri azt a cellát, amelyben az van írva, hogy az automatának az állapotba kell mennie. q 0 . Ezeket a sejteket ún állítsa le a sejteket. Bármely ilyen cellát elérve a Turing-gépet megáll.

Egyszerű felépítése ellenére a Turing-gép a szavak minden lehetséges transzformációját képes végrehajtani, ezáltal az összes lehetséges algoritmust megvalósítja.

Példa. Meg kell építeni egy Turing-gépet, amely hozzáad egyet a szalagon lévő számokhoz. A beviteli szó a szalagon lévő, egymást követő cellákba írt decimális egész számjegyekből áll. A kezdeti pillanatban a gép a szám jobb szélső számjegyével szemben található.

Megoldás. A gépnek hozzá kell adnia egyet a szám utolsó számjegyéhez. Ha az utolsó számjegy 9, akkor cserélje ki 0-ra, és adjon hozzá egyet az előző számjegyhez. Egy adott Turing-géphez tartozó program így nézhet ki:

Ebben a Turing-gépben q 1 számjegyű változás állapota, q 0 - stop állapot. Ha tudod q l a gép látja a 0..8 számot, majd lecseréli 1..9-re, és állapotba lép q 0, azaz megáll a kocsi. Ha látja a 9-es számot, akkor lecseréli 0-ra, balra mozog, és az állapotban marad q l. Ez addig folytatódik, amíg a gép 9-nél kisebb számmal nem találkozik. Ha az összes szám egyenlő 9-cel, akkor nullákkal helyettesíti őket, a legmagasabb számjegy helyére 0-t ír, balra lép és 1-et ír egy üres cellába. Aztán az államba kerül q 0, azaz meg fog állni.

Gyakorlati feladatok

1. A Turing-gép szalag „+” jelsorozatot tartalmaz. Írjon programot egy Turing-gépre, amely minden második „+” jelet „–”-ra cserél! A csere a sorozat jobb végétől kezdődik. A gép képes q 1 az egyik karaktert nézi a megadott sorrendben. Magán a táblaprogramon kívül írja le szavakkal, hogy mit hajt végre a gép az egyes állapotokban.

2. Adott egy szám n nyolcas számrendszerben. Tervezz meg egy Turing-gépet, amely egy adott számot növel n 1-nél. A gép képes q Az 1 a bemeneti szó egy bizonyos számjegyét nézi. Magán a táblaprogramon kívül írja le szavakkal, hogy mit hajt végre a gép az egyes állapotokban.

3. Adott egy természetes szám decimális jelölése n> 1. Készítsünk olyan Turing-gépet, amely egy adott számot csökkentene n 1-nél. A gép képes q Az 1 a szám jobb oldali számjegyét nézi. Magán a táblaprogramon kívül írja le szavakkal, hogy mit hajt végre a gép az egyes állapotokban.

4. Adott egy természetes szám n> 1. Készítsünk olyan Turing-gépet, amely egy adott számot csökkentene n 1-gyel, míg a kimeneti szó legjelentősebb számjegye nem lehet 0. Például, ha a bemeneti szó „100”, akkor a kimeneti szó „99” legyen, nem „099”. A gép képes q Az 1 a szám jobb oldali számjegyét nézi. Magán a táblaprogramon kívül írja le szavakkal, hogy mit hajt végre a gép az egyes állapotokban.

5. Adott egy sor nyitó és záró zárójel. Építsünk egy Turing-gépet, amely eltávolítja a kölcsönös zárójelpárokat, pl. a „()” sorban található.

Például a(z) „) (() (())” esetén a „) . . . (().

A gép képes q

6. Adott egy betűsor a"És" b" Fejlesszünk ki egy Turing-gépet, amely az összes betűt mozgatja. a"balra, és a "betűk" b” - a vonal jobb oldalára. A gép képes q 1 a sor bal szélső karakterét nézi. Magán a táblaprogramon kívül írja le szavakkal, hogy mit hajt végre a gép az egyes állapotokban.

7. A Turing-gép szalagon van egy decimális számrendszerben írt szám. Szorozzuk meg ezt a számot 2-vel. A gép képes q Az 1 a szám bal szélső számjegyét nézi. Magán a táblaprogramon kívül írja le szavakkal, hogy mit hajt végre a gép az egyes állapotokban.

8. Adott két természetes szám mÉs n, az unáris számrendszerben bemutatva. Az egyező karakterkészletek: „|” üres cellával elválasztva. A gép képes q Az 1 a bemeneti sorozat jobb szélső karakterét nézi. Fejlesszünk ki egy Turing-gépet, amely számok összegét hagyja a szalagon mÉs n. Magán a táblaprogramon kívül írja le szavakkal, hogy mit hajt végre a gép az egyes állapotokban.

9. Adott két természetes szám mÉs n, az unáris számrendszerben bemutatva. Az egyező karakterkészletek: „|” üres cellával elválasztva. A gép képes q Az 1 a bemeneti sorozat jobb szélső karakterét nézi. Fejlesszünk ki egy Turing-gépet, amely különbséget hagy a számok között a szalagon. mÉs n. Ismeretes, hogy m> n. Magán a táblaprogramon kívül írja le szavakkal, hogy mit hajt végre a gép az egyes állapotokban.

10. A Turing-gép szalagján van egy decimális szám. Határozza meg, hogy ez a szám osztható-e 5-tel maradék nélkül! Ha osztható, akkor a szám jobb oldalára írja az „igen” szót, ellenkező esetben a „nem” szót. A gép megvizsgálja a bemeneti szám egy bizonyos számjegyét. Magán a táblaprogramon kívül írja le szavakkal, hogy mit hajt végre a gép az egyes állapotokban.

Képes q 1 gép a szám jobb végét keresi, képes q 2 - kihagyja a „+” jelet, amikor eléri a sorozat végét – megáll. Képes q 3, a gép a „+” jelet „–” jelre cseréli, és amikor a sorozat végére ér, leáll.

A probléma megoldása hasonló a fent tárgyalt példához.

Állapot q 1 - a legalacsonyabb (következő) számjegyet csökkentjük 1-gyel. Ha nem egyenlő nullával, akkor a csökkentés után azonnal le kell állni, ha a legalacsonyabb számjegy 0, akkor helyette 9-et írunk, balra toljuk, és ismét végrehajtjuk a kivonást . Ketrecben [ a 0 , q 1 ] egy Turing-gép soha nem fog eltalálni, ezért kitöltetlenül hagyható.

4. feladat (a 3. feladat bonyolultsága)

Állapot q 1 - a mellék (következő) számjegyet csökkentjük 1-gyel. Ha nagyobb, mint 1, akkor a kicsinyítés után azonnal abbahagyjuk, de ha a kis számjegy 0, akkor helyette 9-et írunk, balra toljuk és végrehajtjuk a kivonást újra. Ha a csökkentendő számjegy 1, akkor helyette 0-t írunk, és az állapotba lépünk q 2 .

Állapot q 2 - a „0” tetszőleges pozícióba történő beírása után meg kell vizsgálni, hogy ez a nulla a legjelentősebb számjegy (azaz, hogy a kimeneti szórekordban tőle balra van-e a 0).

Állapot q 3 - ha a rögzített „0” a legjelentősebb számjegy, akkor azt el kell távolítani a kimeneti szórekordból.

Azok a cellák, amelyekbe a Turing-gép soha nem jut be, üresen maradnak.

Állapot q 1: ha "(") jelenik meg, váltson jobbra, és lépjen az állapotba q 2; ha találkoznál" a 0”, majd megáll.

Állapot q 2: a „(” szimbólum elemzése a párosításhoz, párosítás esetén „)”-t kell látniuk. Ha gőzfürdőről van szó, akkor térjen vissza balra, és menjen az állapotba q 3 .

Állapot q 3: először törölje a „(”, majd a „)” jelet, és lépjen tovább q 1 .

Ennek a problémának a megoldása általában nehézségeket okoz az iskolásoknak. A probléma megoldásának elemzésekor például a következő módon járhat el.

Tekintse át a következő bemeneti szavakat a tanulókkal, és kérje meg őket, hogy fogalmazzák meg, mit kell tennie egy Turing-gépnek, hogyan néz ki a kimeneti szó, és miben különböznek ezek a lehetőségek egy Turing-gép szempontjából:

aaa ->

a -> a kimeneti szó megegyezik a bemeneti szóval, végignézzük a bemeneti szót, amíg véget nem ér.

bbb -> a kimeneti szó megegyezik a bemeneti szóval, végignézzük a bemeneti szót, amíg véget nem ér.

b -> a kimeneti szó megegyezik a bemeneti szóval, végignézzük a bemeneti szót, amíg véget nem ér.

ab -> a kimeneti szó megegyezik a bemeneti szóval, végignézzük a bemeneti szót, amíg véget nem ér.

A megbeszélés eredménye. Egy Turing-gépnek „meg kell értenie”, hogy melyik betűláncot követi, ti. legalább két állapotúnak kell lennie. Legyen az állam q 1 - mozgás egy betűlánc mentén " a", A q 2 - mozgás állapota egy betűlánc mentén " b" Vegye figyelembe, hogy a lánc egy betűből is állhat. Ha az államban a sor végére értünk q 1 ill q 2, azaz találkozott a 0, a gépnek le kell állnia, a teljes sort feldolgoztuk.

Fontolja meg a következő lehetőségeket a beviteli szavakhoz:

bba -> abb

bbbaab -> aabbbb

aabbbaab -> aaaabbbb

A megbeszélés eredménye. A beviteli szó első változata szekvenciálisan a következőképpen feldolgozható: bba -> bbb-> vissza a levéllánc bal végére " b” -> abb(a lánc első betűjét cserélje ki erre: " a"). Ezen műveletek végrehajtásához két új állapotot kell bevezetnünk, és ezen felül tisztázni kell az állapotot q 2. Így a probléma megoldásához egy Turing-gépet kell készítenünk a következő állapotokkal:

q 1 - menjen jobbra a betűlánc mentén " a" Ha a lánc véget ér a 0, majd lépjen ide q 0 ; ha "betűvel" végződik b", akkor megyünk a q 2 ;

q 2 - menjen jobbra a betűlánc mentén " b” ha a lánc véget ér a 0, majd lépjen ide q 0 ; ha véget ér" a", majd cserélje ki a "betűt" a" tovább " b”, menjen az államhoz q 3 (a faj láncát a faj láncolata váltotta fel);

q 3 - menj balra a betűlánc mentén b” a bal végéhez. Ha találkoztál a 0 vagy " a", akkor megyünk a q 4 ;

q 4 - cserélje ki b" tovább " a” és menj ide q 1 (cserélje ki az űrlap láncát egy űrlap láncára.

7. probléma

állapot q 1 - egy szám jobb (legalacsonyabb) számjegyének keresése;

állapot q 2 - egy szám következő számjegyének megszorzása 2-vel anélkül, hogy 1 átvitelt adna hozzá;

állapot q 3 - egy szám következő számjegyének megszorzása 2-vel, 1 átvitel hozzáadásával.

A program Turing-gépe triviálisan egyszerűnek tűnik - csak egy állapota van. Egy ilyen Turing-gép a következő műveleteket hajtja végre: törli a jobb szélső vonást, keres egy elválasztót (üres cellát), és egy körvonalat helyez el ebbe az üres cellába, ezáltal folyamatos hosszúságú vonássorozatot alkot. n + m.

Azonban furcsa módon ennek a problémának a megoldása nagy nehézségeket okoz. Nagyon gyakran a diákok olyan Turing-gépet építenek, amely ciklikus műveleteket hajt végre: egymás után nyomják a jobb oldalt nütések balra.

Ebben az esetben a programjuk így néz ki:

állapot q 1 - elválasztó keresése;

állapot q 2 - mozgott a stroke;

állapot q 3 - ellenőrizze a végét (az összes ütést elmozdította-e).

A probléma példája jól mutatja, hogy a gyerekek milyen gyakran próbálnak megoldani egy problémát a már megszokott módon. Számomra úgy tűnik, hogy azáltal, hogy a diákoknak Turing-gépek készítésére vonatkozó feladatokat kínálunk, fejlesztjük a szokatlan megoldások megtalálásának képességét és fejlesztjük a kreatív gondolkodás képességét!

Ez a feladat meglehetősen könnyűnek tűnik az iskolások számára, de nehézségek merülnek fel a Turing-gép leállításával. Az alábbiakban a Turing-gép egyik lehetséges változata látható erre a feladatra.

Megoldási ötlet (stop feltétel). A szalagon két kezdeti körvonal található.

Elkezdjük törölni a körvonalakat a tömb bal végéről m. És egyenként töröljük a tömb bal szélső vonalát més a tömb jobb szélső vonala n. De mielőtt kitörölné a megfelelő körvonalat a tömbből n, ellenőrizzük, hogy ez az egyetlen (azaz az utolsó, amelyet törölni kell) vagy sem.

Először írjuk le a Turing-gép azon állapotait, amelyek a feladatunk megoldásához szükségesek, majd készítsünk egy táblaprogramot.

Állapot q 1 - elválasztó keresése a vonástömbök között jobbról balra haladva;

állapot q 2 - a bal oldali körvonal keresése a tömbben m;

állapot q 3 - a bal oldali körvonal eltávolítása a tömbből m;

állapot q 4 - elválasztó keresése balról jobbra haladva;

állapot q 5 - a megfelelő körvonal keresése a tömbben n;

állapot q 6 - ennek a körvonalnak az egyediségének ellenőrzése a tömbben n, azaz határozza meg, hogy ez volt-e az utolsó;

állapot q 7 - ha ez volt az utolsó, akkor álljon meg, ellenkező esetben lépjen egy új algoritmus-végrehajtási ciklusra.

A probléma megoldása során ügyeljen az ábécé helyes írására:

A = ( a 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, D, A, N, E, T).

Állapot q 1 - keresse meg a szám jobb végét;

állapot q 2 - a szám legkisebb jelentőségű számjegyének elemzése; ha egyenlő „0” vagy „5”, azaz. a szám osztható 5-tel, majd átmenet az állapotba q 3 , egyébként átmenet állapotba q 5 ;

állapot q 3 - írja be a „D” betűt a szó jobb oldalán a szalagon;

állapot q 4 - írja be az „A” betűt a szó jobb oldalán, és állítsa le a gépet;

állapot q 5 - az „N” betű írása a szó jobb oldalán;

állapot q 6 - az „E” betű írása a szó jobb oldalán;

állapot q 7 - írja be a „T” betűt a szó jobb oldalán, és állítsa le a gépet.

A Turing-gép, mint algoritmus tulajdonságai

A Turing-gépet példaként használva jól láthatóak az algoritmusok tulajdonságai. Kérje meg a tanulókat, mutassák meg, hogy egy Turing-gép rendelkezik egy algoritmus összes tulajdonságával.

Diszkrétség. Egy Turing gép tud menni ( k + 1) lépés csak a befejezés után Nak nek- lépés, mert pontosan Nak nek- lépés határozza meg, mi lesz ( k + 1) lépés.

Világosság. Minden lépésben az ábécéből egy szimbólumot írunk a cellába, az automata egy mozdulatot tesz (L, P, N), és a Turing-gép a leírt állapotok egyikébe lép.

Determinizmus. A Turing-gép táblázat minden cellája csak egy opciót tartalmaz egy művelethez. Minden lépésnél egyedileg meghatározott az eredmény, ezért a probléma megoldásának lépéssora egyedileg meghatározott, azaz. Ha egy Turing-gép ugyanazt a bemeneti szót kapja, akkor a kimeneti szó minden alkalommal ugyanaz lesz.

Termelékenység. Tartalmát tekintve az egyes lépések eredményei és a lépések teljes sorozata egyedileg definiált, ezért a helyesen megírt Turing-gép véges számú lépésben kerül az állapotba. q 0, azaz véges számú lépésben megkapjuk a választ a problémakérdésre.

Tömegjelleg. Minden Turing-gép az ábécé összes megengedett szója felett van definiálva, ez a tömegkarakter tulajdonsága. Minden Turing-gépet úgy terveztek, hogy egy osztályú feladatot oldjon meg, pl. Minden feladathoz meg van írva a saját (új) Turing-gépe.

A SZERKESZTŐTŐL

A cikkben szereplő összes probléma egyszerűen egy füzetben megoldható egy információs csík és egy táblázatos program rajzolásával. De ezt a folyamatot szórakoztatóbbá és vizuálisabbá teheti: használjon gépi megvalósítást - a Postagép értelmezőjét és az „Algo2000” Turing-gépet, amelyet Radik Zartdinov készített. A program intuitív felülettel rendelkezik, követelményei a legmérsékeltebbek: IBM PC AT 486 vagy újabb számítógép, Windows 95/98/NT operációs rendszer.

Nézzük meg általánosságban az „Algo2000” működését.

A program menüben válassza ki a kívánt elemet Tolmácsés jelezzük, hogy melyik géppel szeretnénk dolgozni (esetünkben ez egy „Turing-gép”).

Egy Turing-gépmező jelenik meg előttünk.

Most be kell állítani a külső ábécét, pl. Sorban Külső ábécé jelezze, hogy mely karakterek szerepelnek benne (ha a karakterlánc Külső ábécé nem látható, ki kell választani egy menüpontot Megtekintés | Külső ábécé). Minden karakter csak egyszer adható meg. A külső ábécé beírása után létrejön a táblázat első oszlopa: a külső ábécé karakterei ugyanabban a sorrendben töltődnek fel. A külső ábécé szerkesztésekor a táblázat automatikusan megváltozik: sorok szúródnak be, törlődnek vagy felcserélődnek.

Ne felejtsük el, hogy a külső ábécé szimbólumait valahogyan a szalag szakaszaiba kell rendezni (az összes részt üresen hagyhatja), és a kocsit az egyik résszel szemben kell elhelyezni, pl. be kell állítani a programot és a gép valamilyen állapotát.

Most közvetlenül folytathatja a probléma megoldására szolgáló algoritmus megírását. Táblázat formájában van megadva: a belső ábécé karakterei a felső sor minden oszlopába, a külső ábécé karakterei az első oszlop minden sorába kerülnek beírásra. A parancsok a többi oszlop és sor metszéspontjában lévő cellákba kerülnek. Ha bármely sor és oszlop metszéspontjában üres cellát kapunk, ez azt jelenti, hogy ebben a belső állapotban ez a szimbólum nem található.

Például készítünk egy algoritmust két pozitív egész szám különbségének megállapítására (tizedes számrendszerben), ha ismert, hogy az első szám nagyobb, mint a második, és mínusz előjel van közöttük.

A programmező így fog kinézni:

A parancsformátum minden cellában aKq. Itt:
a az aktuális cella új tartalma (az aktuális cellába beírt külső ábécé új szimbóluma), K a Turing-gép szalagmechanizmusának parancsa (balra, jobbra, stop), q az új belső állapot a Turing-gépről.

A gomb elindítja a programot. Ha a végrehajtást nem függesztették fel, akkor mindig a Q0 nulla belső állapotról indul.

A program lépésről lépésre végezhető el. Ehhez kattintson a gombra az eszköztáron (ha a gombok nem láthatók, akkor ki kell választani a menüpontot Megtekintés | Eszköztár), vagy válassza ki a főmenüből Indítás | Lépésről lépésre. Ha teljesen meg kell szakítania a program végrehajtását, ezt megteheti az eszköztár gombjával vagy a főmenü használatával ( Indítás | Elvetél). Menü tétel Sebesség lehetővé teszi a program végrehajtási sebességének beállítását.

A program mindaddig fut, amíg a „Stop” parancsot meg nem találja, vagy valamilyen hiba nem történik.

Ha bármilyen kérdése van a tolmács programmal végzett munka során, kérjük, tekintse meg a súgófájlt Algo2000.hlp. Ez, valamint maga az „Algo2000” program megtalálható az „Informatika” újság honlapján. http://inf.1september.ru a „Letöltés” ​​részben.

Mesterséges intelligencia (AI, angol: Artificial Intelligence, AI) - az intelligens gépek, különösen az intelligens számítógépes programok létrehozásának tudománya és technológiája. A mesterséges intelligencia ahhoz a hasonló feladathoz kapcsolódik, hogy számítógépeket használnak az emberi intelligencia megértésére, de nem feltétlenül korlátozódik biológiailag elfogadható módszerekre.

Mi a mesterséges intelligencia

Intelligencia(a lat. intellectus szóból - érzés, észlelés, megértés, megértés, fogalom, értelem), vagy elme - a psziché egy olyan tulajdonsága, amely az új helyzetekhez való alkalmazkodás képességéből, a tapasztalaton alapuló tanulás és emlékezés, megértés és alkalmazás képességéből áll. elvont fogalmakat, és tudását a környezetgazdálkodásban felhasználni. Az intelligencia a megismerés és a nehézségek megoldásának általános képessége, amely egyesíti az összes emberi kognitív képességet: az érzékelést, az észlelést, a memóriát, a reprezentációt, a gondolkodást, a képzeletet.

Az 1980-as évek elején. Barr és Fajgenbaum számítástechnikai tudósok a mesterséges intelligencia (AI) következő meghatározását javasolták:

Később számos algoritmust és szoftverrendszert kezdtek besorolni a mesterséges intelligencia körébe, amelyek megkülönböztető tulajdonsága, hogy bizonyos problémákat ugyanúgy meg tud oldani, ahogyan azt az ember, aki a megoldásán gondolkodik.

A mesterséges intelligencia fő tulajdonságai a nyelv megértése, a tanulás, valamint a gondolkodás, és ami fontos, a cselekvés képessége.

Az AI kapcsolódó technológiák és folyamatok komplexuma, amelyek minőségileg és gyorsan fejlődnek, például:

• természetes nyelvű szövegfeldolgozás
• szakértői rendszerek
• virtuális ügynökök (chatbotok és virtuális asszisztensek)
• ajánlási rendszerek.

A mesterséges intelligencia fejlesztésének nemzeti stratégiája

• Fő cikk: A mesterséges intelligencia fejlesztésének nemzeti stratégiája

AI kutatás

• Fő cikk: Mesterséges intelligencia kutatás

Szabványosítás az AI-ban

2019: Az ISO/IEC szakértői támogatták az orosz nyelvű szabvány kidolgozására irányuló javaslatot

2019. április 16-án vált ismertté, hogy az ISO/IEC mesterséges intelligencia szabványosítási albizottsága támogatta az RVC alapján létrehozott „Kiberfizikai rendszerek” Technikai Bizottság javaslatát a „Mesterséges intelligencia” fejlesztésére. alapértelmezett. Fogalmak és terminológia" orosz nyelven az alap angol változat mellett.

Terminológiai szabvány „Mesterséges intelligencia. Fogalmak és terminológia” alapvető fontosságú a mesterséges intelligencia területére vonatkozó nemzetközi szabályozási és műszaki dokumentumok teljes családjában. A kifejezéseken és definíciókon kívül ez a dokumentum koncepcionális megközelítéseket és elveket tartalmaz az elemeket tartalmazó rendszerek felépítéséhez, a mesterséges intelligencia és más végpontok közötti technológiák közötti kapcsolat leírását, valamint a szabályozási és műszaki szabályozás alapelveit és keretmegközelítését. a mesterséges intelligencia.

Az ISO/IEC illetékes albizottságának dublini ülését követően az ISO/IEC szakértői támogatták az orosz delegáció javaslatát, hogy egyidejűleg dolgozzanak ki egy terminológiai szabványt a mesterséges intelligencia területén ne csak angolul, hanem oroszul is. A dokumentum jóváhagyása 2021 elején várható.

Az értekezleten az ISO/IEC szakértői támogatták az Informatika – Mesterséges Intelligencia (AI) – Az AI-rendszerek számítási megközelítéseinek áttekintése című nemzetközi dokumentum tervezetének kidolgozását is, amelyben Oroszország társszerkesztőként működik közre. A dokumentum áttekintést ad a mesterséges intelligencia rendszerek jelenlegi állapotáról, leírja a rendszerek főbb jellemzőit, algoritmusait és megközelítéseit, valamint példákat mutat be a mesterséges intelligencia területén alkalmazott speciális alkalmazásokra. E dokumentumtervezet kidolgozását az albizottságon belül egy speciálisan létrehozott 5. „A mesterséges intelligencia rendszerek számítási megközelítései és számítási jellemzői” munkacsoport végzi (SC 42 Munkacsoport 5 „Számítási megközelítések és AI rendszerek számítási jellemzői”).

A mesterséges intelligencia technológiákra nagy a kereslet a digitális gazdaság számos ágazatában. A teljes körű gyakorlati alkalmazásukat leginkább akadályozó tényezők között szerepel a szabályozási keretek fejletlensége. Ugyanakkor a jól kidolgozott szabályozási és műszaki keret biztosítja a technológia alkalmazásának meghatározott minőségét és az ennek megfelelő gazdasági hatást.

A mesterséges intelligencia területén az RVC-n alapuló TC Cyber-Physical Systems számos nemzeti szabványt fejleszt, amelyek jóváhagyását 2019 végére - 2020 elejére tervezik. Emellett a piaci szereplőkkel közösen dolgoznak a nemzeti szabványosítási terv (NSP) kidolgozásán 2020-ra és azt követően. A TC "Kiberfizikai rendszerek" nyitva áll az érdekelt szervezetek dokumentumfejlesztési javaslataira.

2018: Szabványok kidolgozása a kvantumkommunikáció, az AI és az intelligens város területén

2018. december 6-án az RVC-n alapuló „Kiberfizikai rendszerek” Műszaki Bizottság a „SafeNet” Regionális Mérnöki Központtal közösen megkezdte a Nemzeti Technológiai Kezdeményezés (NTI) és a digitális gazdaság piacaira vonatkozó szabványcsomag kidolgozását. 2019 márciusára a tervek szerint műszaki szabványosítási dokumentumokat dolgoznak ki a kvantumkommunikáció területén, és számolt be az RVC. Olvass tovább.

A mesterséges intelligencia hatása

Az emberi civilizáció fejlődésének veszélye

Hatás a gazdaságra és az üzleti életre

• A mesterséges intelligencia technológiák hatása a gazdaságra és az üzleti életre

Hatás a munkaerőpiacra

Mesterséges intelligencia elfogultság

A mesterséges intelligencia gyakorlatának (gépi fordítás, beszédfelismerés, természetes nyelvi feldolgozás, számítógépes látás, automatizált vezetés és még sok más) középpontjában a mély tanulás áll. Ez a gépi tanulás egy részhalmaza, amelyet neurális hálózati modellek használata jellemez, amelyekről elmondható, hogy utánozzák az agy működését, ezért nehéz lenne az MI-be sorolni őket. Bármely neurális hálózati modellt nagy adathalmazokon képezik, így bizonyos „készségekre” tesz szert, de ezek felhasználási módja továbbra is homályos a készítői számára, ami végül sok mély tanulási alkalmazás egyik legfontosabb problémája lesz. Ennek az az oka, hogy egy ilyen modell formálisan működik képekkel, anélkül, hogy megértené, mit csinál. Egy ilyen rendszer mesterséges intelligencia, és megbízhatóak-e a gépi tanulásra épülő rendszerek? Az utolsó kérdésre adott válasz következményei túlmutatnak a tudományos laboratóriumon. Ezért érezhetően felerősödött a média figyelme az AI-bias nevű jelenségre. Lefordítható „AI torzításnak” vagy „AI torzításnak”. Olvass tovább.

Mesterséges intelligencia technológiai piac

AI piac Oroszországban

Globális AI piac

Az AI alkalmazási területei

A mesterséges intelligencia alkalmazási területei meglehetősen szélesek, és egyaránt lefedik az ismert technológiákat és a kialakulóban lévő új területeket, amelyek távol állnak a tömeges alkalmazástól, vagyis ez a megoldások teljes skálája, a porszívóktól az űrállomásokig. Az összes sokféleségüket feloszthatja a kulcsfontosságú fejlesztési pontok kritériumai szerint.

Az AI nem egy monolitikus témakör. Ezenkívül a mesterséges intelligencia egyes technológiai területei a gazdaság új alágazataként és különálló entitásként jelennek meg, miközben a gazdaság legtöbb területét egyidejűleg szolgálják ki.

A mesterséges intelligencia használatának fejlődése a gazdaság klasszikus ágazataiban a technológiák adaptációjához vezet a teljes értéklánc mentén, és átalakítja azokat, ami a logisztikától a vállalatirányításig szinte minden funkcionalitás algoritmizálásához vezet.

AI használata védelmi és katonai ügyekben

Használata az oktatásban

AI használata az üzleti életben

AI a csalás elleni küzdelemben

2019. július 11-én vált ismertté, hogy mindössze két éven belül a mesterséges intelligenciát és a gépi tanulást háromszor gyakrabban fogják használni a csalás elleni küzdelemben, mint 2019 júliusában. Ilyen adatokhoz az SAS és a Certified Fraud Examiners (ACFE) közös tanulmánya során jutottak hozzá. 2019 júliusában a felmérésben részt vevő szervezetek 13 százalékánál már használnak ilyen csalás elleni eszközöket, további 25 százalékuk pedig azt mondta, hogy a következő egy-két éven belül tervezi ezek bevezetését. Olvass tovább.

AI az elektromos energiaiparban

• Tervezési szinten: a termelés és az energiaforrások iránti kereslet jobb előrejelzése, az energiatermelő berendezések megbízhatóságának felmérése, a megnövekedett kereslet esetén a megnövekedett termelés automatizálása.
• Gyártási szinten: berendezések megelőző karbantartásának optimalizálása, termelési hatékonyság növelése, veszteségek csökkentése, energiaforrások ellopásának megakadályozása.
• Promóciós szinten: az árképzés napszaktól és dinamikus számlázástól függő optimalizálása.
• Szolgáltatásnyújtás szintjén: a legjövedelmezőbb szállító automatikus kiválasztása, részletes fogyasztási statisztikák, automatizált ügyfélszolgálat, az energiafogyasztás optimalizálása a vevő szokásait és viselkedését figyelembe véve.

AI a gyártásban

• Tervezési szinten: új termékfejlesztés hatékonyságának növelése, automatizált beszállítói felmérés és alkatrészigények elemzése.
• Gyártási szinten: a feladatok elvégzésének folyamatának javítása, az összeszerelő sorok automatizálása, a hibák számának csökkentése, az alapanyagok szállítási idejének csökkentése.
• Promóciós szinten: támogatási és karbantartási szolgáltatások volumenének előrejelzése, árkezelés.
• Szolgáltatásnyújtás szintjén: járműflotta útvonalak tervezésének javítása, flottaerőforrás-igény, szervizmérnök képzés színvonalának javítása.

AI a bankokban

• Mintafelismerés – használt incl. hogy felismerje az ügyfeleket a fiókokban, és speciális ajánlatokat közvetítsen számukra.

AI a közlekedésben

• Az autóipar forradalom küszöbén áll: 5 kihívás a pilóta nélküli vezetés korszakában

AI a logisztikában

AI a sörfőzésben

AI az igazságszolgáltatásban

A mesterséges intelligencia területén végrehajtott fejlesztések hozzájárulnak az igazságszolgáltatási rendszer gyökeres megváltoztatásához, igazságosabbá és korrupciós rendszerektől mentessé téve azt. Ezt a véleményt 2017 nyarán fejtette ki Vladimir Krylov, a műszaki tudományok doktora, az Artezio műszaki tanácsadója.

A tudós úgy véli, hogy a mesterséges intelligencia területén meglévő megoldások sikeresen alkalmazhatók a gazdaság és a közélet különböző területein. A szakember kiemeli, hogy a mesterséges intelligenciát sikeresen alkalmazzák az orvostudományban, de a jövőben teljesen megváltoztathatja az igazságszolgáltatási rendszert.

„Minden nap nézegeti a híradásokat a mesterséges intelligencia terén elért fejleményekről, és csak csodálkozik a kutatók és fejlesztők kimeríthetetlen fantáziáján és gyümölcsöző képességén ezen a területen. A tudományos kutatásokról szóló jelentések folyamatosan tarkítják a piacra kerülő új termékekről szóló publikációkat, valamint a mesterséges intelligencia különféle területeken történő felhasználásával elért lenyűgöző eredményekről szóló jelentéseket. Ha a várható eseményekről beszélünk, a médiában feltűnő hype kíséretében, amelyben a mesterséges intelligencia ismét a hírek hőse lesz, akkor valószínűleg nem kockáztatom meg a technológiai előrejelzéseket. El tudom képzelni, hogy a következő esemény egy rendkívül hozzáértő bíróság megjelenése valahol mesterséges intelligencia formájában, tisztességes és megvesztegethetetlen. Ez nyilván 2020-2025-ben fog megtörténni. Az ebben a bíróságon lezajló folyamatok pedig váratlan gondolatokhoz és sok ember vágyához vezetnek, hogy az emberi társadalom irányításának legtöbb folyamatát átvigyék a mesterséges intelligenciára.”

A tudós a mesterséges intelligencia igazságszolgáltatási rendszerben történő alkalmazását „logikus lépésként” ismeri el a jogalkotási egyenlőség és igazságosság fejlesztése felé. A gépi intelligencia nem kitéve a korrupciónak és az érzelmeknek, szigorúan be tudja tartani a jogszabályi keretet, és számos tényezőt figyelembe véve hozhat döntéseket, beleértve a vitában részt vevő feleket jellemző adatokat is. Az orvosi terület analógiájára a robotbírók a kormányzati szolgáltatások adattáraiból származó big data segítségével dolgozhatnak. Feltételezhető, hogy

Zene

Festmény

2015-ben a Google csapata neurális hálózatokat tesztelt, hogy megnézze, képesek-e önállóan képeket létrehozni. Ezután a mesterséges intelligenciát számos különböző kép felhasználásával képezték ki. Amikor azonban „megkérték” a gépet, hogy önmagában is ábrázoljon valamit, kiderült, hogy kissé furcsán értelmezi a minket körülvevő világot. Például a súlyzók rajzolásának feladatához a fejlesztők egy képet kaptak, amelyen a fémet emberi kéz köti össze. Ez valószínűleg annak köszönhető, hogy a képzési szakaszban a súlyzókkal elemzett képek kezet tartalmaztak, és a neurális hálózat ezt hibásan értelmezte.

2016. február 26-án egy különleges aukción San Franciscóban a Google képviselői mintegy 98 ezer dollárt gyűjtöttek be mesterséges intelligencia által létrehozott pszichedelikus festményekből, amelyeket jótékony célokra ajánlottak fel. Az alábbiakban bemutatjuk az egyik legsikeresebb képet az autóról.

A Google mesterséges intelligenciája által festett festmény.

Mindig azt látjuk. „RESTful” ez, „REST” protokoll, hogy stb. Sokan azonban nem igazán értjük, hogy ez pontosan mit is jelent. Ebben a cikkben pontosan ezt a hiányosságot pótoljuk!

Állapot

Az informatikában (és bizonyos mértékig a matematikában) létezik az állam fogalma. Egy bizonyos rendszer lehet állapotban A vagy lehet állapotban B vagy lehet egy csomó más állapot (általában az állapotok véges listája).

Példaként tegyük fel, hogy írunk egy programot, amely pirosra változtatja a képernyőt, ha a hőmérséklet meghaladja a 80 fokot, vagy kékre, ha a hőmérséklet kevesebb, mint 80 farenheit.

Az első állapotot (hőmérséklet > 80 fok) nevezhetjük „A”-nak, a második állapotot (hőmérséklet< 80 degrees) state “B”. We’ll call the middling state (temp = 80 degrees) state “C”. As we can see, we have defined behaviours of the programs at state A and state B, but not at state C.

Ez az állam általános elképzelése. Íme a mindent tudó Wikipédia definíciója:

„A számítástechnikában és az automataelméletben a digitális logikai áramkör vagy számítógépes program állapota egy technikai kifejezés az összes tárolt információra egy adott időpontban, amelyet az áramkör vagy a program használ.”

Röviden, ez egyfajta „kombináció” mindazon információknak, amelyeket a program figyelembe vesz.

Most meg fogunk ugrani valamiben, amit nagyrészt elméletinek és haszontalannak tartanak, majd valahogy kapcsolódunk a REST nagyon gyakorlati világához.

Turing gépek

Volt egy Alan Turing nevű ember, aki meglehetősen okos matematikus volt, akit érdekelt a számítógépek működése. Elgondolt egy képzeletbeli számítógépet (amelyet, mint látni fogjuk, valójában lehetetlen megépíteni), amelyet arra használt, hogy a valós számítógépekben történõ dolgokról okoskodjon.

A számítógép egy végtelen hosszúságú szalagból áll, egy fejjel, amelyen a szalag áthalad. A szalagon vannak „cellák”, amelyekbe információkat lehet írni (számok, színek, stb.) A szalag a gépen halad keresztül, balra vagy jobbra, egyenként cellánként. A gép beolvassa azt, ami már a szalagon van, és attól függően, hogy milyen állapotban van, visszaír valamit a szalagra, majd ezt követően megváltoztatja az állapotát.

Érdemes újra elolvasni ezt a definíciót, hogy teljesen belesüllyedjen. Az ötlet lényege, hogy a memórián állapot alapján hajt végre műveleteket, és a memórián végzett műveletek szerint változtatja meg az állapotokat.

Ez meglehetősen haszontalan elméleti fantáziának tűnik (bár nincs ezzel semmi baj, olvassa el az Egy matematikus bocsánatkérését, ha kíváncsi arra, hogy az emberek miért érdeklődnek az elméleti dolgok iránt). Valószínűleg azonban ez a számítástechnika legalapvetőbb fogalma.

A Turing-gép segítségével az informatikusok képesek megfontolni bármely számítógépen futtatható algoritmust. Valójában a Turing-gép számos előrelépéshez vezetett a számítástechnikában.

Tehát a Turing-gép megmutatja, hogy ma (megjegyzés: nem a gráfredukciós processzorokra gondolok) a számítástechnikában szó szerint minden az állapot gondolatán alapul.

A hálózat

Aztán jött az internet fogalma. Ez az a hely, ahol a csomagok széthullhatnak, és addig küldik őket, amíg el nem érik a céljukat. Általánosságban elmondható, hogy soha nem kerül sor a teljes adatok teljes átvitelére.

Az ügyfelek gyorsan jönnek és kétszer olyan gyorsan távoznak. Mint ilyen, a kliens állapotának megőrzésének nincs sok értelme, ha hálózati rendszeren dolgozik.

Általánosságban elmondható, hogy a túl sok állapot megtartása egy rendszerben komoly fájdalmat okozott (ami szintén funkcionális programozási nyelvekhez vezet, amelyek nem teszik lehetővé az állapot megtartását a kód nagy részében).

Az embereknek most olyan hálózati protokollra volt szükségük az internethez, amely egyszerű, gyors és jól kezeli az állapotkezelést egy rendkívül dinamikus környezetben.

Ez a protokoll a HTTP volt, és a HTTP-vel kapcsolatos munkából kifejlődött elmélet a REST címkét kapta.

PIHENÉS

A REST jelentése: RErepresentational State Transfer. Ez egy olyan „kliens-szerver” koncepció köré épülő rendszer, amelyre a hálózatok épülnek (na jó, vannak peer-to-peer típusú hálózatok is, de a kliens-szerver vitathatatlanul a legegyszerűbb és legtöbbet tesztelt architektúra). Maga a név kissé megtévesztő, mivel a szerver teljesen állapotmentes!

Van néhány megkötés, amelyeket minden „RESTful”-nak mondó rendszernek be kell tartania.

Először is azt kell kliens-szerver rendszer legyen. Ezt a megszorítást a múltban módosították, de a formális definícióban (és ahhoz, hogy a REST elmélete megfelelően működjön) vannak szervereink, amelyekhez az ügyfelek csatlakozhatnak.

A szerver teljesen állapotmentes. Ez azt jelenti, hogy a kiszolgálóhoz intézett egyes klienskérésekhez nincs lefoglalva állapot a kiszolgálón. Például, ha egy kliens (HTTP-t használva) lekéri az indexoldalt, majd ezt követően a /user/home oldalt, akkor a két kérelem teljesen független egymástól. Az ügyfél tartja minden a rendszer állapotáról (ezért van a vissza gomb).

A szervertől érkező válaszoknak gyorsítótárazhatónak kell lenniük, ami azt jelenti, hogy a szerveren kell lennie egy rendszernek, amely azonosítja a válaszokat gyorsítótárazható-e vagy sem, hogy a kliensek (pl. webböngészők) kihasználhassák a gyorsítótár előnyeit.

Végül egy egyszerű, tiszta és egységes felülettel kell rendelkeznünk. Ha van némi tapasztalata a HTTP működésével kapcsolatban, a kérési űrlapok nagyon egyszerűek. Ezek nagyrészt igék és főnevek, nagyon könnyen értelmezhető és ember által olvasható formátummal. A SOAP a hálózati protokoll egy másik formája, amely teljesen eltörli ezt a követelményt, és ezért gyakran nagyon nehéz vele dolgozni.

Nos, mit takarnak ezek a tulajdonságok, ha együtt vesszük?

A REST következményei

Lehetővé teszik számunkra, hogy tisztán elkülöníthető, méretezhető és könnyen hibakereshető rendszereket építsünk.

Nézzük először a hontalanság korlátozását a szerveren, ez lehet a legfontosabb (és egyben az ún. RESTful architektúrák által leggyakrabban megsértett) bit.

Ahogy korábban említettük, a kliens-szerver architektúrában az ügyfelek nagyon ügyesek; kéréseket indítanak el, és hirtelen megölnek minden kommunikációt. Ilyen helyzetben sokkal tisztább, ha nem mentjük el a kliens állapotát a szerveren. Ez lehetővé teszi számunkra, hogy nagyon könnyen érveljünk a HTTP szerverekkel kapcsolatban; minden ügyfélkérést úgy lehet kezelni, mintha teljesen új ügyfélről lenne szó, és ez egy fillért sem jelentene.

Másodszor, a gyorsítótárazható válaszok azt jelentik, hogy a kliensek sokkal gyorsabban tudnak adatokat kapni, mivel gyakran az adatok visszakereshetők a kliens memóriájából. Ez azonnal növeli a kliens teljesítményét, és egyes rendszerekben a szerver méretezhetőségét.

Az egységes felület talán a legfontosabb. Miután a SOAP-pal dolgoztam, elmondhatom, hogy a HTTP egyszerű formátuma áldásos a szerverkód hibakeresése során, és ugyanez vonatkozik a többi RESTful rendszerre is.

RESTful rendszer tervezése

Tegyük fel, hogy írnunk kell egy szervert, amely visszaadja a részvényárfolyamokat, valamint megőrzi a figyelni kívánt részvényárfolyamok listáját (és a felhasználó hozzáadhatja vagy törölheti a listát).

Ez egy kiváló eset egy RESTful rendszer számára, mert eleve független a kliens azonosságától. Ezért a kiszolgálónak nem kell semmilyen állapotot birtokolnia a kliensről.

Először is meghatározzuk, hogyan fog működni a protokollnyelv (kicsit úgy, mint a HTTP GET és POST igéi):

IDÉZZ ketyegő- egy adott részvény árát adja meg
ADDTICKER ketyegő- hozzáadja az adott részvényt a listához
GETLIST – a listában szereplő részvények vesszővel elválasztott listáját kapja meg

Ez egy meglehetősen egyszerű protokoll, és nem tart fenn semmilyen állapotot a szerveren. Ami pedig a gyorsítótárat illeti, azt mondhatjuk, hogy óránként frissítjük az árakat, így az egy óránál régebbi gyorsítótárak kidobhatók.

És ez minden benne van! Természetesen ezt még meg kell valósítanunk, de a rendszer általános ötlete meglehetősen egyszerű és letisztult!

Következtetés

Remélhetőleg ez a cikk alapos megértést adott a RESTről.

Továbbá, remélem, hogy most már meg tudja majd hívni azokat az embereket, akik túl sokat dobnak a „RESTful” kifejezéssel – mondhatom, nagyon sok van belőlük!

TURING

TURING(Turing) Alan (1912-54), angol matematikus és logikus, aki olyan elméleteket fogalmazott meg, amelyek később a számítástechnika alapjává váltak. 1937-ben azzal állt elő Turing gép - egy hipotetikus gép, amely képes átalakítani a bemeneti parancsok halmazát. Ez volt a modern számítógépek előfutára. Turing a számítógép ötletét is felhasználta arra, hogy alternatív és egyszerűbb bizonyítást adjon Gödel hiányossági tételére. Turing jelentős szerepet játszott az Enigma megoldásában, egy összetett titkosítási módszerben, amelyet Németország használt a második világháború alatt. 1948-ban részt vett a világ egyik első számítógépének megalkotásában. 1950-ben azzal állt elő Turing teszt - ez a számítógép „gondolkodási” képességének próbája volt. Lényegében azt mondta ki, hogy egy személy nem tudja megkülönböztetni a géppel folytatott párbeszédet a másik személlyel folytatott párbeszédtől. Ez a munka megnyitotta az utat a MESTERSÉGES INTELLIGENCIA létrehozásához. Turing az elméleti biológiával is foglalkozott. Folyamatban "A morfogenezis kémiai alapjai"(1952) olyan modellt javasolt, amely leírja az élőlények különféle szerkezeti mintáinak eredetét a biológiában. Azóta gyakran használnak ilyen modelleket számos, a természetben megfigyelt rendszer leírására és magyarázatára. Turing öngyilkos lett, miután hivatalosan is megvádolták homoszexualitással.

Tudományos és műszaki enciklopédikus szótár.

Nézze meg, mi a "TURING" más szótárakban:

Turing, Alan Mathison Alan Turing Alan Mathison Turing emlékmű a Sackville Parkban Születési dátum ... Wikipédia

- (Turing) Alan Mathieson (1912 54), angol matematikus. 1936-1937-ben bevezette az algoritmus absztrakt megfelelőjének, vagy egy kiszámítható függvénynek a matematikai fogalmát, amelyet akkoriban Turing-gépnek neveztek... Modern enciklopédia

- (Turing), Alan Matheson (1912. június 23. – 1954. június 7.) - angol. logikus és matematikus. 1936–37-ben a számítás idealizált gépi modelljét javasolta. folyamat - egy számítási séma, amely közel áll a számításokat végző személy tevékenységéhez, és előterjesztett... ... Filozófiai Enciklopédia

Turing A.- Turing A. angol matematikus. Témák információbiztonság HU Turing… Műszaki fordítói útmutató

Alan Turing Alan Turing emlékmű a Sackville Parkban Születési idő: 1912. június 23. Születési hely: London, Anglia Halálozás ideje: 1954. június 7. ... Wikipédia

Turing- Alan M. Turing angol matematikus, különösen a számítástechnika logikai alapjainak egyik megalkotója adta meg az algoritmus egyik formális definícióját; bebizonyította, hogy létezik a számítógépeknek egy osztálya, amely képes szimulálni... ... Lem világa - Szótár és útmutató

- (Turing) Alan Mathieson (1912.6.23., London, 1954.6.7., Wilmslow, Manchester mellett), angol matematikus. A Royal Society tagja (1951). A Cambridge-i Egyetem elvégzése után (1935) Princetonban dolgozott doktori disszertációján... ... Nagy Szovjet Enciklopédia

Turing A.M.- TURING (Turing) Alan Mathieson (191254), angol. matematikus. Alapvető tr. a matematikában logika, számol. matematika. 1936-ban37 bevezette a matematikát. egy algoritmus absztrakt megfelelőjének vagy egy kiszámítható függvénynek a fogalma, amelyet akkor nevezünk. autó T... Életrajzi szótár

- (teljes Alan Mathison Turing) (1912. június 23., London, 1954. június 7., Wilmslow, Egyesült Királyság), brit matematikus, matematikai logikával és számítási matematikával foglalkozó művek szerzője. 1936-1937-ben bevezette a matematikai fogalmat... enciklopédikus szótár

Könyvek

• Tud gondolkodni egy gép? Az automaták általános és logikai elmélete. Issue 14, Turing A., Ez a könyv, amely Alan Turing és John von Neumann munkáit tartalmazza, akik az első gondolkodó számítógépek megalkotásának kezdetei voltak, a filozófiai-kibernetikai... Kategória: Adatbázisok Sorozat: Mesterséges tudományok Kiadó: URSS, Gyártó: URSS,
• Tud gondolkodni egy gép? Az automaták általános és logikai elmélete. 14. szám, Turing A., A filozófiai-kibernetika klasszikusai közé tartozik ez a könyv, amely Alan Turing és John von Neumann munkáit tartalmazza, akik a számítógépek első „gondolkodógépei” megalkotásának kezdetei voltak. irány... Kategória: