FEDERALINĖ ŠVIETIMO AGENTŪRA VALSTYBINĖ AUKŠTOJO PROFESINIO MOKYMO INSTITUCIJA „VORONEŽO VALSTYBINIO UNIVERSITETAS“ T.K. Katsaranas, L.N. Stroeva TURINGO MAŠINA IR REKURSINĖS FUNKCIJOS Vadovėlis universitetams Voronežo valstybinio universiteto Leidybos ir spausdinimo centras 2008 Patvirtinta PMM fakulteto mokslo ir metodinės tarybos 2008 m. gegužės 25 d., protokolas Nr. 9 Recenzentas Technikos mokslų daktaras, prof. Operacijų tyrimo matematinių metodų katedra T.M. Ledeneva Vadovėlis parengtas Voronežo valstybinio universiteto Mechaninės matematikos fakulteto Netiesinių virpesių katedroje. Rekomenduojamas VSU Taikomosios matematikos ir matematikos fakulteto, VSU Starooskolsky ir Liskinsky filialų I kurso studentams. Specialybei 010500 – Taikomoji matematika ir informatika ĮVADAS Žodis „algoritmas“ kilęs iš „algoritmi“ – uzbekų matematiko ir astronomo, gyvenusio VIII–IX a. (783–850 m.), Muhammado ben Musa al-, lotyniškos rašybos. Khwarizmi. Šiuo vardu viduramžių Europoje buvo žinomas didžiausias matematikas iš Chorezmo (šiuolaikinio Uzbekistano miesto). Savo knygoje „Apie indišką skaičiavimą“ jis suformulavo natūraliųjų skaičių rašymo naudojant arabiškus skaitmenis taisykles ir veikimo su jais taisykles. Tada algoritmo sąvoka pradėta vartoti platesne prasme ir ne tik matematikoje. Ir matematikams, ir praktikams svarbi algoritmo sąvoka. Taigi galima teigti, kad algoritmas – tai tikslus nurodymas atlikti tam tikrą operacijų sistemą tam tikra tvarka, siekiant išspręsti visas to paties tipo problemas, apibrėžiantis veiksmų seką, užtikrinančią reikiamo rezultato gavimą iš pradinių duomenų. Atkreipkite dėmesį, kad tai nėra sąvokos „algoritmas“ apibrėžimas, o tik jos aprašymas, intuityvi prasmė. Algoritmas gali būti sukurtas taip, kad jį vykdytų asmuo arba automatinis įrenginys. Ši algoritmo idėja matematiniu požiūriu nėra griežta, nes joje vartojamos tokios sąvokos kaip „tikslios instrukcijos“ ir „pradiniai duomenys“, kurios, paprastai kalbant, nėra griežtai apibrėžtos. Bet kurio algoritmo bruožas yra jo gebėjimas išspręsti tam tikros klasės problemas. Pavyzdžiui, tai gali būti tiesinių lygčių sistemų sprendimo algoritmas, trumpiausio kelio radimas grafike ir pan. Algoritmo, net ir paprasčiausio, sukūrimas yra kūrybingas procesas. Jis prieinamas tik gyvoms būtybėms, ir ilgą laiką buvo manoma, kad tik žmonėms. Kitas dalykas – esamo algoritmo įgyvendinimas. Tai gali būti patikėta subjektui ar objektui, kuris neprivalo gilintis į reikalo esmę, o galbūt ir nesugeba jos suprasti. Toks subjektas ar objektas paprastai vadinamas formaliuoju atlikėju. Oficialaus atlikėjo pavyzdys – automatinė skalbimo mašina, kuri griežtai atlieka jai numatytus veiksmus, net jei pamiršote į ją įdėti miltelių. Žmogus gali veikti ir kaip formalus atlikėjas, tačiau visų pirma įvairūs automatiniai įrenginiai, tarp jų ir kompiuteris, yra formalūs atlikėjai. Kiekvienas algoritmas sukurtas turint omenyje labai konkretų atlikėją. Tie veiksmai, kuriuos atlikėjas gali atlikti, vadinami jo leistinais veiksmais. Leidžiamų veiksmų rinkinys sudaro vykdytojo komandų sistemą. Algoritme turi būti tik tie veiksmai, kurie yra leidžiami konkrečiam atlikėjui. Todėl dažniausiai suformuluojamos kelios bendrosios algoritmų savybės, kad atskirtų algoritmus nuo kitų instrukcijų. Algoritmas turi turėti šias savybes. Diskretiškumas (nepertraukiamumas, atskirumas) – algoritmas turi vaizduoti problemos sprendimo procesą kaip nuoseklų paprastų (arba anksčiau apibrėžtų) žingsnių vykdymą. Kiekvienas algoritmo numatytas veiksmas vykdomas tik po to, kai ankstesnis veiksmas baigia vykdyti. Tikrumas – kiekviena algoritmo taisyklė turi būti aiški, nedviprasmiška ir nepalikti vietos savivalei. Šios savybės dėka algoritmo vykdymas yra mechaninio pobūdžio ir nereikalauja jokių papildomų nurodymų ar informacijos apie sprendžiamą problemą. Efektyvumas (baigtiškumas) – algoritmas turi padėti išspręsti problemą per baigtinį žingsnių skaičių. 4 Masyvumas - problemos sprendimo algoritmas yra sukurtas bendra forma, tai yra, jis turėtų būti taikomas tam tikrai problemų klasei, kurios skiriasi tik pradiniais duomenimis. Tokiu atveju pradinius duomenis galima pasirinkti iš tam tikros srities, kuri vadinama algoritmo taikymo sritimi. Algoritmų teorija – matematikos šaka, tirianti bendrąsias algoritmų savybes. Yra kokybinė ir metrinė algoritmų teorijos. Pagrindinė kokybinės algoritmų teorijos problema yra algoritmo, turinčio nurodytas savybes, konstravimo problema. Ši problema vadinama algoritmine problema. Metrinė algoritmų teorija nagrinėja algoritmus pagal jų sudėtingumą. Ši algoritmų teorijos šaka taip pat žinoma kaip algoritminio sudėtingumo teorija. Ieškant sprendimų kai kurioms problemoms, prireikė daug laiko rasti tinkamą algoritmą. Tokių problemų pavyzdžiai: a) nurodykite metodą, pagal kurį bet kuriai predikatinei formulei per baigtinį skaičių operacijų galima sužinoti, ar ji yra identiška, ar ne; b) ar Diofanto lygtis (algebrinė lygtis su sveikųjų skaičių koeficientais) gali būti išspręsta sveikaisiais skaičiais? Kadangi šių problemų sprendimo algoritmų rasti nepavyko, kilo prielaida, kad tokių algoritmų apskritai nėra, kas pasitvirtino: pirmąją problemą išsprendė A. Church, o antrąją – Yu.V. Matiyasevičius ir G.V. Chudnovskis. Iš principo neįmanoma to įrodyti naudojant intuityvią algoritmo koncepciją. Todėl buvo bandoma pateikti tikslų matematinį algoritmo sąvokos apibrėžimą. XX amžiaus 30-ųjų viduryje S.K. Kleene, A.A. Markovas, E. Postas, A. Turingas, A. Church ir kiti pasiūlė įvairius matematinius algoritmo sąvokos apibrėžimus 5 . Vėliau buvo įrodyta, kad šie skirtingi formalūs matematiniai apibrėžimai tam tikra prasme yra lygiaverčiai: jie apskaičiuoja tą patį funkcijų rinkinį. Tai rodo, kad pagrindinės intuityvios algoritmo koncepcijos ypatybės šiuose apibrėžimuose yra teisingai užfiksuotos. Toliau nagrinėjame A. Turingo pasiūlyto algoritmo, kuris vadinamas Tiuringo mašina, matematinį patikslinimą. 6 1. TURINGO MAŠINA § 1. Matematinis Tiuringo mašinos modelis Anglų matematiko A. Turingo XX amžiaus trečiajame dešimtmetyje pasiūlyta Tiuringo mašinos sukūrimo idėja yra susijusi su jo bandymu pateikti tikslus matematinis algoritmo sąvokos apibrėžimas. Turingo mašina (MT) yra matematinis idealizuoto skaitmeninio kompiuterio modelis. Tiuringo mašina yra tas pats matematinis objektas kaip funkcija, išvestinė, integralas, grupė ir kt. Kaip ir kitos matematinės sąvokos, Tiuringo mašinos sąvoka atspindi objektyvią tikrovę ir modeliuoja tam tikrus realius procesus. Norint apibūdinti MT algoritmą, patogu įsivaizduoti įrenginį, susidedantį iš keturių dalių: juostos, skaitymo galvutės, valdymo įrenginio ir vidinės atminties. 1. Daroma prielaida, kad juosta yra potencialiai begalinė, padalinta į ląsteles (lygias ląsteles). Jei reikia, prie pirmos arba paskutinės langelio, kuriame yra simboliai, pridedamas tuščias langelis. Mašina veikia laiku, kuris laikomas diskretišku, o jo momentai sunumeruoti 1, 2, 3, …. Bet kuriuo metu juostoje yra baigtinis skaičius langelių. Tik vienas simbolis (raidė) iš išorinės abėcėlės A = (L, a1 , a 2 ,..., a n -1 ), n ³ 2 gali būti įrašytas į langelius diskrečiu laiku. Tuščias langelis žymimas simboliu L, o pats simbolis L vadinamas tuščiu, o likę simboliai – netušti. Šioje abėcėlėje A informacija, kuri pateikiama MT, yra užkoduota žodžio forma (baigtinis sutvarkytas simbolių rinkinys). Mašina „apdoroja“ informaciją, pateiktą žodžio forma, į naują žodį. 2. Skaitymo galvutė (tam tikras skaitymo elementas) juda išilgai juostos taip, kad kiekvienu laiko momentu peržiūrėtų tiksliai vieną juostos langelį. Galva gali perskaityti langelio turinį ir įrašyti į jį naują abėcėlės simbolį Vieno veikimo ciklo metu ji gali perkelti tik vieną langelį į dešinę (R), į kairę (L) arba likti vietoje (N ). Pažymime galvos judesių (posmainų) aibę D = (P, L, N). Jei tam tikru momentu t galva yra atokiausioje ląstelėje ir pereina į trūkstamą langelį, tada pridedamas naujas tuščias langelis, virš kurio galva bus šiuo metu t + 1. 3. Mašinos vidinė atmintis yra tam tikra baigtinė vidinių būsenų rinkinys Q = ( q0 , q1 , q 2 , ..., q m ), m ³ 1 . Darysime prielaidą, kad galia |Q | ³ 2. Dvi mašinos būsenos turi ypatingą reikšmę: q1 – pradinė vidinė būsena (gali būti keletas pradinių vidinių būsenų), q0 – galutinė būsena arba sustojimo būsena (visada yra viena galutinė būsena). Kiekvienu laiko momentu MT apibūdinama galvos padėtimi ir vidine būsena. Pavyzdžiui, po langeliu, virš kurio yra galvutė, nurodoma vidinė mašinos būsena. ¯ a2 a1 L a2 a3 q1 4. Kiekvieną akimirką t valdymo įtaisas, priklausomai nuo simbolio juostoje tuo momentu skaitomo ir aparato vidinės būsenos, atlieka šiuos veiksmus: 1) pakeičia simbolį ai read šiuo metu t į naują simbolį a j (ypač palieka jį nepakeistą, t. y. ai = a j); 2) judina galvą viena iš šių krypčių: N, L, R; 3) pakeičia vidinę mašinos 8 qi būseną, esančią momentu t, į naują q j, kurioje mašina bus momentu t +1 (gali būti, kad qi = q j). Tokie valdymo įtaiso veiksmai vadinami komanda, kurią galima parašyti tokia forma: qi ai ® a j D q j , (1) kur qi – mašinos vidinė būsena šiuo metu; a i – šiuo metu skaitomas simbolis; a j – simbolis, į kurį keičiasi simbolis a i (gali būti ai = a j); simbolis D yra arba N, arba L, arba P ir nurodo galvos judėjimo kryptį; q j – vidinė mašinos būsena kitą akimirką (gal qi = q j). Išraiškos qi ai ir a j D q j atitinkamai vadinamos kairiąja ir dešine šios komandos pusėmis. Komandų, kurių kairiosios pusės skiriasi poromis, skaičius yra baigtinis skaičius, nes aibės Q \ (q 0 ) ir A yra baigtinės. Nėra komandų su identiškomis kairiosiomis pusėmis, t. y. jei mašinos programoje T yra išraiškos qi ai ® a j D q j ir qt at ® ak D qk , tada qi ¹ qt arba ai ¹ at ir D O (P, L, N ). Visų instrukcijų rinkinys vadinamas Tiuringo mašinos programa. Didžiausias komandų skaičius programoje yra (n + 1) x m, kur n + 1 = A ir m + 1 = Q. Manoma, kad galutinė komandos būsena q0 gali pasirodyti tik dešinėje komandos pusėje, pradinė būsena q1 gali būti tiek kairėje, tiek dešinėje komandos pusėje. Vienos komandos vykdymas vadinamas žingsniu. Tiuringo mašinos skaičiavimas (arba operacija) yra žingsnių seka vienas po kito nepraleidžiant, pradedant nuo pirmojo. Taigi, MT duota, jei žinomos keturios baigtinės aibės: išorinė abėcėlė A, vidinė abėcėlė Q, galvos judesių aibė D ir mašinos programa, kuri yra baigtinė komandų rinkinys. 9 § 2. Turingo mašinos veikimas Mašinos veikimą visiškai lemia užduotis pirmuoju (pradiniu) momentu: 1) žodžiai juostoje, t.y., juostos langeliuose įrašytų simbolių seka (a žodis gaunamas perskaičius šiuos simbolius juostos langeliuose iš kairės į dešinę) ; 2) galvos padėtis; 3) vidinė mašinos būsena. Šių trijų sąlygų derinys (šiuo metu) vadinamas konfigūracija (šiuo metu). Paprastai pradiniu momentu vidinė mašinos būsena yra q1, o galvutė yra virš pirmosios kairiosios arba pirmosios dešinės juostos langelio. Nurodytas žodis juostoje su pradine būsena q1 ir galvos padėtimi virš pirmojo žodžio vadinamas pradine konfigūracija. Kitu atveju sakome, kad Tiuringo mašina netaikoma pradinės konfigūracijos žodžiui. Kitaip tariant, pradiniu momentu konfigūraciją galima pavaizduoti tokia forma: juostoje, susidedančioje iš tam tikro skaičiaus langelių, kiekviename langelyje rašomas vienas iš išorinės abėcėlės A simbolių, galva yra virš pirmosios. kairysis arba pirmasis dešinysis juostos ląstelė ir vidinė mašinos padėtis yra q1. Gautas žodis juostoje ir galvos padėtis, atsirandantis įgyvendinus šią komandą, vadinamas galutine konfigūracija. Pavyzdžiui, jei pradiniu momentu ant juostos užrašomas žodis a1La 2 a1a1, tada pradinė konfigūracija atrodys taip: a1 a2 L a1 a1 q1 (po langeliu, virš kurio yra galvutė, vidinė mašinos būsena yra nurodyta). 10

Tema „Turingo mašina“ mokykliniame informatikos kurse

I.N. Falina,
Maskva

Daugelyje informatikos vadovėlių, studijuojant algoritmo sampratą ir savybes, yra tokio turinio frazės: „... yra daug skirtingų būdų parašyti tą patį algoritmą, pavyzdžiui, rašymas teksto forma, rašymas. struktūrinės schemos pavidalu, rašymas tam tikra algoritmine kalba, algoritmo atvaizdavimas Tiuringo mašinos arba pašto mašinos pavidalu...“ Deja, tik tokio tipo frazėse minima Tiuringo mašina. Be jokios abejonės, valandų, skirtų algoritmams tirti, apimtis neleidžia į šią temą įtraukti ir algoritmo rašymo Tiuringo mašinos pavidalu būdų tyrimo. Tačiau ši tema be galo įdomi, svarbi ir naudinga moksleiviams, ypač besidomintiems informatika.

Temą „Turingo mašina“ galima mokytis 8–11 klasėse kaip temos „Informacijos procesai“ dalį. Informacijos apdorojimas“, pasirenkamosiose klasėse, papildomo ugdymo sistemoje, pavyzdžiui, jaunųjų programuotojų mokyklose. Šios temos studijas gali lydėti kompiuterinė pagalba, jei mokytojas turi programinį treniruoklį „Turing Machine“. Išplėstinėse programavimo pamokose mokiniai gali savarankiškai rašyti Tiuringo mašinos programą. Kaip šio straipsnio dalį siūlome jums seminarą, skirtą problemų sprendimui tema „Turingo mašina“. Teorinė medžiaga šia tema ne kartą buvo publikuota Informatikos laikraščio puslapiuose, pavyzdžiui, Nr.3/2004, I. N. straipsnis. Falina „Algoritmų teorijos elementai“.

Tiuringo mašina – tai griežta matematinė konstrukcija, matematinis aparatas (panašus, pavyzdžiui, į diferencialinių lygčių aparatą), sukurtas tam tikriems uždaviniams spręsti. Šis matematinis aparatas buvo vadinamas „mašina“ dėl to, kad pagal sudedamųjų dalių ir veikimo aprašymą jis panašus į kompiuterį. Esminis skirtumas tarp Tiuringo mašinos ir kompiuterių yra tas, kad jos saugojimo įrenginys yra begalinė juosta: tikruose kompiuteriuose saugojimo įrenginys gali būti tiek, kiek norite, bet jis turi būti baigtinis. Tiuringo mašina negali būti realizuota būtent todėl, kad jos juosta yra begalinė. Šia prasme jis yra galingesnis už bet kurią skaičiavimo mašiną.

Kiekvieną Turingo mašiną sudaro dvi dalys:

1)neribotas kelionė pirmyn ir atgal juostele, padalintas į ląsteles;

2) mašina(skaitymo/rašymo galvutė valdoma programine įranga).

Kiekviena Tiuringo mašina yra susijusi su dvi paskutinės abėcėlės: įvesties simbolių abėcėlė A = (a 0 , a 1 , ..., a m ) ir būsenų abėcėlė Q = (q 0 , q 1 , ..., q p ). (Skirtingose ​​Tiuringo mašinose gali būti susietos skirtingos abėcėlės A Ir K.) Būsena q 0 vadinama pasyvus. Manoma, kad jei mašina patenka į tokią būseną, ji baigė savo darbą. Būsena q 1 vadinama pradinė. Šioje būsenoje mašina pradeda savo darbą.

Įvesties žodis įrašomas į juostą po vieną raidę iš eilės. Įvesties žodžio kairėje ir dešinėje yra tik tušti langeliai (abėcėlėje A visada yra tuščia raidė A 0 yra ženklas, kad langelis tuščias).

Aparatas gali judėti juosta į kairę arba į dešinę, skaityti langelių turinį ir rašyti į langelius raides. Žemiau pateikiamas scheminis Tiuringo mašinos brėžinys, kurio automatas tiria pirmą langelį su duomenimis.

Mašina kiekvieną kartą „mato“ tik vieną langelį. Priklausomai nuo to, kokia raidė ai jis mato, taip pat priklausomai nuo jo būklės qj Mašina gali atlikti šiuos veiksmus:

• · stebimoje langelyje parašyti naują raidę;
• · perkelkite juostą vienu langeliu į dešinę/kairę arba nejudėkite;
• · persikelti į naują būseną.

Tai yra, Tiuringo mašina turi trijų tipų operacijas. Kiekvieną kartą kitai porai ( q j, a i) Tiuringo mašina vykdo komandą, susidedančią iš trijų operacijų su tam tikrais parametrais.

Tiuringo mašinos programa yra lentelė, kurios kiekviename langelyje parašyta komanda.

Ląstelė ( q j, a i) lemia du parametrai – abėcėlės simbolis ir mašinos būsena. Komanda yra nuoroda: kur perkelti skaitymo/rašymo galvutę, kokį simbolį įrašyti į esamą langelį, į kokią būseną turi pereiti mašina. Norėdami nurodyti mašinos judėjimo kryptį, naudojame vieną iš trijų raidžių: „L“ (kairėje), „P“ (dešinėje) arba „N“ (stacionarios).

Kai mašina įvykdo kitą komandą, ji pereina į būseną q m(kuri konkrečiu atveju gali sutapti su ankstesne būsena q j). Kitą komandą reikia rasti m lentelės eilutė sankirtoje su stulpeliu a l(laiškas a l mašina mato po pamainos).

Sutikime, kad kai juostoje yra įvesties žodis, tada mašina yra prieš kurią nors būsenos langelį q 1. Veikimo metu automatas šokinėja iš vienos programos (lentelės) langelio į kitą, kol pasieks langelį, kuriame parašyta, kad automatas turi pereiti į būseną. q 0 . Šios ląstelės vadinamos sustabdyti ląsteles. Pasiekusi bet kurią tokią ląstelę, Tiuringo mašina sustoja.

Nepaisant paprastos konstrukcijos, Tiuringo mašina gali atlikti visas įmanomas žodžių transformacijas, taip įgyvendindama visus įmanomus algoritmus.

Pavyzdys. Turite sukurti Tiuringo mašiną, kuri prideda vieną prie skaičiaus juostoje. Įvesties žodis susideda iš dešimtainių sveikųjų skaičių skaitmenų, įrašytų į juostos langelius iš eilės. Iš pradžių mašina yra priešais dešinįjį skaičiaus skaitmenį.

Sprendimas. Prie paskutinio skaičiaus skaitmens mašina turi pridėti vieną. Jei paskutinis skaitmuo yra 9, pakeiskite jį 0 ir pridėkite vieną prie ankstesnio skaitmens. Tam tikros Tiuringo mašinos programa gali atrodyti taip:

Šioje Tiuringo mašinoje q 1 – skaitmenų pasikeitimo būsena, q 0 - sustabdymo būsena. Jei gali q l mašina mato skaičių 0..8, tada atitinkamai pakeičia jį 1..9 ir pereina į būseną q 0, t.y. automobilis sustoja. Jei jis mato skaičių 9, jis pakeičia jį 0, juda į kairę, likdamas būsenoje q l. Tai tęsiasi tol, kol aparatas susidurs su skaičiumi, mažesniu nei 9. Jei visi skaičiai buvo lygūs 9, tada jis pakeis juos nuliais, vietoj didžiausio skaitmens parašys 0, pereis į kairę ir tuščiame langelyje įrašys 1. Tada jis pateks į valstybę q 0, t.y. sustos.

Praktinės užduotys

1. Tiuringo mašinos juostoje yra simbolių „+“ seka. Parašykite programą Tiuringo mašinai, kuri kas antrą „+“ simbolį pakeistų „–“. Keitimas prasideda nuo dešiniojo sekos galo. Mašina gali q 1 žiūri į vieną iš simbolių nurodytoje sekoje. Be pačios lentelės programos, žodžiais apibūdinkite, ką mašina atlieka kiekvienoje būsenoje.

2. Duotas skaičius n aštuntųjų skaičių sistemoje. Sukurkite Tiuringo mašiną, kuri padidintų nurodytą skaičių n esant 1. Mašina gali q 1 žiūri į tam tikrą įvesties žodžio skaitmenį. Be pačios lentelės programos, žodžiais apibūdinkite, ką mašina atlieka kiekvienoje būsenoje.

3. Duotas natūraliojo skaičiaus dešimtainis žymėjimas n> 1. Sukurkite Tiuringo mašiną, kuri sumažintų duotą skaičių n esant 1. Mašina gali q 1 žiūri į dešinįjį skaičiaus skaitmenį. Be pačios lentelės programos, žodžiais apibūdinkite, ką mašina atlieka kiekvienoje būsenoje.

4. Duotas natūralusis skaičius n> 1. Sukurkite Tiuringo mašiną, kuri sumažintų duotą skaičių n 1, o svarbiausias skaitmuo išvesties žodyje neturi būti 0. Pavyzdžiui, jei įvesties žodis buvo „100“, tada išvesties žodis turi būti „99“, o ne „099“. Mašina gali q 1 žiūri į dešinįjį skaičiaus skaitmenį. Be pačios lentelės programos, žodžiais apibūdinkite, ką mašina atlieka kiekvienoje būsenoje.

5. Duotas atidaromų ir uždaromų skliaustų masyvas. Sukurkite Tiuringo mašiną, kuri pašalintų abipusių skliaustų poras, t.y. esantis eilėje „()“.

Pavyzdžiui, „)“ (() (()), turite gauti „) . . . ((“.

Mašina gali q

6. Duota raidžių eilutė “ a"Ir" b“ Sukurkite Tiuringo mašiną, kuri perkels visas raides “ a“ kairėje ir raidės “ b“ – į dešinę linijos pusę. Mašina gali q 1 žiūri į kairįjį eilutės simbolį. Be pačios lentelės programos, žodžiais apibūdinkite, ką mašina atlieka kiekvienoje būsenoje.

7. Tiuringo mašinos juostoje yra skaičius, parašytas dešimtaine skaičių sistema. Padauginkite šį skaičių iš 2. Mašina gali q 1 žiūri į kairįjį skaičiaus skaitmenį. Be pačios lentelės programos, žodžiais apibūdinkite, ką mašina atlieka kiekvienoje būsenoje.

8. Duoti du natūralieji skaičiai m Ir n, pateikiami vienanarių skaičių sistemoje. Atitinkami simbolių rinkiniai yra „|“ atskirtas tuščiu langeliu. Mašina gali q 1 žiūri į dešinįjį įvesties sekos simbolį. Sukurkite Tiuringo mašiną, kuri juostoje paliks skaičių sumą m Ir n. Be pačios lentelės programos, žodžiais apibūdinkite, ką mašina atlieka kiekvienoje būsenoje.

9. Duoti du natūralieji skaičiai m Ir n, pateiktas vienanarių skaičių sistemoje. Atitinkami simbolių rinkiniai yra „|“ atskirtas tuščiu langeliu. Mašina gali q 1 žiūri į dešinįjį įvesties sekos simbolį. Sukurkite Tiuringo mašiną, kuri juostoje paliks skirtumą tarp skaičių. m Ir n. Yra žinoma, kad m> n. Be pačios lentelės programos, žodžiais apibūdinkite, ką mašina atlieka kiekvienoje būsenoje.

10. Tiuringo mašinos juostoje yra dešimtainis skaičius. Nustatykite, ar šis skaičius dalijasi iš 5 be liekanos. Jei jis dalijasi, dešinėje skaičiaus parašykite žodį „taip“, kitu atveju „ne“. Aparatas tiria tam tikrą įvesties numerio skaitmenį. Be pačios lentelės programos, žodžiais apibūdinkite, ką mašina atlieka kiekvienoje būsenoje.

Gali q 1 aparatas ieško teisingo numerio galo, gali q 2 - praleidžia ženklą „+“, pasiekus sekos pabaigą – sustoja. Gali q 3, mašina pakeičia „+“ ženklą „–“ ženklu ir, pasiekusi sekos pabaigą, sustoja.

Šios problemos sprendimas yra panašus į aukščiau aptartą pavyzdį.

valstybė q 1 - sumažiname žemiausią (kitą) skaitmenį 1. Jei jis nėra lygus nuliui, tada iškart sustabdome po sumažėjimo, jei mažiausias skaitmuo yra 0, tada vietoj jo rašome 9, perkeliame į kairę ir dar kartą atliekame atimtį . narve [ a 0 , q 1 ] Tiuringo mašina niekada nepataikys, todėl ją galima palikti neužpildytą.

4 užduotis (3 užduoties komplikacija)

valstybė q 1 - sumažiname šalutinį (kitą) skaitmenį 1. Jei jis didesnis nei 1, tada po sumažinimo iš karto sustojame, bet jei mažasis skaitmuo yra 0, tada vietoj jo rašome 9, perkeliame į kairę ir atliekame atimtį vėl. Jei sumažinamas skaitmuo yra 1, vietoj to rašome 0 ir pereiname į būseną q 2 .

valstybė q 2 - bet kurioje pozicijoje įrašius „0“, reikia išanalizuoti, ar šis nulis yra reikšmingiausias skaitmuo (t. y. ar jis yra kairėje nuo jo išvesties žodžio įraše a 0).

valstybė q 3 - jei įrašytas „0“ yra reikšmingiausias skaitmuo, jis turi būti pašalintas iš išvesties žodžio įrašo.

Tos ląstelės, į kurias Tiuringo mašina niekada nepatenka, paliekamos tuščios.

valstybė q 1: jei susiduriate su „(“, perjunkite į dešinę ir eikite į būseną q 2 ; jei susitiktum “ a 0“, tada sustokite.

valstybė q 2: simbolio „(“ poravimui analizė, poravimo atveju jie turėtų matyti „)“. Jei tai garinė pirtis, grįžkite į kairę ir eikite į valstiją q 3 .

valstybė q 3: pirmiausia ištrinkite „(“, tada „)“ ir eikite į q 1 .

Šios problemos sprendimas dažniausiai sukelia sunkumų moksleiviams. Analizuodami šios problemos sprendimą, galite eiti, pavyzdžiui, tokiu būdu.

Kartu su mokiniais peržiūrėkite šias įvesties žodžių parinktis ir paprašykite jų suformuluoti, ką turėtų daryti Tiuringo mašina, kaip atrodo išvesties žodis ir kuo šios parinktys skiriasi Tiuringo mašinos požiūriu:

aaa ->

a -> išvesties žodis atitinka įvesties žodį, žiūrime įvesties žodį, kol jis baigiasi.

bbb -> išvesties žodis atitinka įvesties žodį, žiūrime įvesties žodį, kol jis baigiasi.

b -> išvesties žodis atitinka įvesties žodį, žiūrime įvesties žodį, kol jis baigiasi.

ab -> išvesties žodis atitinka įvesties žodį, žiūrime įvesties žodį, kol jis baigiasi.

Diskusijos rezultatas. Tiuringo mašina turi „suprasti“, kokia raidžių grandine ji seka, t.y. jis turi turėti bent dvi būsenas. Tegul valstybė q 1 - judėjimas raidžių grandine a“, A q 2 - judėjimo raidžių grandinėje būsena “ b“ Atkreipkite dėmesį, kad grandinė taip pat gali būti sudaryta iš vienos raidės. Jei valstybėje pasiekėme eilutės galą q 1 arba q 2, t.y. susitiko a 0, mašina turėtų sustoti, apdorojome visą eilutę.

Apsvarstykite šias įvesties žodžių parinktis:

bba -> abb

bbbaab -> aabbbb

aabbbaab -> aaaabbbb

Diskusijos rezultatas. Pirmoji įvesties žodžio versija gali būti apdorojama nuosekliai taip: bba -> bbb-> grįžti į kairįjį raidžių grandinės galą “ b” -> abb(pakeiskite pirmąją šios grandinės raidę į " a“). Norėdami atlikti šiuos veiksmus, turėsime įvesti dvi naujas būsenas ir papildomai išaiškinti būseną q 2. Taigi, norėdami išspręsti šią problemą, turime sukurti Tiuringo mašiną su šiomis būsenomis:

q 1 - eikite į dešinę išilgai raidžių grandinės “ a“ Jei grandinė baigiasi a 0, tada eikite į q 0 ; jei jis baigiasi raide " b“, tada einame į q 2 ;

q 2 - eikite į dešinę išilgai raidžių grandinės “ b“, jei grandinė baigiasi a 0, tada eikite į q 0 ; jei baigiasi“ a“, tada pakeiskite raidę „ a"įjungta" b“, eikite į valstybę q 3 (rūšies grandinė buvo pakeista rūšies grandine);

q 3 - eikite į kairę palei raidžių grandinę “ b“ iki kairiojo galo. Jei susitikote a 0 arba " a“, tada einame į q 4 ;

q 4 – pakeisti “ b"įjungta" a“ ir eikite į q 1 (pakeiskite formos grandinę formos grandine .

7 problema

valstybė q 1 - ieškoti dešiniojo (mažiausio) skaičiaus skaitmens;

valstybė q 2 - padauginti kitą skaičiaus skaitmenį iš 2, nepridedant 1 perkėlimo;

valstybė q 3 - padauginti kitą skaičiaus skaitmenį iš 2, pridedant 1 skaitmenį.

Šios programos Turingo mašina atrodo trivialiai paprasta – ji turi tik vieną būseną. Tokia Tiuringo mašina atlieka šiuos veiksmus: ištrina dešinįjį brūkšnį, ieško skyriklio (tuščios ląstelės) ir įdeda brūkšnį į šį tuščią langelį, taip sudarydama ištisinę ilgio potėpių seką. n + m.

Tačiau, kaip bebūtų keista, šios problemos sprendimas sukelia didelių sunkumų. Labai dažnai studentai kuria Tiuringo mašiną, kuri atlieka ciklinius veiksmus: nuosekliai stumia dešinę n potėpius į kairę.

Šiuo atveju jų programa atrodo taip:

valstybė q 1 - separatoriaus paieška;

valstybė q 2 - perkeltas smūgis;

valstybė q 3 - patikrinkite pabaigą (ar visi smūgiai buvo perkelti).

Šios problemos pavyzdys aiškiai parodo, kaip dažnai vaikai bando išspręsti problemą jau pažįstamais būdais. Man atrodo, kad siūlydami studentams uždavinius konstruoti Tiuringo mašinas, ugdome gebėjimą rasti neįprastus sprendimus ir ugdome gebėjimą kūrybiškai mąstyti!

Ši užduotis moksleiviams atrodo gana lengva, tačiau sunkumų kyla sustabdant Tiuringo mašiną. Žemiau yra viena iš galimų Turingo mašinos versijų šiai užduočiai atlikti.

Sprendimo idėja (stop sąlyga). Juostoje yra dvi pradinės eigos matricos.

Pradedame trinti potėpius iš kairiojo masyvo galo m. Ir po vieną ištriname kairįjį masyvo brūkšnį m ir dešinysis brūkšnys masyve n. Bet prieš ištrinant tinkamą masyvo potėpį n, patikriname, ar jis vienintelis (t.y. paskutinis, kurį reikia ištrinti), ar ne.

Pirmiausia apibūdinkime Tiuringo mašinos būsenas, reikalingas mūsų uždaviniui išspręsti, o tada sukurkime lentelės programą.

valstybė q 1 - ieškoti skyriklio tarp potėpių masyvų judant iš dešinės į kairę;

valstybė q 2 - ieškokite kairiojo potėpio masyve m;

valstybė q 3 - kairiojo brūkšnio pašalinimas masyve m;

valstybė q 4 - ieškoti separatoriaus judant iš kairės į dešinę;

valstybė q 5 - ieškokite tinkamo potėpio masyve n;

valstybė q 6 - šio potėpio unikalumo tikrinimas masyve n, t.y. nustatyti, ar tai buvo paskutinis;

valstybė q 7 - jei tai buvo paskutinis, sustokite, kitaip pereikite prie naujo algoritmo vykdymo ciklo.

Spręsdami šią problemą, turėtumėte atkreipti dėmesį į teisingą abėcėlės rašymą:

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

valstybė q 1 - ieškoti dešiniojo numerio galo;

valstybė q 2 - mažiausio skaičiaus skaitmens analizė; jei jis lygus „0“ arba „5“, t.y. skaičius dalijasi iš 5, tada pereinama į būseną q 3 , kitaip perėjimas į būseną q 5 ;

valstybė q 3 - juostoje žodžio dešinėje parašykite raidę „D“;

valstybė q 4 - žodžio dešinėje parašykite raidę „A“ ir sustabdykite mašiną;

valstybė q 5 - raidės „N“ rašymas žodžio dešinėje;

valstybė q 6 - raidės „E“ rašymas žodžio dešinėje;

valstybė q 7 - žodžio dešinėje parašykite raidę „T“ ir sustabdykite mašiną.

Tiuringo mašinos kaip algoritmo savybės

Naudojant Tiuringo mašiną kaip pavyzdį, galima aiškiai matyti algoritmų savybes. Paprašykite mokinių parodyti, kad Tiuringo mašina turi visas algoritmo savybes.

Diskretiškumas. Tiuringo mašina gali eiti į ( k + 1) žingsnis tik atlikus į-žingsnis, nes tiksliai į-žingsnis nustato, kas bus ( k + 1) žingsnis.

Aiškumas. Kiekviename žingsnyje į langelį įrašomas simbolis iš abėcėlės, automatas atlieka vieną judesį (L, P, N), o Tiuringo mašina pereina į vieną iš aprašytų būsenų.

Determinizmas. Kiekviename Tiuringo mašinos lentelės langelyje yra tik viena veiksmo parinktis. Kiekviename žingsnyje vienareikšmiškai nustatomas rezultatas, todėl vienareikšmiškai nustatoma problemos sprendimo žingsnių seka, t.y. Jei Tiuringo mašinai suteikiamas tas pats įvesties žodis, tada išvesties žodis kiekvieną kartą bus toks pat.

Produktyvumas. Kalbant apie turinį, kiekvieno žingsnio rezultatai ir visa veiksmų seka yra vienareikšmiškai apibrėžti, todėl teisingai parašyta Turingo mašina pereis į būseną per baigtinį žingsnių skaičių q 0, t.y. per baigtinį žingsnių skaičių bus gautas atsakymas į probleminį klausimą.

Masinis personažas. Kiekviena Turingo mašina apibrėžiama per visus leistinus abėcėlės žodžius, tai yra masės charakterio savybė. Kiekviena Tiuringo mašina skirta spręsti vienos klasės uždavinius, t.y. Kiekvienai problemai parašyta savo (nauja) Tiuringo mašina.

IŠ REDAKTORIAUS

Visas straipsnyje pateiktas problemas galima išspręsti tiesiog sąsiuvinyje, nubraižant informacinę juostelę ir lentelės programą. Bet jūs galite padaryti šį procesą smagesnį ir vaizdingesnį: naudokite mašinos įgyvendinimą - pašto mašinos interpretatorių ir Turingo mašiną „Algo2000“, sukurtą Radiko Zartdinovo. Programa turi intuityvią sąsają, o jos reikalavimai yra patys nuosaikiausi: IBM PC AT 486 ar aukštesnės versijos kompiuteris, Windows 95/98/NT operacinė sistema.

Pažvelkime bendrai, kaip veikia „Algo2000“.

Programos meniu pasirinkite elementą Vertėjas ir nurodykite, su kokia mašina norime dirbti (mūsų atveju tai yra „Turingo mašina“).

Prieš mus atsiras Tiuringo mašinos laukas.

Dabar reikia nustatyti išorinę abėcėlę, t.y. eilėje Išorinė abėcėlė nurodykite, kurie simboliai yra įtraukti (jei eilutė Išorinė abėcėlė nematomas, reikia pasirinkti meniu elementą Žiūrėti | Išorinė abėcėlė). Kiekvienas simbolis gali būti nurodytas tik vieną kartą. Pabaigus įvesti išorinę abėcėlę, suformuojamas pirmasis lentelės stulpelis: jis ta pačia tvarka užpildomas išorinės abėcėlės ženklais. Redaguojant išorinę abėcėlę, lentelė automatiškai keičiama: įterpiamos, ištrinamos arba keičiamos eilutės.

Nepamirškime, kad reikia kažkaip išdėlioti išorinės abėcėlės simbolius į juostos dalis (galite visas dalis palikti tuščias) ir vežimėlį pastatyti priešais vieną iš sekcijų, t.y. reikia nustatyti programą ir tam tikrą mašinos būseną.

Dabar galite pereiti tiesiai prie problemos sprendimo algoritmo rašymo. Jis nurodomas lentelės pavidalu: vidinės abėcėlės ženklai įrašomi į kiekvieną viršutinės eilutės stulpelį, o išorinės abėcėlės ženklai – į kiekvieną pirmos stulpelio eilutę. Komandos dedamos į langelius kitų stulpelių ir eilučių sankirtoje. Jei bet kurios eilutės ir bet kurio stulpelio sankirtoje gauname tuščią langelį, tai reiškia, kad šioje vidinėje būsenoje šio simbolio negalima rasti.

Pavyzdžiui, kuriame algoritmą, kaip rasti skirtumą tarp dviejų teigiamų sveikųjų skaičių (dešimtainių skaičių sistemoje), jei žinoma, kad pirmasis skaičius didesnis už antrąjį, o tarp jų yra minuso ženklas.

Programos laukas atrodys taip:

Komandos formatas kiekviename langelyje yra aKq. Čia:
a yra naujas dabartinės ląstelės turinys (naujas išorinės abėcėlės simbolis, kuris įvedamas į esamą langelį), K yra Tiuringo mašinos juostos mechanizmo komanda (kairėn, dešinėn, sustabdyti), q yra nauja vidinė būsena. iš Tiuringo mašinos.

Mygtukas paleis programą. Jei vykdymas nebuvo sustabdytas, jis visada prasideda nuo nulinės vidinės būsenos Q0.

Programą galima atlikti žingsnis po žingsnio. Norėdami tai padaryti, spustelėkite mygtuką įrankių juostoje (jei mygtukų nesimato, turite pasirinkti meniu elementą Žiūrėti | Įrankių juosta) arba pasirinkite pagrindiniame meniu Pradėti | Žingsnis po žingsnio. Jei reikia visiškai nutraukti programos vykdymą, tai galima padaryti naudojant mygtuką įrankių juostoje arba naudojant pagrindinį meniu ( Pradėti | Nutraukti). Meniu elementas Greitis leidžia reguliuoti programos vykdymo greitį.

Programa bus vykdoma tol, kol bus pateikta komanda „Stop“ arba įvyks klaida.

Jei dirbdami su vertėjo programa turite klausimų, žr. žinyno failą Algo2000.hlp. Ją, kaip ir pačią programą „Algo2000“, galima rasti laikraščio „Informatika“ svetainėje http://inf.1september.ru skiltyje „Atsisiųsti“.

Dirbtinis intelektas (AI, angl. Artificial Intelligence, AI) – mokslas ir technologija, kurianti išmaniąsias mašinas, ypač išmaniąsias kompiuterines programas. AI yra susijęs su panašia užduotimi naudojant kompiuterius žmogaus intelektui suprasti, bet nebūtinai apsiriboja biologiškai patikimais metodais.

Kas yra dirbtinis intelektas

Intelektas(iš lot. intellectus – pojūtis, suvokimas, supratimas, supratimas, samprata, protas), arba protas – psichikos savybė, susidedanti iš gebėjimo prisitaikyti prie naujų situacijų, gebėjimo mokytis ir prisiminti remiantis patirtimi, suprasti ir taikyti abstrakčias sąvokas ir panaudoti savo žinias aplinkos valdymui. Intelektas – tai bendras gebėjimas pažinti ir spręsti sunkumus, jungiantis visus žmogaus pažintinius gebėjimus: jutimą, suvokimą, atmintį, reprezentaciją, mąstymą, vaizduotę.

1980-ųjų pradžioje. Skaičiavimo mokslininkai Barras ir Fajgenbaumas pasiūlė tokį dirbtinio intelekto (AI) apibrėžimą:

Vėliau nemažai algoritmų ir programinės įrangos sistemų buvo pradėtos priskirti dirbtiniam intelektui, kurio išskirtinė savybė yra ta, kad kai kurias problemas jie gali išspręsti taip pat, kaip tai darytų žmogus, galvojantis apie jų sprendimą.

Pagrindinės AI savybės yra kalbos supratimas, mokymasis ir gebėjimas mąstyti ir, svarbiausia, veikti.

AI yra susijusių technologijų ir procesų kompleksas, kuris kokybiškai ir greitai vystosi, pavyzdžiui:

• natūralios kalbos teksto apdorojimas
• ekspertų sistemos
• virtualūs agentai (pokalbių robotai ir virtualūs asistentai)
• rekomendacijų sistemos.

Nacionalinė dirbtinio intelekto plėtros strategija

• Pagrindinis straipsnis: Nacionalinė dirbtinio intelekto plėtros strategija

AI tyrimai

• Pagrindinis straipsnis: Dirbtinio intelekto tyrimai

AI standartizavimas

2019 m.: ISO/IEC ekspertai pritarė siūlymui parengti standartą rusų kalba

2019 m. balandžio 16 d. tapo žinoma, kad ISO/IEC dirbtinio intelekto standartizacijos pakomitetis pritarė RVC pagrindu sukurto Techninio komiteto „Kibernetinės fizinės sistemos“ siūlymui plėtoti „Dirbtinį intelektą“. standartinis. Sąvokos ir terminija“ rusų kalba, be pagrindinės anglų kalbos versijos.

Terminų standartas „Dirbtinis intelektas. Sąvokos ir terminija“ yra esminis visos tarptautinių norminių ir techninių dokumentų dirbtinio intelekto srityje šeima. Be terminų ir apibrėžimų, šiame dokumente pateikiami konceptualūs sistemų su elementais konstravimo metodai ir principai, AI ir kitų galutinių technologijų sąsajos aprašymas, taip pat pagrindiniai reguliavimo ir techninio reglamento principai ir pagrindiniai požiūriai. dirbtinio intelekto.

Po atitinkamo ISO/IEC pakomitečio posėdžio Dubline ISO/IEC ekspertai pritarė delegacijos iš Rusijos siūlymui vienu metu parengti terminų standartą dirbtinio intelekto srityje ne tik anglų, bet ir rusų kalba. Tikimasi, kad dokumentas bus patvirtintas 2021 m. pradžioje.

Susitikimo metu ISO/IEC ekspertai taip pat parėmė tarptautinio dokumento Informacinės technologijos – Dirbtinis intelektas (AI) – AI sistemų skaičiavimo metodų apžvalga, kuriame Rusija yra viena iš redaktorių, projekto rengimą. Dokumente apžvelgiama dabartinė dirbtinio intelekto sistemų būklė, aprašomos pagrindinės sistemų charakteristikos, algoritmai ir metodai, taip pat pateikiami specializuotų pritaikymų dirbtinio intelekto srityje pavyzdžiai. Šio dokumento projekto rengimą vykdys pakomitečio 5-oji darbo grupė „Skaičiavimo metodai ir AI sistemų skaičiavimo charakteristikos“ (SC 42 5 darbo grupė „AI sistemų skaičiavimo metodai ir skaičiavimo charakteristikos“).

Dirbtinio intelekto technologijos yra labai paklausios įvairiuose skaitmeninės ekonomikos sektoriuose. Vienas iš pagrindinių veiksnių, trukdančių visapusiškai jas praktiškai naudoti, yra nepakankamas reguliavimo sistemos išvystymas. Kartu būtent gerai išvystyta reguliavimo ir techninė bazė užtikrina nurodytą technologijos pritaikymo kokybę ir atitinkamą ekonominį efektą.

Dirbtinio intelekto srityje RVC pagrindu sukurta TC Cyber-Physical Systems kuria daugybę nacionalinių standartų, kuriuos planuojama patvirtinti 2019 metų pabaigoje – 2020 metų pradžioje. Be to, kartu su rinkos dalyviais dirbama siekiant suformuluoti Nacionalinį standartizacijos planą (NSP) 2020 m. ir vėlesniems metams. TC „Kibernetinės fizinės sistemos“ gali teikti suinteresuotų organizacijų pasiūlymus dėl dokumentų rengimo.

2018 m.: Kvantinių ryšių, AI ir išmaniojo miesto standartų kūrimas

2018 m. gruodžio 6 d. RVC pagrindu sukurtas Techninis komitetas „Kibernetinės fizinės sistemos“ kartu su Regioniniu inžinerijos centru „SafeNet“ pradėjo kurti standartų rinkinį Nacionalinės technologijų iniciatyvos (NTI) ir skaitmeninės ekonomikos rinkoms. Iki 2019 metų kovo mėnesio planuojama parengti techninio standartizavimo dokumentus kvantinių ryšių srityje, pranešė RVC. Skaityti daugiau.

Dirbtinio intelekto poveikis

Pavojus žmogaus civilizacijos vystymuisi

Poveikis ekonomikai ir verslui

• Dirbtinio intelekto technologijų įtaka ekonomikai ir verslui

Poveikis darbo rinkai

Dirbtinio intelekto šališkumas

Viso, kas yra AI (masinis vertimas, kalbos atpažinimas, natūralios kalbos apdorojimas, kompiuterinis matymas, automatizuotas vairavimas ir daug daugiau) pagrindas yra gilus mokymasis. Tai mašininio mokymosi pogrupis, kuriam būdingi neuroninių tinklų modeliai, kurie, galima sakyti, imituoja smegenų veiklą, todėl būtų sunku juos priskirti AI. Bet koks neuroninio tinklo modelis yra apmokytas naudojant didelius duomenų rinkinius, todėl jis įgyja tam tikrų „įgūdžių“, tačiau kaip juos naudoti, kūrėjams lieka neaišku, o tai galiausiai tampa viena iš svarbiausių daugelio gilaus mokymosi programų problemų. Priežastis ta, kad toks modelis su vaizdais dirba formaliai, nesuvokdamas, ką daro. Ar tokia sistema AI ir ar galima pasitikėti mašininio mokymosi pagrindu sukurtomis sistemomis? Atsakymo į paskutinį klausimą reikšmė neapsiriboja moksline laboratorija. Todėl žiniasklaidos dėmesys reiškiniui, vadinamam AI šališkumu, pastebimai sustiprėjo. Jis gali būti išverstas kaip „AI šališkumas“ arba „AI šališkumas“. Skaityti daugiau.

Dirbtinio intelekto technologijų rinka

AI rinka Rusijoje

Pasaulinė AI rinka

AI taikymo sritys

AI pritaikymo sritys yra gana plačios ir apima tiek pažįstamas technologijas, tiek atsirandančias naujas sritis, kurios toli gražu nėra masinis, kitaip tariant, tai yra visas sprendimų spektras nuo dulkių siurblių iki kosminių stočių. Galite suskirstyti visą jų įvairovę pagal pagrindinių vystymosi taškų kriterijų.

AI nėra monolitinė dalykinė sritis. Be to, kai kurios DI technologinės sritys atrodo kaip nauji ekonomikos subsektoriai ir atskiri subjektai, tuo pat metu aptarnaujantys daugumą ekonomikos sričių.

Plėtojant AI panaudojimą, technologijos pritaikomos klasikiniuose ekonomikos sektoriuose visoje vertės grandinėje ir jas transformuoja, o tai leidžia algoritmizuoti beveik visas funkcijas – nuo ​​logistikos iki įmonės valdymo.

AI naudojimas gynybos ir kariniams reikalams

Naudojimas švietime

AI naudojimas versle

AI kovoje su sukčiavimu

2019 m. liepos 11 d. tapo žinoma, kad vos per dvejus metus dirbtinis intelektas ir mašininis mokymasis bus naudojami kovojant su sukčiavimu tris kartus dažniau nei 2019 m. Tokie duomenys buvo gauti per bendrą SAS ir Sertifikuotų sukčiavimo ekspertų asociacijos (ACFE) tyrimą. 2019 m. liepos mėn. tokias kovos su sukčiavimu priemones jau naudoja 13% tyrime dalyvavusių organizacijų, o dar 25% teigė planuojantys jas įdiegti per artimiausius metus ar dvejus. Skaityti daugiau.

AI elektros energijos pramonėje

• Projektavimo lygmeniu: patobulintas energijos gamybos ir energijos išteklių poreikio prognozavimas, elektros energijos gamybos įrenginių patikimumo įvertinimas, padidintos gamybos automatizavimas padidėjus paklausai.
• Gamybos lygmenyje: profilaktinės įrangos priežiūros optimizavimas, gamybos efektyvumo didinimas, nuostolių mažinimas, energijos išteklių vagysčių prevencija.
• Akcijos lygiu: kainodaros optimizavimas priklausomai nuo paros laiko ir dinaminis atsiskaitymas.
• Paslaugų teikimo lygmenyje: automatinis pelningiausio tiekėjo parinkimas, detali vartojimo statistika, automatizuotas klientų aptarnavimas, energijos suvartojimo optimizavimas atsižvelgiant į kliento įpročius ir elgesį.

AI gamyboje

• Projektavimo lygmeniu: naujų produktų kūrimo efektyvumo didinimas, automatizuotas tiekėjų vertinimas ir atsarginių dalių reikalavimų analizė.
• Gamybos lygiu: užduočių atlikimo proceso tobulinimas, surinkimo linijų automatizavimas, klaidų skaičiaus mažinimas, žaliavų pristatymo terminų mažinimas.
• Akcijos lygiu: palaikymo ir priežiūros paslaugų apimties prognozavimas, kainodaros valdymas.
• Paslaugų teikimo lygmeniu: transporto parko maršrutų planavimo tobulinimas, parko išteklių poreikis, serviso inžinierių rengimo kokybės gerinimas.

AI bankuose

• Rašto atpažinimas – naudojamas įsk. atpažinti klientus filialuose ir perteikti jiems specializuotus pasiūlymus.

AI transporte

• Automobilių pramonė yra ant revoliucijos slenksčio: 5 bepiločio vairavimo eros iššūkiai

AI logistikoje

AI alaus daryme

AI teismuose

Pokyčiai dirbtinio intelekto srityje padės radikaliai pakeisti teismų sistemą, padaryti ją teisingesnę ir be korupcijos schemų. Tokią nuomonę 2017 metų vasarą išsakė technikos mokslų daktaras, „Artezio“ techninis konsultantas Vladimiras Krylovas.

Mokslininkas mano, kad esami sprendimai AI srityje gali būti sėkmingai taikomi įvairiose ekonomikos ir visuomenės gyvenimo srityse. Ekspertas atkreipia dėmesį, kad dirbtinis intelektas sėkmingai naudojamas medicinoje, tačiau ateityje jis gali visiškai pakeisti teismų sistemą.

„Kiekvieną dieną žiūrėdami į naujienas apie AI srities pokyčius, jus stebina neišsenkama šios srities tyrėjų ir kūrėjų vaizduotė ir vaisingumas. Ataskaitos apie mokslinius tyrimus nuolat persipina su publikacijomis apie naujus produktus, atsirandančius rinkoje, ir pranešimais apie nuostabius rezultatus, gautus naudojant dirbtinį intelektą įvairiose srityse. Jei kalbėsime apie numatomus įvykius, lydimus pastebimo ažiotažo žiniasklaidoje, kai AI vėl taps naujienų herojumi, tikriausiai nerizikuosiu daryti technologinių prognozių. Galiu manyti, kad kitas įvykis bus kur nors itin kompetentingo dirbtinio intelekto, sąžiningo ir nepaperkamo teismo pasirodymas. Tai įvyks, matyt, 2020–2025 m. O procesai, kurie vyks šiame teisme, sukels netikėtus apmąstymus ir daugelio žmonių norą perkelti į DI daugumą žmonių visuomenės valdymo procesų.

Mokslininkas pripažįsta, kad dirbtinio intelekto naudojimas teismų sistemoje yra „logiškas žingsnis“ plėtojant įstatymų lygybę ir teisingumą. Mašininis intelektas nėra pavaldus korupcijai ir emocijoms, gali griežtai laikytis įstatyminės bazės ir priimti sprendimus atsižvelgdamas į daugelį veiksnių, įskaitant duomenis, apibūdinančius ginčo šalis. Analogiškai su medicinos sritimi, teisėjai robotai gali dirbti su dideliais duomenimis iš vyriausybinių paslaugų saugyklų. Galima manyti, kad

Muzika

Tapyba

2015 m. „Google“ komanda išbandė neuroninius tinklus, siekdama išsiaiškinti, ar jie gali patys sukurti vaizdus. Tada dirbtinis intelektas buvo treniruojamas naudojant daugybę skirtingų paveikslėlių. Tačiau aparato „paprašius“ pavaizduoti kažką savaime, paaiškėjo, kad ji kiek keistai interpretuoja mus supantį pasaulį. Pavyzdžiui, užduočiai piešti hantelius kūrėjai gavo vaizdą, kuriame metalas buvo sujungtas žmogaus rankomis. Tikriausiai taip atsitiko dėl to, kad treniruočių etape analizuojamose nuotraukose su hanteliais buvo rankos, o neuroninis tinklas tai interpretavo neteisingai.

2016 metų vasario 26 dieną specialiame aukcione San Franciske „Google“ atstovai iš dirbtinio intelekto sukurtų psichodelinių paveikslų surinko apie 98 tūkst. Žemiau pateikiama viena sėkmingiausių automobilio nuotraukų.

Google dirbtinio intelekto nutapytas paveikslas.

Mes tai matome visą laiką. „RESTful“ tai, „REST“ protokolas tas ir tt Tačiau daugelis iš mūsų nelabai supranta, ką tai reiškia. Šiame straipsnyje mes ištaisysime būtent šią spragą!

valstybė

Informatikos moksle (tam tikru mastu ir matematikoje) yra valstybės samprata. Tam tikra sistema gali būti būsenoje A arba gali būti būsenoje B arba tai gali būti daugybė kitų būsenų (dažniausiai baigtinis būsenų sąrašas).

Pavyzdžiui, tarkime, kad rašote programą, kuri paverčia ekraną raudonu, jei temperatūra yra aukštesnė nei 80 laipsnių Farenheito, arba mėlyną, jei temperatūra yra mažesnė nei 80 laipsnių Farenheito.

Pirmąją būseną (temp. > 80 laipsnių) galime vadinti „A“, o antrąją (temp< 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.

Tokia yra bendra valstybės idėja. Štai apibrėžimas, pateiktas viską žinančios Vikipedijos:

„Kompiuterių moksle ir automatų teorijoje skaitmeninės loginės grandinės arba kompiuterinės programos būsena yra techninis terminas, apibūdinantis visą saugomą informaciją tam tikru momentu, kurią naudoja grandinė arba programa.

Trumpai tariant, tai savotiškas visos informacijos, į kurią atsižvelgia programa, „derinys“.

Dabar mes padarysime šuolį į tai, kas laikoma daugiausia teoriniu ir nenaudingu, o tada kažkaip prisijungsime prie labai praktinio REST pasaulio.

Tiuringo mašinos

Buvo toks žmogus, vardu Alanas Turingas, ir jis buvo gana protingas matematikas, besidomintis kompiuterių veikimu. Jis sukūrė įsivaizduojamą kompiuterį (kurio, kaip matysime, iš tikrųjų neįmanoma sukurti), kurį naudojo samprotauti apie dalykus, kurie vyksta tikruose kompiuteriuose.

Kompiuteris susideda iš begalinio ilgio juostos su galvute, per kurią praeina juosta. Juosta turi „ląsteles“, į kurias galima įrašyti informaciją (skaičius, spalvas ir pan.) Juosta juda per šį įrenginį į kairę arba į dešinę, po vieną langelį. Aparatas nuskaito viską, kas jau yra juostoje, ir, priklausomai nuo to, kokios būsenos ji yra, kažką įrašo atgal į juostą, o vėliau pakeičia būseną.

Galbūt norėsite dar kartą perskaityti tą apibrėžimą, kad jis visiškai įsimintų. Idėjos esmė yra ta, kad ji atlieka operacijas su atmintimi pagal būseną ir būsenas keičia pagal operacijas atmintyje.

Tai atrodo gana nenaudinga teorinė fantazija (nors tame nėra nieko blogo, perskaitykite „Matematiko atsiprašymą“, jei svarstote, kodėl žmonėms rūpi domėtis teoriniais dalykais). Tačiau tai tikriausiai yra pati pagrindinė kompiuterių mokslo koncepcija.

Naudodami Turingo mašiną kompiuterių mokslininkai gali nuspręsti apie bet kokį algoritmą, kurį galima paleisti kompiuteryje. Tiesą sakant, Tiuringo mašina lėmė daugybę kompiuterių mokslo pažangos.

Taigi, Turingo mašina mums parodo, kad šiandien (pastaba: aš negalvoju apie grafikų mažinimo procesorius) tiesiogine prasme viskas kompiuterių moksle yra pagrįsta valstybės idėja.

Tinklas

Tada atsirado interneto koncepcija. Tai vieta, kur paketai gali suklysti ir siunčiami tol, kol pasiekia paskirties vietą. Apskritai, niekada nebūna visiškai perduodami visi duomenys.

Klientai ateina greitai ir išeina dvigubai greičiau. Todėl dirbant tinklo sistemoje nėra prasmės išlaikyti kliento būseną.

Be to, apskritai per didelis būsenos laikymas sistemoje sukėlė didelį skausmą (tai taip pat lemia funkcines programavimo kalbas, kurios neleidžia išlaikyti būsenos didelėje jūsų kodo dalyje).

Dabar žmonėms reikėjo interneto tinklo protokolo, kuris būtų paprastas, greitas ir puikiai valdytų būseną itin dinamiškoje aplinkoje.

Tas protokolas buvo HTTP, o teorija, kuri išaugo iš HTTP darbo, buvo pažymėta REST.

POILSIS

REST reiškia: RErepresentational State Transfer. Tai sistema, sukurta remiantis „kliento-serverio“ koncepcija, ant kurios kuriami tinklai (na, taip pat yra lygiaverčių tinklų, bet klientas-serveris, be abejo, yra paprasčiausia ir labiausiai patikrinta architektūra). Pats pavadinimas yra šiek tiek klaidinantis, nes serveris yra visiškai be būsenos!

Yra keletas apribojimų, kurių turi laikytis visos sistemos, kurios teigia, kad yra „PAilsėjusios“.

Visų pirma, tai privalo būti kliento-serverio sistema. Šis apribojimas buvo pakeistas praeityje, tačiau formaliame apibrėžime (ir tam, kad REST teorija tinkamai veiktų), turime serverius, prie kurių klientai gali prisijungti.

Serveris visiškai be pilietybės. Tai reiškia, kad kiekvienai kliento užklausai serveryje nerezervuojama jokia būsena. Pavyzdžiui, jei klientas (naudojantis HTTP) užklausa rodyklės puslapio, o vėliau prašo /user/home puslapio, šios dvi užklausos yra visiškai nepriklausomos viena nuo kitos. Klientas laikosi visi apie sistemos būseną (taigi, turime mygtuką atgal).

Atsakymai iš serverio turi būti talpinami, o tai reiškia, kad serveryje turi būti sistema, kuri identifikuotų atsakymus kaip talpyklą, ar ne, kad klientai (pvz., žiniatinklio naršyklės) galėtų pasinaudoti talpykla.

Galiausiai turime turėti paprastą, švarią ir vienodą sąsają. Jei turite patirties, kaip veikia HTTP, užklausų formos yra labai paprastos. Tai daugiausia veiksmažodžiai ir daiktavardžiai, kurių formatą labai lengva išanalizuoti ir skaitomas žmonėms. SOAP yra kita tinklo protokolo forma, kuri visiškai panaikina šį reikalavimą ir todėl dažnai yra labai sunku dirbti.

Ką reiškia visos šios savybės, paėmus kartu?

REST pasekmės

Jie leidžia mums sukurti sistemas, kurios yra aiškiai atskirtos, keičiamos ir lengvai derinamos.

Pirmiausia panagrinėkime bevalstybės apribojimą serveryje, jis gali būti pats svarbiausias (ir, beje, dažniausiai pažeidžiamas vadinamasis RESTful architektūros) bitas.

Kaip minėta anksčiau, kliento-serverio architektūroje klientai yra labai judrūs; jie paleidžia prašymus ir staiga nužudo visą bendravimą. Esant tokiai situacijai, daug švariau neišsaugoti būsenos apie klientą serveryje. Tai leidžia mums labai lengvai samprotauti dėl HTTP serverių; kiekvienas kliento prašymas gali būti traktuojamas taip, lyg tai būtų visiškai naujas klientas, ir tai neturėtų jokios įtakos.

Antra, talpykloje saugomi atsakymai reiškia, kad klientai gali gauti duomenis daug greičiau, nes dažnai duomenis galima gauti iš kliento atminties. Tai iš karto padidina kliento našumą ir, kai kuriose sistemose, serverio mastelį.

Vienoda sąsaja gali būti pati svarbiausia. Dirbdamas su SOAP galiu pasakyti, kad paprastas HTTP formatas yra palaima bandant derinti serverio kodą ir tas pats pasakytina apie kitas RESTful sistemas.

RESTful sistemos projektavimas

Tarkime, kad turime sukurti serverį, kuris grąžintų akcijų kainas, taip pat saugotų akcijų kainų sąrašą, kurį reikia stebėti (ir vartotojas gali jį papildyti arba ištrinti).

Tai puikus atvejis RESTful sistemai, nes ji iš esmės nepriklauso nuo kliento tapatybės. Todėl serveris neturi turėti jokios būsenos apie klientą.

Pirmiausia apibrėžiame, kaip veiks protokolo kalba (šiek tiek panašiai kaip HTTP veiksmažodžiai GET ir POST):

GAUTI CITATĄ ticker- nurodo konkrečios akcijos kainą
ADDTICKER ticker- įtraukia nurodytą atsargą į sąrašą
GETLIST – gauna kableliais atskirtą sąraše esančių akcijų sąrašą

Tai gana paprastas protokolas ir neturi jokios būsenos serveryje. Dabar, kalbant apie talpyklą, galime sakyti, kad kainas atnaujiname kas valandą, todėl senesnės nei vienos valandos talpyklos gali būti išmestos.

Ir štai viskas! Žinoma, mes dar turime tai įgyvendinti, tačiau bendra sistemos idėja yra gana paprasta ir švari!

Išvada

Tikimės, kad šis straipsnis suteikė jums tvirtą supratimą apie REST.

Be to, tikiuosi, kad dabar galėsite prisišaukti žmones, kurie per daug blaškosi terminu „PAILSINGAS“ – galiu pasakyti, kad jų yra daug!

TURINGAS

TURINGAS(Turingas) Alanas (1912-54), anglų matematikas ir logikas, suformulavęs teorijas, kurios vėliau tapo kompiuterinių technologijų pagrindu. 1937 metais jis sugalvojo Tiuringo mašina - hipotetinė mašina, galinti transformuoti įvesties komandų rinkinį. Tai buvo šiuolaikinių kompiuterių pirmtakas. Turingas taip pat panaudojo kompiuterio idėją, kad pateiktų alternatyvų ir paprastesnį Gödelio neužbaigtumo teoremos įrodymą. Turingas atliko svarbų vaidmenį sprendžiant Enigmą – sudėtingą šifravimo metodą, kurį Vokietija naudojo Antrojo pasaulinio karo metais. 1948 m. jis dalyvavo kuriant vieną pirmųjų kompiuterių pasaulyje. 1950 metais jis sugalvojo Turingo testas - tai turėjo būti kompiuterio gebėjimo „mąstyti“ testas. Iš esmės jame buvo teigiama, kad žmogus negalės atskirti dialogo su mašina nuo dialogo su kitu asmeniu. Šis darbas atvėrė kelią DIRBTINIO INTELEKTO kūrimui. Turingas taip pat dalyvavo teorinėje biologijoje. Vykdoma „Cheminis morfogenezės pagrindas“(1952) jis pasiūlė modelį, apibūdinantį įvairių biologinių organizmų struktūrinių modelių kilmę. Nuo tada tokie modeliai dažnai buvo naudojami daugeliui gamtoje stebimų sistemų apibūdinti ir paaiškinti. Turingas nusižudė po to, kai buvo oficialiai apkaltintas homoseksualumu.

Mokslinis ir techninis enciklopedinis žodynas.

Pažiūrėkite, kas yra „TURING“ kituose žodynuose:

Turingas, Alanas Mathisonas Alanas Turingas Alanas Matisonas Tiuringas Paminklas Sackville Parke Gimimo data... Wikipedia

– (Turingas) Alanas Mathiesonas (1912 m. 54 m.), anglų matematikas. 1936–1937 m. jis pristatė matematinę sampratą apie abstrakčią algoritmo atitikmenį arba apskaičiuojamą funkciją, kuri tada buvo vadinama Tiuringo mašina... Šiuolaikinė enciklopedija

– (Turingas), Alanas Mathesonas (1912 m. birželio 23 d. – 1954 m. birželio 7 d.) – angl. logikas ir matematikas. 1936–1937 m. jis pasiūlė idealizuotą skaičiavimo mašinos modelį. procesas - skaičiavimo schema, artima skaičiavimus atliekančio asmens veiksmams, ir pateikta... ... Filosofinė enciklopedija

Turingas A.– Turingas A. Anglų matematikas. Informacijos saugumo temos LT Turing… Techninis vertėjo vadovas

Alano Turingo Alano Turingo paminklas Sackville parke Gimimo data: 1912 m. birželio 23 d. Gimimo vieta: Londonas, Anglija Mirties data: 1954 m. birželio 7 d. ... Vikipedija

Turingas- Anglų matematikas Alanas M. Turingas, vienas iš loginių kompiuterinių technologijų pagrindų kūrėjų, pateikė vieną iš formalių algoritmo apibrėžimų; įrodė, kad yra kompiuterių klasė, kuri gali imituoti... Lemo pasaulis – žodynas ir vadovas

– (Turingas) Alanas Mathiesonas (1912 06 23, Londonas, 1954 06 7, Wilmslow, netoli Mančesterio), anglų matematikas. Karališkosios draugijos narys (1951). Baigęs Kembridžo universitetą (1935), jis dirbo prie daktaro disertacijos Prinstone... ... Didžioji sovietinė enciklopedija

Turingas A. M.– TURINGAS (Turingas) Alanas Mathiesonas (191254), angl. matematikas. Pagrindinis tr. matematikoje logika, skaičiuoja. matematika. 1936 m.37 pristatė matematiką. abstrakčiojo algoritmo atitikmens sąvoka arba apskaičiuojama funkcija, tada vadinama. automobilis T... Biografinis žodynas

– (visas Alanas Matisonas Turingas) (1912 m. birželio 23 d., Londonas, 1954 m. birželio 7 d., Wilmslow, JK), britų matematikas, darbų apie matematinę logiką ir skaičiavimo matematiką autorius. 1936-1937 metais jis pristatė matematinę sąvoką... enciklopedinis žodynas

Knygos

• Ar mašina gali mąstyti? Bendroji ir loginė automatų teorija. 14 leidimas, Turing A., Ši knyga, kurioje yra Alano Turingo ir Johno von Neumanno, kurie buvo pirmųjų mąstančių kompiuterių kūrimo ištakos, darbai, priklauso filosofinės-kibernetinės... Kategorija: Duomenų bazės Serija: Dirbtiniai mokslai Leidėjas: URSS, Gamintojas: URSS,
• Ar mašina gali mąstyti? Bendroji ir loginė automatų teorija. 14 leidimas, Turing A., Ši knyga, kurioje yra Alano Turingo ir Johno von Neumanno, kurie buvo pirmųjų kompiuterių „mąstymo mašinų“ ištakų, darbai, priklauso filosofinės-kibernetikos klasikai. kryptis... Kategorija: