ingångFormella artister är övervägande. "Datavetenskap"
Matematiska grunder för informatik
A.G. Gein
Kursplan
| NEWSPAPER_NUMBER | Föreläsning |
Föreläsning 1.Vad är "matematiska grunder för datavetenskap". Varför datavetenskap ofta anses vara ett närbesläktat Information och dess kodning. Matematik av koder. Fel vid korrigering av koder. Ekonomisk kodning. |
|
| Föreläsning 2.Matematiska modeller av formella artister. Vad är formell informationsbehandling? Slutlig nya maskiner. Vad kommer först: språk eller artist? Språkets grammatik. Erkända språk. Universella versioner karosser (Turingmaskin, Postmaskin). |
|
| Föreläsning 3.Algoritm och dess egenskaper. Algoritmisk obestämbarhet. Beräkningsbarhet. Komplexitet. | |
| Tentamensarbete nummer 1. | |
| Föreläsning 4. Grafer... Grafer och digrafer. I vilka uppgifter uppstår de? Olika egenskaper hos grafer (Euler, Hamiltonian nyheter, planaritet, bipartition). Nätverk. Strömmar i nätverk. Graf representation. Grundläggande algoritmer på grafer. |
|
| Föreläsning 5. Logiska modeller inom datavetenskap. Algebra av propositioner. booleska funktioner. Normala former. Full klasser av booleska funktioner. Reläkontaktkretsar. Ventiler. Matematiska modeller av processorn och datorns minne. Predikat och relationer. Relationell algebra. Teoretisk grund relationell DBMS. Logiska programmeringsspråk och deras matematiska grund. |
|
| Testarbete nummer 2. | |
| Föreläsning 6. Datortalteori och beräkningsgeometri. Varför behöver du talteori i dator vetenskaper? Kapplöpningen om primtal. Hur faktorisera ett tal? Vad är skillnaden mellan teoretisk geometri och datoranvändning? Varför är det smidigt på pappret, men klumpigt på datorn? Grundläggande regler och algoritmer för beräkning geometri. |
|
| 23/2007 | Föreläsning 7. Skydd av information... Skydd av symbolisk information. Vad behöver skyddas? Elektronisk signatur... System verifiering. Public key kryptosystem. Skydd grafisk information... Matematik för elektroniska vattenstämplar. |
| 24/2007 | Föreläsning 8. Grunderna i undervisningsmetoder för matematiska grunder för datavetenskap. |
| Slutarbete |
Föreläsning 2.
Matematiska modeller av formella artister
"Nåden är kylig i detta fåfänga ljus." Denna fras uppfanns av en dator som använder ett av de första programmen för att skapa texter på naturliga språk. Men känslorna som denna fras förmedlar är naturligtvis otillgängliga för datorn. Och datorn kan inte förstå innebörden av denna fras. För han är bara en formell artist.
I vårt allmänna medvetande har ordet "formell" vanligtvis en negativ klang. Vi belönar en tjänsteman med den föraktfulla stigmatiseringen "formalist" som agerar enbart på grundval av de instruktioner som han fått, utan att vilja fördjupa sig i kärnan av problemet som ställs till honom.
Men är det alltid dåligt att vara en formell artist? Kommer herdens ägare att vara glad när, på kommandot "Fas!" hans fyrbenta vän kommer att fundera på om han ska bråka med banditen. Eller när planet, som svar på rodrets pilots rörelse, fortsätter att flyga samma kurs, eftersom du inte vill göra en U-sväng. Och operatören av en kärnreaktor, som överger instruktionen, kommer att hantera den på ett infall. Håller med om att även en person ibland behöver vara en formell artist. När det gäller enheter för automatisk informationsbehandling är en informell väg helt enkelt omöjlig för dem. Kom ihåg att, som nämnts i föreläsning 1, handlar datavetenskap om studiet av bara processerna automatiserad behandling information.
Informationsbehandling (transformation) är en ganska brett förstådd informationsprocess. Informationsbehandling förstås som att erhålla ny information från befintlig information eller att transformera formen för informationspresentation.
Detektiven samlade bevis och angav vem som begick brottet. Matematikern jämförde de påståenden han kände till och bevisade en ny sats. DI. Mendeleev formulerade den periodiska lagen på basis av information om grundämnens kemiska egenskaper. I alla dessa exempel, som ett resultat av informationsbehandling, dök ny information upp.
Beräkningen av summan av två siffror bör också erkännas som informationsbehandling - trots allt, från två kända data, erhålls en ny, tidigare okänd. Informationsbehandling är till exempel översättning av en mening från ryska till ett främmande språk.
Vid första anblicken, mellan insom anges i de två föregående styckena, stor skillnad... Den största skillnaden här är att för sökandet efter en brottsling eller för att bevisa en ny sats finns det inga och kan inte specificeras strikta regler för hur den initiala informationen ska behandlas. Som de säger, personen i dessa fall agerar heuristiskt... Genom att lägga till två siffror styrs vi redan av strikt specificerade regler. Sådant arbete kan anförtros en teknisk anordning som är kapabel att förstå och utföra de instruktioner som föreskrivs för den. Enheter som styrs av instruktioner och som gör sitt jobb automatiskt kallas programmerbara och sägs göra sitt jobb formellt.
I synnerhet kan vi prata om den formella behandlingen av information. Den utförare som utför sådan bearbetning bör inte fördjupa sig i innebörden av de handlingar som utförs av honom; därför gäller den formella behandlingen av information som regel förändringen i formen av dess presentation och inte innehållet.
Så det är bekvämt att förstå behandlingen av information som varje transformation av dess innehåll eller form av presentation.
Men oavsett sätt att bearbeta information - formell eller heuristisk, finns det något eller någon som utför denna bearbetning. Det brukar kallas artist.
Formella artister kan arrangeras på väldigt olika sätt. För att studera dem, som i vilken vetenskap som helst, används modellering. Vilka matematiska modeller som används för att studera formella artister kommer vi att berätta i denna föreläsning.
§ 3. Formell utförare: automat
Människan är mycket framgångsrik i att skapa en mängd olika enheter som utför detta eller det arbetet i enlighet med tydliga instruktioner. Samtidigt är han inte längre skyldig att ständigt vara nära den här enheten för att kontrollera den. I det här fallet säger de att enheten gör jobbet automatiskt, och en sådan enhet kallas själv automatisk.
I verkligheten är maskiner väldigt olika. Det kan vara en biljettautomat för pendeltåg, eller en automat för att fylla på färdiga produkter, eller en automat för tillverkning av vilka delar som helst. Automater av den senare typen kallas ofta industrirobotar.
Ur datavetenskapens synvinkel spelar det ingen roll vad maskinen är gjord av. Det enda viktiga är att han uppfattar vissa signaler som kommandon och för varje kommando utför någon handling, går från ett tillstånd till ett annat. Därför kan vi anta att varje automat beskrivs av en uppsättning möjliga tillstånd, en lista med giltiga kommandon och en uppräkning av det tillstånd från vilket automaten passerar under påverkan av varje kommando. Till exempel, om det bara finns två kommandon, kan de betecknas med bokstäver, säg, a och b, eller i siffror, maskinens tillstånd - i bokstäver q 1, q 2, ..., qm, och det är möjligt att räkna upp alternativen för övergången från ett tillstånd till ett annat med hjälp av tabellen (se Tabell 1).
bord 1
Cellen i skärningspunkten mellan en rad och en kolumn indikerar det tillstånd som automaten går in i, som var i det tillstånd som anges i rubriken till samma kolumn och fick kommandot som anges i rubriken på samma rad. Det är klart för alla att en sådan tabell är en informationsmodell av en riktig automat.
Automaten kan även beskrivas av en annan informationsmodell, digrafen *. Spetsen på digrafen är tillstånden för automaten, bågarna är övergångar från ett tillstånd till ett annat. Varje båge har en markering som indikerar vilket kommando övergången görs. Sedan automaten som beskrivs i tabell 2 visas som visas i ris. 1.
Tabell 2
Ett av tillstånden kallas initialtillståndet - det är i det som maskinen är placerad innan arbetet påbörjas. Låt oss komma överens om att alltid beteckna initialtillståndet q 1. Några av tillstånden är slutgiltiga - att föra automaten till detta tillstånd är målet att styra automaten med en eller annan sekvens av kommandon. Till exempel, om det är en tågbiljettautomat, förväntar sig maskinen i initialtillståndet att mynt börjar komma in i myntmottagaren. Det finns två slutliga tillstånd: biljettutfärdande och återbetalning av pengar. Dessutom finns det mellanliggande tillstånd - räknar summan pengar som överförts till maskinen vid detta ögonblick. Kommandon som överför maskinen från ett tillstånd till ett annat är att sänka myntet i myntmottagaren, trycka på biljettutfärdandeknappen eller trycka på pengarna tillbaka-knappen. Det faktum att detta tillstånd är slutgiltigt kommer att betecknas med bokstaven K inom parentes nära beteckningen för detta tillstånd. Till exempel, q 2 (K).
Det är tydligt att syftet med att styra en automat är att ge den en sådan sekvens av kommandon som överför den från ett initialt tillstånd till något slutligt. Eftersom varje kommando betecknas med en bokstav, kan den uppsättning kommandon som den här maskinen förstår betraktas som ett alfabet A... Sedan sekvensen av kommandon, dvs. programmet kommer att skrivas som ett ord i detta alfabet. Till exempel ordet abaöversätter automaten som beskrivs i tabellen. 2, från initialtillståndq 1 i staten q 4 . Man kan säga att ordet aba definierar på digrafen för den givna automaten någon väg från staten q 1 i staten q 4 .
Uppsättningen av alla de ord som överför automaten från initialtillståndet till ett av sluttillstånden bildar ett slags formellt språk. Detta språk kallas språk som känns igen av den här maskinen... Om det för något språk finns åtminstone en automat som känner igen detta språk, så kallas ett sådant språk igenkännlig.
På ris. 2 visar en automat med två tillstånd - q 1 (K) och q 2 - och förstår två kommandon, som betecknas med siffrorna 0 och 1. Det är lätt att ta reda på att språket som känns igen av den här maskinen består av dessa och endast de ord som innehåller ett jämnt antal ettor och valfritt antal nollor. Med andra ord, denna automat beräknar summan av siffrorna i det inskrivna numret binärt system beräkning.
Låt oss nu ha ett fast alfabet A, och L- någon uppsättning ord, sammansatt av symbolerna i det givna alfabetet. Är det alltid möjligt att bygga en sådan automat så att uppsättningen L var det ett igenkännbart språk för honom? Svaret är nej.
Sats. Låt vara A = {a, b}, L = {a n b n, var n intervall över mängden av alla naturliga tal). Mycket av Lär inte ett erkänt språk.
Inspelning ett förekommer i uttalandet av denna sats betyder att bokstaven a upprepas n en gång.
Beviset för satsen använder en av de viktigaste matematiska metoderna - motsägelsefullt. Så anta det L- det erkända språket. Detta betyder att det finns en automat som kan översättas till något slutligt tillstånd av vilket ord som helst på detta språk. Låt denna automat ha k stater. Tänk på ordet a k b k... Det tillhör språket L och överför därför denna automat från initialtillståndet q 1 till något slutligt tillstånd q s. Sedan brevet a upprepas minst lika många gånger som antalet tillstånd för automaten, det finns ett sådant tillstånd q t, som för den första k ansökningar av brevet a kommer att godkännas två gånger (se. ris. 3). Låt automaten gå in i tillståndet för första gången q t som ett resultat av att ansöka ett u, och nästa gång kommer att vara i samma tillstånd efter ansökan ett u + v... Tänk på ordet ett k + v b k... Det är tydligt att tillämpningen av detta ord till det ursprungliga tillståndet q 1 kommer att sätta den i samma slutliga tillstånd q s. Det betyder att det givna ordet också känns igen av den givna automaten och därför måste tillhöra språket L... Men i många L det finns inget sådant ord. Den resulterande motsägelsen visar att det gjorda antagandet är felaktigt, d.v.s. maskin för vilken given uppsättning skulle fungera som ett igenkännbart språk finns inte.
Ris. 3. Rutta på automatdigrafen från utgångsläget q 1 till sluttillstånd q s (att ange q t bokstav a står på bågar u tid, på slingan - mer v en gång)
Eftersom inte varje uppsättning ord är ett igenkännbart språk, uppstår frågan vilka uppsättningar som är lämpliga för detta. Matematiker hittade bekväma sätt beskrivningar av erkända språk, och dessa metoder låg till grund för utformningen av alla för närvarande existerande programmeringsspråk.
Frågor och uppgifter
1. Vilka två informationsmodeller kan en automat representera?
2. Vilket språk känns igen av den här maskinen?
3. Vilket språk kallas igenkännbart?
4. För maskinen som visas på ris. 1, bestäm i vilket tillstånd det kommer att vara efter utförandet av en sekvens av kommandon
a) abba; v) babaabaaa;
b) ababbabbb; G)* a n b n.
5. För maskinen som visas på ris. 2, gör en beskrivning i form av en tabell.
6. Rita som en graf informationsmodell maskinen som anges i tabellen. 3.
Tabell 3
7. Vilket språk över ett alfabet med två bokstäver (0, 1) känns igen av maskinen som visas i ris. 4?
Ris. 4
8. Vilket språk över alfabetet med två bokstäver ( a, b) känns igen av automaten som anges i tabellen. 3?
9. Rita i form av en graf informationsmodellen för en automat som skulle känna igen ett språk över alfabetet (0, 1), bestående av alla ord som innehåller exakt 5 på varandra följande ord.
10. Rita i form av en graf informationsmodellen för en automat som skulle känna igen ett språk över alfabetet (0, 1), bestående av alla ord som innehåller exakt 5 enheter.
11. Avbilda i form av en graf informationsmodellen för en automat som skulle känna igen ett språk över alfabetet (0, 1), bestående av alla ord som börjar med ett (det vill säga denna automat skiljer naturliga tal skrivna i ett binärt tal system från godtyckliga sekvenser tecken 0 och 1).
12. Bland språken nedan L 1 , L 2 , L 3 , L 4, definierat över ett alfabet med två tecken (1; 2), indikerar vilka som känns igen. För vart och ett av de erkända språken, bygg en automat som känner igen det; för vart och ett av de oigenkännliga språken, bevisa att det är oigenkännligt.
a) L 1 består av alla ord som är jämna naturliga tal som börjar med talet 1;
b) L 2 består av alla ord, antalet enheter i vilket ett naturligt tal som slutar på siffran 3;
v) L 3 består av alla ord där antalet tvåor är ett primtal;
G) L 4 består av alla ord som är naturliga tal delbara med 3.
13. Vad är skillnaden ur informatikens synvinkel "i livet enligt lagarna" och "i livet enligt begreppen"?
§ 4. Universell utövare
Datorspel ... Förmodligen har alla som någonsin sysslat med en dator sett, och möjligen själv, spelat vilket datorspel som helst. På skärmen lyder vissa föremål i form av levande varelser eller tekniska enheter spelarens kommandon, andra styrs av en dator som utför förinställt program... Alla dessa objekt är formella exekutörer, var och en med sin egen uppsättning tillåtna handlingar. Endast dessa objekt är inte verkliga, utan simulerade av en dator. Det visar sig att med hjälp av en formell artist imiteras andra.
Om du försöker formulera vad det innebär att en artist imiteras med hjälp av en annan får du följande. De säger att en formell artist A imiterar en formell artist V, om
Till varje objekt som utföraren utför åtgärder på V, motsvarar otvetydigt det objekt på vilket exekutören utför åtgärder A(imitation av artistens miljö);
Till varje tillåten handling av artisten Vöver ett eller annat föremål i miljön är den utövandes tillåtna handling entydigt förknippad Aöver motsvarande föremål för sin omgivning (imitation av handlingar);
Varje instruktion skriven för artisten V och att under dess verkställande leda till ett visst resultat (d.v.s. till ett visst tillstånd av bosatts omgivning och honom själv), kan genom imitation av tillåtna handlingar omvandlas till en instruktion för verkställaren. A, vars utförande leder till motsvarande resultat i utförarens miljö A.
Men antagandet att de utövande A och V den olika miljön där de finns är inte i grunden ur informationssynpunkt. Till exempel artisten A handlar om siffror och V omvandlar grafiska bilder... Men du vet redan att vi faktiskt i vart och ett av dessa fall talar om att transformera korrekt kodad information. Dessutom kan det antas att samma binära kod används. I denna mening kan vi anta att artistens miljö helt enkelt är densamma – information presenterad i form av ett kodat meddelande.
En av de viktigaste frågorna inom teoretisk datavetenskap är: finns det en sådan formell artist med hjälp av vilken vilken som helst formell artist kan imiteras? Det är naturligt att kalla en sådan artist universell... Det är lätt att förstå att som en fysisk enhet existerar inte en universell exekutor - trots allt kan information kodas i alla långa meddelanden, och vilket fysiskt medium som helst är ändligt. Om vi talar om en universell utförare som ett idealiskt objekt, så visar det sig att svaret på frågan är ja. Och det erhölls nästan samtidigt och oberoende av två framstående vetenskapsmän - A. Turing (1936) och E. Post (1937). De artister de föreslog skilde sig från varandra, men det visade sig att de kunde imitera varandra, och viktigast av allt, imitera vilken formell artist som helst i allmänhet.
Det är vanligt att kalla en universell utförare för en maskin. Det är också vanligt att ge maskiner namnen på deras uppfinnare. Så den universella artisten som uppfanns av A. Turing kallas Turing-maskinen; utföraren som beskrivs av E. Post är Posts maskin. Senare dök andra universella artister upp, till exempel Minsky-maskinen.
Så vi kan anta att vi har ett meddelande skrivet i något alfabet, och det måste konverteras till ett annat meddelande. Att skriva en instruktion till en formell exekutor att bearbeta ett specifikt par meddelanden är naturligtvis inte en knepig sak. Men du vet redan att instruktioner (dvs. algoritmer) som tillåter att lösa en hel klass av problem av samma typ - den så kallade "massaegenskapen hos en algoritm" är av verkligt intresse. Till exempel, en sådan uppgift: att tilldela till höger ytterligare ett fördefinierat tecken till ett meddelande. Om, säg, en sekvens av identiska tecken fungerar som koden för ett naturligt tal - antalet tecken i sekvensen är det kodade naturliga talet - så pratar vi faktiskt om att skapa en algoritm för att öka antalet med 1.
Det är naturligt att tro att meddelandet är inspelat på bandet. Dessutom är det bekvämt att föreställa sig detta band uppdelat i identiska celler, och varje cell innehåller exakt en meddelandesymbol. Eftersom meddelanden kan vara hur långa som helst, är vi överens om att föreställa bandet som oändligt. Tomma celler anses vara fyllda med ett blanksteg. Därför deklarerade vi att alla alfabet som kommer att användas av oss för att skriva meddelanden på detta band måste innehålla ett "mellanslag". Låt oss komma överens om att utse den a 0. Resten av tecknen i alfabetet som används för att spela in meddelanden på band kommer att anges a 1 , a 2 , ..., a n. Om vi till exempel behöver skriva ner problemet med att beräkna summan av två tal, kan alfabetet tas enligt följande: a 0; 1; 2; 3; 4; 5; 6; 7; åtta; nio; 0; ,; +; =. För ett specifikt datapar (dvs två siffror) kan en bandpost se ut som till exempel som visas i ris. 5.
Ris. 5
Vi kommer naturligtvis inte att skriva symbolen på bandet i tomma celler a 0, menar det där. Dessutom är vi överens om att det första tecknet i meddelandet, förutom ett mellanslag, alltid visas i samma cell - på ris. 4 är den markerad med Ї. Denna cell kommer att kallas den första.
Meddelandet som spelas in på bandet bearbetas av någon enhet, och resultatet skrivs tillbaka till bandet. Eftersom artisten är formell fördjupar han sig inte i budskapets innebörd, utan enligt instruktionerna som sammanställts för honom byter han ut vissa symboler med andra. Vi är inte intresserade av hur en sådan ersättning fysiskt utförs, så vi kan föreställa oss att en viss automat rör sig längs bandet, som läser ett tecken från en cell på bandet, bearbetar den mottagna informationen, skriver ut ett annat tecken i cellen ( om det föreskrivs av instruktionen) och flyttar till den närliggande cellen - höger eller vänster.
Du vet redan att varje automat beskrivs av en uppsättning tillstånd. Det är vanligt att beteckna tillstånden för den specificerade läsaren-utskriftsmaskinen med bokstäver q 0 , q 1 , q 2 , ..., q m. I det här fallet är vi överens om att när maskinen slås på, d.v.s. i början av arbetet är det alltid i samma tillstånd, vilket vi kommer att beteckna q 0, och är placerad mittemot startcellen.
Således beskrivs en Turing-maskin formellt av en uppsättning av två alfabet: A = {a 1 , a 2 , ..., a) och F = {q 0 , q 1 , q 2 , ..., q m). Alfabet A kallad extern och tjänar till att spela in de ursprungliga meddelandena, alfabetet F kallad inre och beskriver en uppsättning tillstånd för läsaren-utskriftsanordningen. Vi kommer att avbilda Turing-maskinen som visas i ris. 6.
Ris. 6
På ris. 6 visar driftögonblicket för Turing-maskinen, när läs-utskriftsanordningen övervakar den tredje cellen från den första (vid det ögonblicket fanns en symbol och s 3) och är i staten q k.
Så, Turing-maskinens tillåtliga åtgärder är följande:
Skriv valfritt tecken i det externa alfabetet i avsnittet på bandet (tecken som fanns där tidigare skrivs över);
Flytta till en intilliggande sektion;
Ändra tillståndet till en av symbolerna som anges av det interna alfabetet;
Sluta arbeta (stoppa).
Naturligtvis, i denna uppräkning anges inte en åtgärd på varje rad, utan en grupp av handlingar av samma typ - handlingar "skriv ner symbolen för det externa alfabetet" lika många som dessa symboler, du kan gå till nästa avsnitt till höger eller till vänster finns det lika många åtgärder för att ändra tillståndet som dessa tillstånd (dvs. hur många tecken i det interna alfabetet).
Nu måste vi säga hur kommandona för att utföra de angivna åtgärderna registreras. Varje kommando på maskinen innehåller högst en åtgärd från varje grupp av åtgärder och har formen
Faktum är att kommandona ser ut så här:
ett i q j - skriv till avsnittet som granskas a i, flytta till höger (till nästa avsnitt) och gå till staten q j;
ett i q j - skriv till avsnittet som granskas a jag, flytta till vänster och gå till staten q j;
a i S q j - skriv till avsnittet som granskas ai, stanna och gå till staten q j.
För att utföra åtgärder har Turing-maskinen en operationell-logisk enhet. Detta block har två ingångar: genom en av dem mottas information om vilken symbol som finns i den övervakade cellen, genom den andra - information om maskinens tillstånd i detta skede av dess arbete. Denna information bestämmer unikt vilket kommando maskinen ska köra. Eftersom kommandot kan innehålla en indikation på exekveringen av tre åtgärder - att skriva ett tecken till bandet, ändra och ändra tillståndet - har det operationella-logiska blocket tre utgångar: att skriva ett tecken A, offset M och byte av stat F(centimeter. ris. 7).
Ris. 7. Operationellt-logiskt block av Turing-maskinen
Eftersom detta block bara har två ingångar, är det bekvämt att representera dess reaktion på tecken som tillförs dem i form av en rektangulär tabell, där rader och kolumner är märkta med symboler för de externa respektive interna alfabeten (se tabell 4) . Kommandon skrivs till cellerna i tabellen. Om bilen står mitt emot cellen där det står skrivet ett i, och dess tillstånd är q j, sedan utförs kommandot vid skärningspunkten för linjen markerad med symbolen ai, och kolumnen markerad med q j.
Tabell 4
Denna tabell kallas funktionsdiagram den här maskinen; den spelar också rollen som en instruktion (program) för Turing-maskinen. Från den kan du i synnerhet se vilka externa och interna alfabet i maskinen.
Anta till exempel att en sekvens med en viss mängd av samma "*"-tecken skrivs på ett band. Sedan funktionsdiagrammet som visas i tabellen. 5 får Turing-maskinen att öka antalet stjärnor i den sekvensen med en.
Tabell 5
Det är omöjligt att bevisa att en Turing-maskin är en universell exekutor. På samma sätt är det till exempel omöjligt att bevisa lagen om energibevarande i fysiken. Men bruket att kompilera algoritmer visar att alla problem som en person kan lösa idag kan programmeras på en Turing-maskin. Detta experimentella faktum, som kallas Turing-uppsatsen, formuleras enligt följande: för ett problem finns det en lösningsalgoritm om och bara om det finns en lämplig Turing-maskin med hjälp av vilken detta problem kan lösas.
Frågor och uppgifter
1. Vilken formell artist kallas universell?
2. Vad är en Turing-maskin?
3. Hur skiljer sig en Turing-maskin från en annan?
4. Vad kallas ett funktionsdiagram av en Turing-maskin?
5. Är det sant att en Turing-maskin med ett funktionsdiagram skrivet för den är en finit automat?
6. Visa i form av en figursekvens hur informationen på bandet förändras under driften av Turingmaskinen, beskrivet av funktionsdiagrammet i tabellen. 5.
7. Följ funktionsdiagrammet som beskrivs i tabellen. 5 tillskrivs Turing-maskinen given sekvens asterisker ytterligare en asterisk till vänster. Rita ett funktionsdiagram enligt vilket en asterisk kommer att tilldelas till höger om den givna sekvensen.
8. Turingmaskinens funktion beskrivs med följande funktionsdiagram:
Bestäm vilket meddelande som kommer att finnas på bandet efter slutet av maskinens arbete och ange mittemot vilken cell för närvarande dess skrivblock kommer att finnas.
Ris. åtta
Ris. nio
9. Bandet på Turing-maskinen innehåller en rad som består av flera på varandra följande tecken "*", följt av flera tecken "#", och i slutet av raden finns ett tecken "e" (en av möjliga alternativ en sådan rad ges på ris. 5).
Ris. tio
Bestäm för vart och ett av funktionsdiagrammen nedan vilken uppgift den är utformad för att lösa. (Tips: för att få ett övertygande svar, tillämpa funktionsdiagrammet på olika alternativ för att fylla nyhetsflödet med teckensekvenser från det externa alfabetet.)
10. Låt det yttre alfabetet bestå av symbolen " a 0 ”och siffrorna 0, 1, 2, ..., 9. Ett naturligt tal skrivs på bandet. Tänk på en Turing-maskin och gör ett funktionsdiagram för den, enligt vilket detta antal kommer att ökas med 1.
11. Låt det yttre alfabetet bestå av symbolen " a 0 ”och siffrorna 0, 1, 2, ..., 9. Ett naturligt tal skrivs på bandet. Gör ett funktionsdiagram för Turing-maskinen, med hjälp av vilken summan av siffrorna i detta nummer kommer att skrivas på bandet. Svaret måste skrivas till höger om originalnumret, separerat från det med ett mellanslag.
Ris. 11
P.S. Att känna sig som en Turing-maskin är nyttigt, men tröttsamt. Vi rekommenderar att du gör uppgifterna 8 och 9 manuellt. För uppgifterna 10 och 11 kan manuell testning av de funktionsdiagram du har ritat vara ineffektiv. I detta avseende föreslår vi att använda datorimplementeringen av Turing-maskinen, skapad av R. Zartdinov. Den kan erhållas på hemsidan för tidningen "Informatika" ( inf.1september.ru). Så här ser till exempel funktionsdiagrammet från uppgift 8 c) ut på den här bilen - skillnaderna är att det istället för bokstaven S finns ett vägmärke och istället för symbolen " a 0 ”skrivs” _ ”(när du anger ett kommando i cellen i tabellen, tryck dock på” blanksteg ”, inte” _ ”). Programmet är försett med detaljerad hjälp om hur man arbetar med det. Gränssnittet för detta program är mycket enkelt. Dessutom finns en beskrivning av denna implementering av Turing-maskinen i tidningen "Informatika" nr 8, 2006. Där hittar du också en analys av ytterligare flera problem för programmering av en Turing-maskin; du behöver bara komma ihåg att de använder ett lite annorlunda (vilket är helt oviktigt) kommandosystem.
* Kom ihåg att en graf är en samling punkter som kallas toppar och linjer som förbinder några av hörnen. Om riktningen anges på linjerna som förbinder hörnen, anropas grafen orienterad(förkortad digrafera), och linjerna kallas det bågar... I en vanlig graf, dvs. oriktade kallas linjerna som förbinder hörnen revben... Mer om grafer kommer att diskuteras i föreläsning 4.
Huvudfrågan är:?
Vägledande frågor:
§ Vilka typer av artister finns det?
§ Vad kännetecknar artisten?
§ Hur får entreprenören att förstå och utföra algoritmen?
Forskningsmål:
§ Hitta exempel på olika konstnärer.
§ Bestäm hur artisterna skiljer sig åt.
§ Ta reda på vad artisterna kännetecknas av.
§ Undersök varför exekutorer inte alltid kan exekvera algoritmen.
§ Ge exempel på algoritmer och bestäm executorn i dem.
Exempel på artister
En ny garderob togs till huset ... Det vill säga, det finns ingen garderob som sådan, dörrar, hyllor, skruvar och andra detaljer om den framtida behållaren med kläder och linne läggs ut på golvet. Min far och jag följer efter detaljerade instruktioner, låt oss börja montera. Här fungerar instruktionen som en algoritm, och min far och jag fungerar som dess utförare.
I matematiklektioner utför vi olika beräkningar - vi multiplicerar och dividerar med en kolumn, lägger till enkla bråk. I dessa fall är vi utförare av motsvarande algoritmer.
Men en artist kan inte bara vara en person. Olika enheter, inklusive en dator, kan också köra de algoritmer som specificeras av den. Till exempel, Lunokhod, ett självgående automatiskt fordon som levererades till månen 1970, utförde komplexa algoritmer, rörde sig längs månens yta och samlade information som var nödvändig för människor. Industrirobotar ersätter människor i produktionen, i vardagen kommer apparater som kan agera enligt givna algoritmer också till hjälp för hemmafruar.
Skådespelare från sagor
Skådespelare finns ofta i sagor. I en av dem säger Ivan Tsarevich till Hut-On-Chicken-Legs: ”Hut, hut! Stå med ryggen mot skogen, framför mig!”. I det här fallet måste kommandot specificeras mycket exakt så att utföraren förstår det. I sagan "Ali Baba och de fyrtio tjuvarna" öppnades den magiska dörren med kommandot "Sesam, öppna!". Den girige Kasym, som i hemlighet gick in i grottan, glömde denna fras och kunde inte lämna grottan.
Både Hut-On-Chicken-Legs och den magiska dörren har mycket gemensamt: de vet hur man förstår och utför några exakt inställda kommandon, det vill säga de är utförare.
Vad är en artist?
Algoritmens exekutor är en levande varelse eller ett tekniskt objekt som kan utföra de åtgärder som föreskrivs av algoritmen.
Artister kan vara:
§ maskiner: verktygsmaskiner, robotar, Vitvaror(tvättmaskin, bandspelare, spelare etc.), datorer;
§ växter: solros (viker ut sig i solen), näckrosor (stänger på natten);
§ djur: tränad hund (ordning, eftersök, jakt), katt;
§ personer: student, arbetare, soldat, lärare, ...
Är alla artister likadana?
Djur och människor som artister skiljer sig från alla andra artister i tre huvuddrag:
§ De förstår kommandon på olika sätt (till exempel "Sätt dig!", "Sätt dig ner!", "Sätt dig ner!").
§ De kan vägra att utföra kommandot om de inte gillar det ("Ät mannagryn!", "Skjut ut genom fönstret med en slangbella!", "Ge benet!"). Det vill säga att en person, och i viss mån ett djur, har en vilja och ansvarar för sina handlingar.
§ Dom kan annan tid utför samma kommandon på olika sätt (du kan till exempel tvätta golvet med händerna, eller så kan du använda en mopp).
Skådespelare är av två slag!
Låt oss nu tänka på den här frågan: eftersom artisterna skiljer sig åt i vissa av sina egenskaper, borde de då inte delas in i två klasser? Då är det inte svårt att gissa att djur och människor kommer att hamna i en klass, och alla andra artister i en annan. Det återstår att bestämma hur man ska namnge dessa klasser och bestämma vilka egenskaper artisten måste ha för att komma in i den eller den gruppen.
Formellt och informellt
För att göra detta, låt oss komma ihåg en av algoritmens egenskaper, nämligen formalitet, det betyder att utföraren kanske inte förstår innebörden av algoritmen, men ändå utför den korrekt ... Kan en person eller ett djur alltid göra detta? Förmodligen inte, därför kan man inte säga att de exekverar algoritmen formellt, så vi kommer att anta att människa och djur är informella exekutörer.
Så, genom att utföra algoritmen, kanske artisten inte fördjupar sig i innebörden av vad han gör och ändå får det önskade resultatet. I sådana fall säger de att artisten agerar formellt, det vill säga att han distraheras från innehållet i den aktuella uppgiften och endast utför alla åtgärder i en strikt sekvens. Det här är en formell artist.
Om en utförare gör några ändringar i algoritmen (ändrar sekvensen av steg; hoppar över några, eftersom de anser att de är onödiga eller obetydliga), så säger de att en sådan utförare inte är formell.
Utförandeegenskaper
Utövaren, som alla föremål, har sina egna egenskaper.
Utövaren kännetecknas av:
§ SKI (utförarens kommandosystem) - en uppsättning kommandon som utföraren förstår och kan utföra.
Varje exekutor kan endast utföra kommandon från en viss strikt specificerad lista.
§ Miljö - de förhållanden under vilka utföraren kan utföra kommandon. Artistens miljö kan också kallas hans "Habitat".
§ Och undantag:
1. "Jag förstår inte" - detta kommando finns inte i listan över utförarens kommandon, och han förstod det inte. Förmodligen gjorde vi ett misstag när vi skrev kommandotexten, kommandot ingår inte i SKI.
2. "Jag kan inte" - utföraren förstod kommandot, men kan inte utföra det. Roboten får till exempel kommandot "framåt", men det finns en vägg framför och den kan inte gå. Eller så fick hunden kommandot "Sitt!" Och hon satt redan.
Hur kommer utföraren att exekvera algoritmen?
Utövaren kommer att kunna exekvera algoritmen om han kan den, om han fick veta algoritmen. För människor är språket det viktigaste kommunikationssättet. Att komma in i ett främmande land och inte kunna det nationella språket, visar sig en person vara helt hjälplös. Teckenspråk, ansiktsuttryck, skrivande med hjälp av ritningar (pictographic skrift) kan komma till undsättning, men allt detta förbättrar bara delvis situationen.
Ett naturligt språk (ryska, engelska, franska, ...) är grunden för fullvärdig kommunikation mellan människor.
Naturliga språk är bildliga och tvetydiga. Om du tittar i den förklarande ordboken för det ryska språket kan du till exempel ta reda på att det finns mer än 20 betydelser av ordet "gå". Här är bara några exempel: �En person går längs vägen; det regnar; tiden går; den här klänningen passar henne; honungssvampar kommer att gå senare, i september; ska vi fiska imorgon? - går!
I naturligt språk kan helt olika begrepp betecknas med samma ord. Som regel väljer en person från den allmänna betydelsen av texten, ibland utan att ens tänka, från hela uppsättningen av betydelser av ordet, exakt den som avsändaren av meddelandet hade i åtanke. Men föreställ dig själv i stället för en formell artist som inte fördjupar sig i hela budskapets innebörd. Hur ska du i det här fallet förstå fraserna: sur min; tidig flykt; åt överallt; bekant miljö?
För att försäkra oss om att språket hos en formell entreprenör inte kan vara polysemantiskt försökte vi med hjälp av en formell översättare att från engelska översätta en text om ... Försök gissa vad det handlar om.
Träaffärer idag är - det dog - skärs från tallplywood och doppas sedan i flytande kemikalier som producerar lätteldade, lösbara råd.
Och det handlade om en enkel trätändsticka, men hur var det att förklara för översättaren att från alla betydelser av ordet "match" var det nödvändigt att välja inte "deal", utan "match", från betydelsen av ordet "tips" - "tips" och inte "råd "att" dö "inte bara betyder" dö "utan också" stämpel ", för att inte tala om komplexiteten i grammatiska konstruktioner?
Vad är ett program?
För en formell artist kan kommunikationsspråket inte vara polysemantiskt; för sådana artister utvecklas och används speciella konstgjorda språk, där enstaka ord och uttryck är inte föremål för olika tolkningar.
En algoritm som beskrivs på exekutorns språk kallas ett program.
För att lära dig hur man skriver program på ett eller annat språk måste du studera alfabetet, ordförrådet och grammatiska regler som meningar på detta språk är uppbyggda efter, medan inga avvikelser från reglerna för att skriva ord och meningar är tillåtna, annars kommer den som utövar vägra helt enkelt att följa dina instruktioner och blir inte förvirrad och orolig över misstag, som Mishkas vän gör från A. Shibaevs dikt:
Ett brev kom till mig
Jag ser -
Från lägret från Mishka ...
Här är en underbar rosett och jag slickar
-Skrivet i ett brev.
Slickar bågen? Vilken typ av mirakel?
Förmodligen skämtar fusket...
Jag läser vidare:
Här är en räv, ett vackert långt spö ...
Häromdagen hittade jag sorg i skogen
och blev väldigt nöjd...
Nej, nej, han skämtar inte! Jag är rädd,
Min vän är allvarligt sjuk.
Returer - måste behandlas:
Låt reglerna lära...
§ Utövande är av två typer: formella och icke-formella.
§ Utövaren kännetecknas av ett kommandosystem, livsmiljö och avslag.
§ För att artisten ska förstå oss är det nödvändigt att skriva en algoritm på artistens språk, det vill säga att skriva ett program.
| Lektionsplanering och lektionsmaterial | 6 betyg | Planera lektioner för läsåret (FSES) | Skådespelare runt omkring oss
Lektion 24
Skådespelare runt omkring oss
Arbeta i miljön för artisten Grasshopper
Formella artister
Formella artister
Det finns två typer av artister: formella och informella. Den formella exekutorn utför alltid samma kommando på samma sätt. En informell utförare kan utföra ett kommando på olika sätt.
Om du till exempel lyssnar på en skiva med din favoritmusik många gånger kan du vara säker på att den spelas av spelaren (formell artist) på samma sätt. Men knappast någon av sångarna (en informell artist) kommer att kunna framföra en låt från sin repertoar på exakt samma sätt flera gånger.
Som regel agerar en person som en informell artist. De formella genomförarna är till övervägande del tekniska anordningar. En person i rollen som en informell artist är själv ansvarig för sina handlingar. Objektet som kontrollerar honom är ansvarigt för den formelle verkställande direktörens handlingar.
Låt oss överväga mer i detalj uppsättningen av formella artister. Formella artister är ovanligt olika, men för var och en av dem kan du specificera omfattningen av uppgifter som ska lösas, miljön, kommandosystemet, felsystemet och driftsätt.
1. En rad uppgifter som ska lösas... Varje artist är skapad för att lösa en viss klass av problem.
2. Konstnärsmiljö... Området, miljön, förhållandena där artisten verkar kallas vanligtvis den givna artistens miljö.
3. Exekutors ledningssystem... Ordern att utföra en separat genomförd åtgärd av utföraren kallas ett kommando. Helheten av alla kommandon som kan utföras av en viss utförare bildar SKI - ett system av utförares kommandon.
4. Exekutors avslagssystem... Avslag "Jag förstår inte" uppstår när utföraren får ett kommando som inte ingår i hans SKI. Avslag "Jag kan inte" uppstår när ett kommando från SQI inte kan utföras av den under specifika miljöförhållanden.
5. Operatörens driftlägen... För de flesta artister finns det direkta och programmerade kontrolllägen. I det första fallet väntar exekutorn på kommandon från kontrollobjektet och utför omedelbart varje mottaget kommando. I det andra fallet får exekutorn först en komplett sekvens av kommandon (program), och sedan utför han alla dessa kommandon i automatiskt läge... Ett antal artister arbetar bara i ett av dessa lägen.
Konstnär - en person, en grupp människor, ett djur eller teknisk anordning kan utföra en specifik uppsättning kommandon. Exempel: Objekt - utförare !! Ström på/av-knapp på datorns hölje Gå till början Pausa Stopp Gå till slutet Spela Utövarens kommandosystem - CD-spelare
Mer komplex artist. Fungerar på program skapade av människan. Programmet väljs av personen. Maskinen fungerar automatiskt. Mer komplex artist. Fungerar på program skapade av människan. Programmet väljs av personen. Maskinen fungerar automatiskt. Entreprenör - tvättmaskin
Informella och formella artister Den informella artistens roll är oftast en person Den formella artistens roll är oftast den tekniska enheten Den informella artisten ansvarar för sina handlingar Den formella artistens handlingar är föremålet som kontrollerar honom.
Formell executor En formell executor utför alltid samma kommando på samma sätt. Automatisk fyllnings- och förpackningsmaskin För varje formell entreprenör kan du specificera: antal uppgifter som ska lösas; onsdag; kommandosystem; felsystem; driftlägen.
Avslagssystem av utförare Avslaget ”Jag förstår inte” uppstår om ett kommando ges som inte ingår i SKI. Avslag "Jag kan inte" uppstår om ett kommando från SQI inte kan utföras under specifika miljöförhållanden. ? Bricka kan inte utföra sköljkommandot om maskinen inte är försedd med vatten. ?
Automatisering är att ersätta en del av mänskligt arbete med en maskins arbete: processen att lösa ett problem presenteras i form av en sekvens av enklaste operationer; en maskin skapas som kan utföra dessa operationer i en given sekvens; exekveringen av algoritmen anförtros en automatisk enhet; en person är befriad från rutinmässiga aktiviteter. Automatisering
Det viktigaste är att exekutorn är en person, en grupp människor, ett djur eller en teknisk anordning som kan utföra de givna kommandona. Den formella exekutorn utför alltid samma kommando på samma sätt. För varje formell entreprenör kan du specificera: - vilka uppgifter som ska lösas; - Onsdag; – System av kommandon; – System av misslyckanden; – Driftlägen.
Algoritmexekutorer. Formell exekvering av algoritmen. Dator som en formell exekutor av algoritmer (program).
Lektionstyp: kombinerad.
Lektionens mål:
Introducera begreppet "exekutorobjekt";
Att bekanta eleverna med det tredje steget av algoritmutveckling;
Introducera konceptet "Program";
Introducera reglerna för att utforma och anropa programmet;
Att lära ut hur man löser problem för att göra upp program med en linjär algoritm.
Lektionens mål:
Kognitiv :
Att organisera elevernas arbete med studier och primär konsolidering av kunskap genomkollektiv och oberoende praktisk verksamhet.
Utvecklande:
Med hjälp av ett integrerat förhållningssätt, visa eleverna vilken betydelse begreppet "performerobjekt" har i naturen, vardagen, tekniken och vardagen.
Att säkerställa utveckling av elevers färdigheter som bidrar till utveckling av minne, logiskt tänkande och användning av befintliga kunskaper och färdigheter vid utarbetande av program i ett programmeringsspråk.
Pedagogisk:
Bildning informationskultur, förmågan och färdigheterna för kollektiv och oberoende behärskning av kunskap;
Att främja en talkultur när man svarar vid tavlan, respekt för alla deltagare i utbildningsprocessen.
Under lektionerna
Organisationsstadiet
Ömsesidiga hälsningar från läraren och eleverna; fixa det frånvarande; kontrollera det yttre tillståndet i klassrummet; kontrollera elevernas beredskap för lektionen; organisation av uppmärksamhet och intern beredskap.
Meddelande om ämnet och målen för lektionen. Upprepning av material
Idag i lektionen kommer vi att fortsätta att studera tekniken för att lösa problem med hjälp av en dator. Vi har redan träffat dig konceptet med en algoritm och dess egenskaper. Och innan vi går vidare till studien av nytt material kommer vi att kontrollera din beredskap för lektionen.
Frontalundersökning:
Lista stadierna för att lösa problemet med hjälp av en PC (ställa in problemet, bestämma villkoren, bygga en modell av problemet, beskriva algoritmen för att lösa problemet, välja den optimala miljön för lösningen, beskriva algoritmen med den valda mjukvaruverktyg, testa lösningen på problemet, om nödvändigt - korrigering av lösningen på problemet)
Lista de viktigaste egenskaperna hos algoritmen (diskret, noggrannhet, begriplighet, masskaraktär, effektivitet)
Lista de viktigaste formerna för presentation av algoritmer (verbal, grafisk, programmatisk, tabellform)
Förklaring av det nya materialet:
Algoritmer för att lösa olika problem måste vara genomförbara i den miljö där det är nödvändigt för att få resultatet. I den här miljön måste det finnas ett objekt som kommer att exekvera algoritmen. Låt oss titta på ett exempel. Petya ville ha te. Han kokade vatten i en tekanna, lade en tepåse i en kopp, hällde kokande vatten i den, tillsatte två teskedar socker, rörde om dem med en sked och drack sitt te med nöje. Låt oss formulera algoritmen för Petyas handlingar i form av ett flödesschema (läraren kallar eleven till svarta tavlan).
I det här exemplet utförs alla dessa åtgärder av Petya, därför är han objektet som exekverar algoritmen. Petya vet hur och kan utföra de åtgärder som anges i algoritmen. Den utför dessa åtgärder i den ordning som visas. Objektet som exekverar algoritmen kallasartist .
Skilja mellan formella och informella artister. En formell exekutor utför samma kommando på samma sätt. En informell utförare kan utföra ett kommando.
Formella artister är ovanligt olika, men för var och en av dem kan följande egenskaper specificeras: utbudet av uppgifter som ska lösas (ändamål), miljö, ledningssystem och driftsätt.
En rad uppgifter som ska lösas. Varje artist är skapad för att lösa ett visst antal uppgifter - bygga kedjor av symboler, utföra beräkningar, rita ritningar på ett plan och så vidare.
Konstnärsmiljö - villkor under vilka exekvering av algoritmen är möjlig.
Performer Command System (SKI) - en lista över handlingar som utföraren kan förstå och utföra.
Systemet med artisters vägran är en lista över vägran som inträffar när det är omöjligt att exekvera algoritmen under specifika förhållanden.
Operatörens driftlägen - direkt och programmerat styrläge. Direkt kontroll - utföraren förväntar sig ett kommando från en person och utför varje kommando omedelbart. Programkontroll - executorn ges en sekvens av kommandon (program), och utför sedan kommandona i automatiskt läge. Vissa artister arbetar bara i ett av lägena.
De artister som stöter på i problemen är "Gräshoppa", "Calculator", "Pendel", "Turtle", "Arrow", "Dyer", "Arrow", "Turtle", "Aquarius" etc. dr.
Exempel: Artist En sköldpadda rör sig på datorskärmen och lämnar ett spår i form av en linje. Kommandosystemet består av följande kommandon:
Framn(varn- heltal) - orsakar rörelse pånsteg i rörelseriktningen - i den riktning som hennes huvud och kropp är utplacerade.
Högerm(varm- ett heltal) - orsakar en förändring i rörelseriktningen genommgrader medurs.
Record RepeteraK [<Команда1> <Команда2> … <Команда n>] - betyder att sekvensen av kommandon inom parentes kommer att upprepasken gång.
Tänk på vilken form som kommer att visas på skärmen efter att sköldpaddan har utfört följande algoritm:
Upprepa 12[ Höger 45 Framåt 20 Höger 45]
Svar:
Exempel: Kommandosystem Miniräknaren består av två kommandon som tilldelas nummer:
1 - subtrahera 1
2 - multiplicera med 3
När du spelar in algoritmen, för korthetens skull, anges endast kommandonumren. Till exempel betyder algoritm 21212 följande
Multiplicera med 3
Subtrahera 1
Multiplicera med 3
Subtrahera 1
Multiplicera med 3
Denna algoritm omvandlar talet 1 till 15: ((1 * 3-1) * 3-1) * 3 = 15
Exempel: Executor Roboten arbetar på ett rutigt fält, mellan de intilliggande cellerna där det kan finnas väggar. Roboten rör sig runt cellerna i fältet och kan utföra följande kommandon: upp, ner, höger, vänster.
När varje sådant kommando exekveras, flyttar roboten till en intilliggande cell i angiven riktning. Om det i denna riktning finns en vägg mellan cellerna, förstörs roboten.
Vad händer med roboten om den utför en sekvens av kommandon: höger, ner, höger, ner, höger. Utgående från cell A. Vilken sekvens av kommandon ska roboten utföra för att flytta från cell A till cell B utan att kollapsa från att möta väggarna?
Algoritmen som presenteras på ett språk som är förståeligt för entreprenören kallasprogram .
Program - en ordnad sekvens av kommandon (instruktioner), nödvändigt för datorn för att lösa problemet.
Den största svårigheten med att utveckla program för en dator ligger just i att skapa eller hitta en algoritm. Att komponera ett program enligt en välkänd algoritm kallas kodning.
Programmering (kodning) - processen att kompilera ett program för en dator.
Varje algoritm som presenteras i form av ett program måste ha ett unikt namn som inte sammanfaller med orden som är inbyggda i språket. Programmet har en titel som anger dess namn. Den nya algoritmen sparas i datorns minne under sitt eget namn, och den kan anropas (exekveras) genom att skriva in namnet på detta program. Program har samma egenskaper som algoritmer.
Lektionssammanfattning:
Dialog:
Vad lärde du dig för nytt på lektionen?
Vilken är den praktiska betydelsen av den fråga som studeras?
Vilka är de positiva aspekterna av lektionen.
Lyckönskningar
Tack för arbetet på lektionen!