Hem › Navigatörer › Utförande av algoritmen för ett specifikt verkställarbeslut. Datavetenskap och informationsteknik. Sätt att beskriva algoritmer

Utförande av algoritmen för ett specifikt verkställarbeslut. Datavetenskap och informationsteknik. Sätt att beskriva algoritmer

Nyckelord:

algoritm
egenskaper hos algoritmen
- diskrethet
- klarhet
- säkerhet
- effektivitet
- masskaraktär
testamentsexekutor

artistegenskaper
- olika uppgifter som ska lösas
- onsdag
- driftläge
- kommandosystem
formell exekvering av algoritmen

3.1.1. Algoritm koncept

Varje person i Vardagsliv, i studier eller på jobbet, löser ett stort antal problem av varierande komplexitet. Komplexa problem kräver mycket eftertanke för att hitta en lösning; En person löser enkla och välbekanta uppgifter utan att tänka, automatiskt. I de flesta fall kan lösningen på varje problem delas upp i enkla steg (steg). För många sådana uppgifter (installation programvara, montera ett skåp, skapa en webbplats, använda en teknisk anordning, köpa en flygbiljett via Internet, etc.) har redan utvecklats och erbjudits steg för steg instruktioner, vilket, när det körs konsekvent, kan leda till det önskade resultatet.

Exempel 1. Problemet "Hitta det aritmetiska medelvärdet av två tal" löses i tre steg:

tänk på två siffror;
lägg till två siffror i åtanke;
dividera det resulterande beloppet med 2.

Exempel 2. Uppgiften "Sätt in pengar på ditt telefonkonto" är uppdelad i följande steg:

gå till betalterminalen;
välj en telekomoperatör;
Fyll i ett telefonnummer;
kontrollera att det angivna numret är korrekt;
infoga en sedel i sedelmottagaren;
vänta på ett meddelande om att pengar krediteras ditt konto;
få en check.

Exempel 3. Stadierna för att lösa problemet "Rita en rolig igelkott" presenteras grafiskt:

Att hitta det aritmetiska medelvärdet, sätta in pengar på ett telefonkonto och rita en igelkott är vid första anblicken helt andra processer. Men de har ett gemensamt drag: var och en av dessa processer beskrivs av en sekvens av korta instruktioner, den strikta efterlevnaden gör att du kan få det önskade resultatet. Instruktionssekvenserna som ges i exempel 1-3 är algoritmer för att lösa motsvarande problem. Utföraren av dessa algoritmer är en person.

Algoritmen kan vara en beskrivning av en viss sekvens av beräkningar (exempel 1) eller steg av icke-matematisk karaktär (exempel 2-3). Men i alla fall, innan dess utveckling, den initiala förhållanden(indata) och vad som ska erhållas (resultat). Vi kan säga att en algoritm är en beskrivning av sekvensen av steg för att lösa ett problem, som leder från de ursprungliga data till det önskade resultatet.

Generellt sett kan algoritmens operationsdiagram representeras enligt följande (Fig. 3.1):

Ris. 3.1.
Generellt schema för algoritmen

Algoritmer är reglerna för addition, subtraktion, multiplikation och division av tal, grammatiska regler, regler för geometriska konstruktioner etc. som studeras i skolan.

Animationer "Arbeta med en algoritm", "Största gemensamma divisor", "Minsta gemensamma multipel" (http://school-collection.edu.ru/) hjälper dig att komma ihåg några algoritmer som studerats i ryska språk- och matematiklektioner.

Exempel 4. En viss algoritm leder till det faktum att från en kedja av tecken erhålls en ny kedja enligt följande:

Längden (i tecken) på källsträngen med tecken beräknas.
Om längden på den ursprungliga kedjan är udda, läggs siffran 1 till den ursprungliga kedjan till höger, annars ändras inte kedjan.
Symbolerna byts ut i par (den första med den andra, den tredje med den fjärde, den femte med den sjätte, etc.).
Siffran 2 läggs till till höger om den resulterande kedjan.

Den resulterande kedjan är resultatet av algoritmen.

Så, om den initiala kedjan var A#B, så kommer resultatet av algoritmen att vara kedjan #A1B2, och om den initiala kedjan var ABC@, så blir resultatet av algoritmen kedjan BA@B2.

3.1.2. Algoritm exekutor

Varje algoritm är designad för en specifik utförare.

Det finns formella och informella artister. En formell artist utför alltid samma kommando på samma sätt. En informell utförare kan utföra ett kommando på olika sätt.

Låt oss överväga mer i detalj uppsättningen av formella artister. Formella artister är extremt olika, men för var och en av dem kan följande egenskaper specificeras: utbudet av uppgifter som ska lösas (ändamål), miljö, kommandosystem och driftsätt.

En rad uppgifter som ska lösas. Varje artist är skapad för att lösa ett visst antal problem - att konstruera kedjor av symboler, utföra beräkningar, konstruera ritningar på ett plan, etc.

Konstnärsmiljö. Området, miljön, förhållandena där artisten verkar kallas vanligtvis den givna artistens miljö. Källdata och resultat för någon algoritm tillhör alltid miljön för den utförare som algoritmen är avsedd för.

Utförarens kommandosystem. En instruktion till en artist att utföra en separat genomförd åtgärd kallas ett kommando. Uppsättningen av alla kommandon som kan utföras av någon executor bildar kommandosystemet för denna executor (SKI). Algoritmen kompileras med hänsyn till förmågan hos en specifik utförare, med andra ord i systemet av kommandon för utföraren som kommer att utföra den.

Utförarens driftlägen. För de flesta artister, direktkontrolllägen och programstyrning. I det första fallet väntar artisten på kommandon från en person och utför omedelbart varje mottagen kommando. I det andra fallet får utföraren 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 de namngivna lägena.

Låt oss titta på exempel på artister.

Exempel 5. Artist Sköldpaddan rör sig på datorskärmen och lämnar ett spår i form av en linje. Sköldpaddans kommandosystem består av två kommandon:

Höger m (där m är ett heltal) - gör att sköldpaddans rörelseriktning ändras med m grader medurs.

Spela in Upprepa k [<Команда1> <Команда2> ... <Командаn>] betyder att sekvensen av kommandon inom parentes kommer att upprepas k gånger.

Tänk på vilken figur som kommer att visas på skärmen efter att sköldpaddan har slutfört följande algoritm.

Upprepa 12 [Höger 4 5 Framåt 20 Höger 45]

Exempel 6. Systemet med exekveringskommandon Datorn består av två kommandon, som är tilldelade nummer:

Den första av dem minskar antalet med 1, den andra ökar antalet med 3 gånger. När du skriver algoritmer, för korthetens skull, anges endast kommandonummer. Till exempel betyder algoritm 21212 följande sekvens av kommandon:

Med denna algoritm kommer talet 1 att omvandlas till 15: ((1-3-1)-3-1)-3 = 15.

Exempel 7. Performer Robot arbetar på ett rutigt fält, mellan intilliggande celler kan det finnas väggar. Roboten rör sig längs fältets celler och kan utföra följande kommandon, som är tilldelade nummer:

När du utför varje sådant kommando, flyttar roboten till en intilliggande cell i den angivna riktningen. Om det finns en vägg i denna riktning mellan cellerna, förstörs roboten. Vad kommer att hända med roboten om den utför kommandosekvensen 32323 (här anger siffrorna kommandonummer), börjar flytta 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 när den träffar väggarna?

När du utvecklar en algoritm:

objekt som förekommer i problemet identifieras, objekts egenskaper, relationer mellan objekt och möjliga åtgärder med föremål;
de initiala data och det erforderliga resultatet bestäms;
sekvensen av handlingar för utföraren bestäms, vilket säkerställer övergången från de ursprungliga data till resultatet;
sekvensen av åtgärder registreras med hjälp av kommandon som ingår i utförarens kommandosystem.

Vi kan säga att en algoritm är en modell av aktiviteten hos algoritmexekvatorn.

3.1.3. Algoritmegenskaper

Inte varje instruktion, sekvens av instruktioner eller handlingsplan kan betraktas som en algoritm. Varje algoritm har med nödvändighet följande egenskaper: diskrethet, förståelighet, säkerhet, effektivitet och masskaraktär.

Egenskapen diskret innebär att vägen till att lösa ett problem är uppdelad i separata steg (åtgärder). Varje åtgärd har en motsvarande instruktion (kommando). Först efter att ha utfört ett kommando kan utföraren börja utföra nästa kommando.

Egenskapen förståelse innebär att algoritmen endast består av kommandon som ingår i utförarens kommandosystem, det vill säga sådana kommandon som utföraren kan uppfatta och enligt vilka han kan utföra de nödvändiga åtgärderna.

Egenskapen säkerhet innebär att algoritmen inte innehåller kommandon vars betydelse kan tolkas tvetydigt av utföraren; Situationer är oacceptabla när det, efter att ha utfört nästa kommando, är oklart för utföraren vilket kommando som ska utföras i nästa steg.

Effektivitetsegenskapen innebär att algoritmen måste kunna få ett resultat efter ett ändligt, eventuellt mycket stort, antal steg. I det här fallet anses resultatet inte bara vara svaret som bestäms av problemformuleringen, utan också slutsatsen om omöjligheten att fortsätta att lösa detta problem av någon anledning.

Egenskapen för massproduktion innebär att algoritmen måste ge möjlighet till sin tillämpning för att lösa alla problem från en viss klass av problem. Till exempel bör algoritmen för att hitta rötterna till en andragradsekvation vara tillämpbar på vilken andragradsekvation som helst, algoritmen för att korsa gatan bör vara tillämpbar var som helst på gatan, algoritmen för att förbereda medicin bör vara tillämplig för att förbereda vilken mängd som helst av den, etc.

Exempel 8. Låt oss överväga en av metoderna för att hitta alla primtal som inte överstiger n. Denna metod kallas "Sil of Eratosthenes", uppkallad efter den antika grekiska vetenskapsmannen Eratosthenes som föreslog den.

För att hitta alla primtal som inte är större än ett givet tal n, enligt Eratosthenes metod, måste du utföra följande steg:

skriv ner alla heltal från 2 till n i rad (2, 3, 4, ..., n);
ram 2 - det första primtalet;
stryka ut från listan alla tal som är delbara med det senast hittade primtalet;
hitta det första omärkta numret (markerade siffror är överstrukna siffror eller siffror inneslutna i en ram) och omslut det i en ram - detta kommer att vara ett annat primtal;
upprepa steg 3 och 4 tills det inte finns några omarkerade nummer kvar.

Du kan få en mer visuell uppfattning om metoden för att hitta primtal med hjälp av animationen "The Sieve of Eratosthenes" (http://school-collection.edu.ru/).

Den övervägda sekvensen av åtgärder är en algoritm, eftersom den uppfyller följande egenskaper:

diskrethet - processen att hitta primtal är uppdelad i steg;
förståelighet - varje kommando är förståeligt för en elev i 9:e klass som utför denna algoritm;
säkerhet - varje kommando tolkas och exekveras av utföraren entydigt; det finns instruktioner om ordningen för utförande av kommandon;
effektivitet - efter ett visst antal steg uppnås resultatet;
masskaraktär - sekvensen av åtgärder är tillämplig för alla naturliga n.

Algoritmens övervägda egenskaper tillåter oss att ge en mer exakt definition av algoritmen.

3.1.4. Möjlighet till automatisering av mänskliga aktiviteter

Att utveckla en algoritm är vanligtvis en arbetskrävande uppgift som kräver att en person har djup kunskap, uppfinningsrikedom och mycket tid.

Att lösa ett problem med en färdig algoritm kräver endast att utföraren strikt följer de givna instruktionerna.

Exempel 9. Från en hög som innehåller valfritt antal föremål större än tre, turas två spelare om att ta ett eller två föremål var. Vinnaren är den som kan plocka upp alla återstående föremål på sitt nästa drag.

Låt oss överväga en algoritm, efter vilken den första spelaren säkerligen kommer att säkerställa en vinst.

Om antalet föremål i högen är en multipel av 3, ge vika för motståndaren, annars starta spelet.
Med ditt nästa drag lägger du varje gång till antalet objekt som din motståndare tog till 3 (antalet återstående objekt måste vara en multipel av 3).

Utövaren får inte fördjupa sig i innebörden av vad han gör och inte resonera varför han agerar på detta sätt och inte på annat sätt, det vill säga han kan agera formellt. Utövarens förmåga att agera formellt ger möjligheten att automatisera mänsklig aktivitet. För detta:

processen att lösa ett problem presenteras som en sekvens av enkla operationer;
en maskin skapas ( automatisk enhet), kapabel att utföra dessa operationer i den sekvens som specificeras i algoritmen;
en person är befriad från rutinaktiviteter, utförandet av algoritmen anförtros en automatisk enhet.

Det viktigaste

Artist - något föremål (person, djur, teknisk anordning), som kan utföra en specifik uppsättning kommandon. En formell artist utför alltid samma kommando på samma sätt. För varje formell utförare kan du specificera: utbudet av uppgifter som ska lösas, miljön, kommandosystemet och driftläget.

En algoritm är en beskrivning av en sekvens av åtgärder avsedda för en specifik utförare som leder från initiala data till det önskade resultatet, som har egenskaperna diskret, förståelighet, säkerhet, effektivitet och masskaraktär.

Utövarens förmåga att agera formellt ger möjligheten att automatisera mänsklig aktivitet.

Frågor och uppgifter

Vad kallas en algoritm?
Hitta synonymer för ordet "recept".
Ge exempel på algoritmer du studerade i skolan.
Vem kan vara exekutor av algoritmen?
Ge ett exempel på en formell artist. Ge ett exempel när en person agerar som en formell artist.
Vilka kommandon ska en robot utföra funktionerna som: a) en kassörska i en butik; b) en vaktmästare; c) en säkerhetsvakt?
Vad bestämmer omfattningen av uppgifter som utförs av "dator"-utövaren?
Tänk som en artist ordbehandlare, tillgänglig på din dator. Beskriv omfånget av uppgifter som löses av denna utförare och hans omgivning.
Vad är ett team, ett system av utförarkommandon?
Lista de viktigaste egenskaperna hos algoritmen.
Vad kan frånvaron av någon egenskap i en algoritm leda till? Ge exempel.
Varför är det viktigt att formellt kunna exekvera en algoritm?
Talföljden är konstruerad enligt följande algoritm: de två första talen i sekvensen tas lika med 1; Varje nästa tal i sekvensen anses vara lika med summan av de två föregående talen. Skriv ner de första 10 termerna i denna sekvens.
En viss algoritm erhåller en ny kedja från en teckensträng enligt följande. Först skrivs den ursprungliga kedjan av tecken, efter den skrivs den ursprungliga kedjan av tecken i omvänd ordning, sedan skrivs bokstaven som följer i det ryska alfabetet efter bokstaven som var på sista plats i den ursprungliga kedjan. Om den sista platsen i den ursprungliga kedjan är bokstaven Z, så skrivs bokstaven A som nästa bokstav. Den resulterande kedjan är resultatet av algoritmen. Till exempel, om den ursprungliga teckenkedjan var DOM, blir resultatet av algoritmen kedjan DOMMODN. Teckensträngen COM ges. Hur många bokstäver O kommer det att finnas i kedjan av symboler som kommer att erhållas om du tillämpar algoritmen på denna kedja och sedan tillämpar algoritmen igen på resultatet av dess arbete?
Hitta en animering av stegen i Eratosthenes algoritm på Internet. Använd Eratosthenes algoritm för att hitta alla primtal som inte överstiger 50.
Vad blir resultatet av Turtles exekvering (se exempel 5) av algoritmen?
Skriv ner en algoritm för kalkylatorns executor (exempel 6), som inte innehåller mer än 5 kommandon:
Systemet med exekveringskommandon Konstruktören består av två kommandon, som är tilldelade nummer:
Enligt den första av dem läggs 2 till talet till höger, enligt den andra delas talet med 2. Hur kommer talet 8 att omvandlas om utföraren kör algoritm 22212? Skapa en algoritm i kommandosystemet för denna executor, enligt vilken siffran 1 kommer att omvandlas till siffran 16 (algoritmen bör inte innehålla mer än 5 kommandon).
I vilken cell ska robotutövaren (exempel 7) placeras för att kunna återvända till den efter att ha exekverat algoritm 3241?

| § 2.1. Algoritmer och exekutorer

Lektion 14
§ 2.1. Algoritmer och exekutorer

Nyckelord:

Algoritm
egenskaper hos algoritmen (diskret; förståelighet; säkerhet; effektivitet; masskaraktär)
testamentsexekutor
utövarens egenskaper (omfattning av uppgifter som ska lösas; miljö; driftläge; kommandosystem)
formell exekvering av algoritmen

2.1.1. Algoritm koncept

Varje person i vardagen, i studier eller på jobbet löser ett stort antal problem av varierande komplexitet. Komplexa problem kräver mycket eftertanke för att hitta en lösning; En person löser enkla och välbekanta uppgifter utan att tänka, automatiskt. I de flesta fall kan lösningen på varje problem delas upp i enkla steg (steg). För många av dessa uppgifter (installera programvara, montera ett skåp, skapa en webbplats, använda en teknisk anordning, köpa en flygbiljett via Internet, etc.) har steg-för-steg-instruktioner redan utvecklats och erbjuds, den sekventiella genomförandet kan leda till önskat resultat.

Exempel 1. Problemet "Hitta det aritmetiska medelvärdet av två tal" löses i tre steg:

1) tänk på två siffror;
2) lägg till två planerade nummer;
3) dividera det resulterande beloppet med 2.

Exempel 2. Uppgiften "Sätt in pengar på ditt telefonkonto" är uppdelad i följande steg:

1) gå till betalterminalen;
2) välj en teleoperatör;
3) ange ett telefonnummer;
4) kontrollera att det angivna numret är korrekt;
5) infoga en sedel i sedelmottagaren;
6) vänta på ett meddelande om att pengar krediteras ditt konto;
7) få en check.

Exempel 3. Stadierna för att lösa problemet "Rita en rolig igelkott" presenteras grafiskt:

Algoritmen kan vara en beskrivning av en viss sekvens av beräkningar (exempel 1) eller steg av icke-matematisk karaktär (exempel 2-3). Men i alla fall, innan dess utveckling, måste de initiala förutsättningarna (initialdata) och vad som ska erhållas (resultat) vara tydligt definierade. Vi kan säga att en algoritm är en beskrivning av sekvensen av steg för att lösa ett problem, som leder från de ursprungliga data till det önskade resultatet.

Generellt sett kan algoritmens operationsdiagram representeras enligt följande (Fig. 2.1).

Ris. 2.1. Generellt schema för algoritmen

Algoritmer är reglerna för addition, subtraktion, multiplikation och division av tal som studeras i skolan, många grammatiska regler, regler för geometriska konstruktioner, etc.

Animationer "Arbeta med en algoritm" (193576), "Största gemensamma divisor" (170363), "Minsta gemensamma multipel" (170390) hjälper dig att komma ihåg några algoritmer som studerats i ryska språk- och matematiklektioner (http://sc.edu. ru /).

Exempel 4. En viss algoritm leder till det faktum att från en kedja av tecken erhålls en ny kedja enligt följande:

1. Längden (i tecken) på den ursprungliga teckensträngen beräknas.
2. Om längden på den ursprungliga kedjan är udda, läggs siffran 1 till den ursprungliga kedjan till höger, annars ändras inte kedjan.
3. Symbolerna byts ut i par (den första med den andra, den tredje med den fjärde, den femte med den sjätte, etc.).
4. Siffran 2 läggs till till höger om den resulterande kedjan.

Den resulterande kedjan är resultatet av algoritmen.

Så, om den initiala kedjan var A#B, så kommer resultatet av algoritmen att vara kedjan #A1B2, och om den initiala kedjan var ABC@, så blir resultatet av algoritmen kedjan BA@B2.

2.1.2. Algoritm exekutor

Varje algoritm är designad för en specifik utförare.

En exekutor är ett objekt (person, djur, teknisk anordning) som kan utföra en viss uppsättning kommandon.

Skilja på formella och informella artister. En formell artist utför alltid samma kommando på samma sätt. En informell utförare kan utföra ett kommando på olika sätt.

En rad uppgifter som ska lösas. Varje artist är skapad för att lösa ett visst antal problem - att konstruera kedjor av symboler, utföra beräkningar, konstruera ritningar på ett plan, etc.

Utförarens driftlägen. För de flesta artister finns lägen för direktkontroll och programstyrning. I det första fallet väntar artisten på kommandon från en person och utför omedelbart varje mottagen kommando. I det andra fallet får utföraren först en komplett sekvens av kommandon (program), och sedan utför han alla dessa kommandon automatiskt. Ett antal artister arbetar bara i ett av de namngivna lägena.

Låt oss titta på exempel på artister.

Exempel 5. Artist Sköldpaddan rör sig på datorskärmen och lämnar ett spår i form av en linje.

Turtle-kommandosystemet består av följande kommandon:

1. Framåt n (där n är ett heltal) - får sköldpaddan att röra sig n steg i rörelseriktningen - i den riktning som dess huvud och kropp är vända mot;
2. Höger m (där m är ett heltal) - orsakar en förändring i riktningen för sköldpaddans rörelse med t grader medurs.
Spela in Upprepa k [<Команда1> <Команда2> ... <Командаn>] betyder att sekvensen av kommandon inom parentes kommer att upprepas k gånger.

Tänk på vilken figur som kommer att visas på skärmen efter att sköldpaddan har slutfört följande algoritm.
Upprepa 12 [höger 45 framåt 20 höger 45]

Exempel 6. Systemet med exekveringskommandon Datorn består av två kommandon, som är tilldelade nummer:

1 - subtrahera 1
2 - multiplicera med 3

Multiplicera med 3
subtrahera 1
multiplicera med 3
subtrahera 1
multiplicera med 3

Med denna algoritm konverteras siffran 1 till 15:

((1 3 - 1) 3 - 1) 3 = 15.

Exempel 7. Performer Robot arbetar på ett rutigt fält, mellan intilliggande celler kan det finnas väggar. Roboten rör sig längs fältets celler och kan utföra följande kommandon, som är tilldelade nummer:

1 upp
2 - ner
3 - rätt
4 kvar

När du utför varje sådant kommando, flyttar roboten till en intilliggande cell i den angivna riktningen. Om det finns en vägg i denna riktning mellan cellerna, förstörs roboten.

Vad kommer att hända med roboten om den utför kommandosekvensen 32323 (här anger siffrorna kommandonummer), börjar flytta 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 när den träffar väggarna?

När du utvecklar en algoritm:

1) objekten som förekommer i problemet identifieras, objektens egenskaper, relationerna mellan objekten och möjliga åtgärder med objekten fastställs;
2) de initiala data och det erforderliga resultatet bestäms;
3) sekvensen av handlingar för utföraren bestäms, vilket säkerställer övergången från de ursprungliga uppgifterna till resultatet;
4) sekvensen av åtgärder registreras med hjälp av kommandon som ingår i utförarens kommandosystem.

Vi kan säga att en algoritm är en modell av aktiviteten hos algoritmexekvatorn.

2.1.3. Algoritmegenskaper

Diskret egendom innebär att vägen till att lösa ett problem är uppdelad i separata steg (åtgärder). Varje åtgärd har en motsvarande instruktion (kommando). Först efter att ha utfört ett kommando kan utföraren börja utföra nästa kommando.

Förståelighet egenskap innebär att algoritmen endast består av kommandon som ingår i utförarens kommandosystem, dvs av sådana kommandon som utföraren kan uppfatta och enligt vilka han kan utföra de nödvändiga åtgärderna.

Säkerhetens egendom betyder att algoritmen inte innehåller kommandon vars betydelse kan tolkas tvetydigt av utföraren; Situationer är oacceptabla när det, efter att ha utfört nästa kommando, är oklart för utföraren vilket kommando som ska utföras härnäst. Tack vare detta bestäms resultatet av algoritmen unikt av uppsättningen initiala data: om algoritmen appliceras flera gånger på samma uppsättning initiala data, producerar utmatningen alltid samma resultat.

Prestandafastighet innebär att algoritmen måste ge ett resultat efter ett ändligt, möjligen mycket stort, antal steg. I det här fallet anses resultatet inte bara vara svaret som bestäms av problemformuleringen, utan också slutsatsen om omöjligheten att fortsätta att lösa detta problem av någon anledning.

Egendom av masskaraktär innebär att algoritmen måste ge möjlighet till sin tillämpning för att lösa alla problem från en viss klass av problem. Till exempel bör algoritmen för att hitta rötterna till en andragradsekvation vara tillämpbar på vilken andragradsekvation som helst, algoritmen för att korsa gatan bör vara tillämpbar var som helst på gatan, algoritmen för att förbereda medicin bör vara tillämplig för att förbereda vilken mängd som helst av den, etc.

Exempel 8. Låt oss överväga en av metoderna för att hitta alla primtal som inte överstiger något naturligt tal n. Denna metod kallas "Eratosthenes såll" efter den antika grekiska vetenskapsmannen Eratosthenes (3:e århundradet f.Kr.) som föreslog den.

För att hitta alla primtal som inte är större än ett givet tal n, enligt Eratosthenes metod, måste du utföra följande steg:

1) skriv ner i rad alla naturliga tal från 2 till n (2, 3, 4, ..., n);
2) ram 2 - det första primtalet;
3) stryk över alla tal som är delbara med det senast hittade primtalet från listan;
4) hitta det första omärkta numret (markerade siffror är överstrukna siffror eller siffror inneslutna i en ram) och omslut det i en ram - detta kommer att vara ett annat primtal;
5) upprepa steg 3 och 4 tills det inte finns några omarkerade nummer kvar.

Du kan få en mer visuell uppfattning om metoden för att hitta primtal med hjälp av animationen "Sieve of Eratosthenes" (180279) publicerad i Unified Collection of Digital Educational Resources.

Den övervägda sekvensen av åtgärder är en algoritm, eftersom den uppfyller följande egenskaper:

diskrethet- processen att hitta primtal är uppdelad i steg;
förståelighet- varje kommando är förståeligt för en elev i 8:e klass som utför denna algoritm;
säkerhet- varje kommando tolkas och utförs entydigt av utföraren; det finns instruktioner om ordningen för utförande av kommandon;
effektivitet- efter ett visst antal steg uppnås resultatet;
masskaraktär- sekvensen av åtgärder är tillämplig för alla naturliga tal n.

Algoritmens övervägda egenskaper tillåter oss att ge en mer exakt definition av algoritmen.

2.1.4. Möjlighet till automatisering av mänskliga aktiviteter

Att utveckla en algoritm är vanligtvis en arbetskrävande uppgift som kräver att en person har djup kunskap, uppfinningsrikedom och mycket tid.

Att lösa ett problem med en färdig algoritm kräver endast att utföraren strikt följer de givna instruktionerna.

Exempel 9. Från en hög som innehåller valfritt antal föremål större än tre, turas två spelare om att ta ett eller två föremål var. Vinnaren är den som kan plocka upp alla återstående föremål på sitt nästa drag.

Låt oss överväga en algoritm, efter vilken den första spelaren säkerligen kommer att säkerställa en vinst.

1. Om antalet föremål i högen är en multipel av 3, ge vika för motståndaren, annars starta spelet genom att ta 1 eller 2 föremål så att antalet föremål som återstår är en multipel av 3.
2. Med ditt nästa drag lägger du varje gång antalet objekt som din motståndare tagit till 3 (antalet återstående objekt måste vara en multipel av 3).

1) processen att lösa ett problem presenteras som en sekvens av enkla operationer;
2) en maskin (automatisk enhet) skapas som är kapabel att utföra dessa operationer i den sekvens som anges i algoritmen;
3) en person är befriad från rutinaktiviteter, exekveringen av algoritmen anförtros en automatisk enhet.

DET VIKTIGASTE

Testamentsexekutor- något föremål (person, djur, teknisk anordning) som kan utföra en viss uppsättning kommandon.

En formell artist utför alltid samma kommando på samma sätt. För varje formell exekutör kan du ange: utbud av uppgifter som ska lösas, miljö, ledningssystem och driftläge.

Algoritm- en beskrivning av sekvensen av åtgärder avsedda för en specifik utförare som leder från de initiala uppgifterna till det önskade resultatet, som har egenskaperna diskret, förståelighet, säkerhet, effektivitet och masskaraktär.

Artistens förmåga att agera formellt ger möjlighet att automatisera mänskliga aktiviteter.

Frågor och uppgifter

1. Läs presentationsmaterialet för stycket i elektronisk ansökan till läroboken. Kompletterar presentationen informationen i stycketexten? Vilka bilder kan du lägga till i din presentation?

2. Vad kallas en algoritm?

3. Välj synonymer för ordet "recept".

4. Ge exempel på algoritmer du studerade i skolan.

5. Vem kan vara exekutor av algoritmen?

6. Ge ett exempel på en formell artist. Ge ett exempel när en person agerar som en formell artist.

7. Vad bestämmer omfattningen av uppgifter som utförs av "dator"-utövaren?

8. Se ordbehandlaren på din dator som exekutor. Beskriv omfånget av uppgifter som löses av denna utförare och hans omgivning.

9. Vad är ett team, ett system av utförarkommandon?

10. Vilka kommandon ska en robot utföra följande funktioner:

a) kassa i en butik;
b) en vaktmästare;
c) en säkerhetsvakt?

11. Lista huvudegenskaperna för algoritmen.

12. Vad kan frånvaron av någon egenskap i en algoritm leda till? Ge exempel.

13. Vad är betydelsen av att formellt kunna exekvera en algoritm?

14. Talföljden är konstruerad enligt följande algoritm: de två första talen i sekvensen tas lika med 1; Varje nästa tal i sekvensen anses vara lika med summan av de två föregående talen. Skriv ner de första 10 termerna i denna sekvens. Ta reda på vad denna sekvens kallas.

15. En viss algoritm erhåller en ny kedja från en sträng av tecken enligt följande. Först skrivs den ursprungliga kedjan av tecken, efter den skrivs den ursprungliga kedjan av tecken i omvänd ordning, sedan skrivs bokstaven som följer i det ryska alfabetet efter bokstaven som var på sista plats i den ursprungliga kedjan. Om bokstaven "I" är på den sista platsen i den ursprungliga kedjan, skrivs bokstaven "A" som nästa bokstav. Den resulterande kedjan är resultatet av algoritmen. Till exempel, om den ursprungliga teckenkedjan var "HUS", blir resultatet av algoritmen kedjan "DOMMODN". Teckensträngen "COM" ges. Hur många bokstäver "O" kommer det att finnas i kedjan av tecken som kommer att erhållas om du tillämpar algoritmen på denna kedja och sedan tillämpar algoritmen igen på resultatet av dess arbete?

16. Hitta en animering av stegen i Eratosthenes algoritm på Internet. Använd Eratosthenes algoritm för att hitta alla primtal som inte överstiger 50.

17. Vad blir resultatet av Turtles exekvering (se exempel 5) av algoritmen?

18. Skriv ner en algoritm för Kalkylatorns executor (se exempel 6), som inte innehåller mer än 5 kommandon:

a) ta emot numret 16 från siffran 3;
b) ta emot numret 25 från siffran 1.

19. System av utförarkommandon Konstruktören består av två kommandon, som är tilldelade nummer:

1 - tilldela 2
2 - dividera med 2

Enligt den första av dem läggs 2 till talet till höger, enligt den andra delas talet med 2. Hur kommer talet 8 att omvandlas om utföraren kör algoritm 22212? Skapa en algoritm i kommandosystemet för denna executor, enligt vilken siffran 1 kommer att omvandlas till siffran 16 (algoritmen bör inte innehålla mer än 5 kommandon).

20. I vilken cell ska robotutövaren (exempel 7) placeras för att kunna återvända till den efter att ha exekverat algoritm 3241?

Gratis mjukvara:

KuMir-system - Uppsättning av utbildningsvärldar (ladda ner programarkivet från webbplatsen) eller besök KuMir-sidan ((http://www.niisi.ru/kumir/)

Stäng av AdBlock på den här webbplatsen.

I den här lektionen kommer vi att titta på några teoretiska begrepp som formaliserar begreppet programmering. Samtidigt kommer vi att mer exakt formulera huvuduppgiften för din träning.

Till att börja med föreslår jag att du leker lite med följande barnleksak. Slutför de fem första uppgifterna, gå tillbaka och fortsätt läsa lektionen.

Fig.1 Skärmbild av spelplanen på code.org

Jag hoppas att allt löste sig för dig. Nu, med hjälp av det här exemplet, kommer vi att beskriva flera grundläggande begrepp:

testamentsexekutor;
system av utförarkommandon;
algoritm.

I leksaken styr vi en röd fågel. Målet med varje steg är att få fågeln till grisen. Fågeln kan utföra vissa kommandon, till exempel: gå framåt, sväng vänster, sväng höger osv.

En person, maskin eller enhet som kan utföra vissa kommandon kallas en exekutor. I denna leksak är artisten uppenbarligen en fågel. Den uppsättning kommandon som utföraren förstår och kan utföra kallas system av exekveringskommandon.

Den sekvens av kommandon som en utförare måste utföra för att lösa ett problem kallas en algoritm.

Det är nödvändigt att fokusera på flera punkter.

Utföraren kan endast utföra de kommandon som ingår i hans kommandosystem.

Det betyder till exempel att du inte kan skriva till fågelartisten: "Gå till grisen!" Du kan skriva ner det mer exakt, men ingenting kommer att hända, för... den som utför sådana kommandon vet inte.

Du kan skriva ner de tillgängliga kommandona i vilken ordning som helst som du anser vara korrekt. Din uppgift som programmerare är att dela upp en stor komplex uppgift i små individuella steg, som vart och ett kommer att vara begripligt för utföraren. Principen om "dela och härska" är på gång igen.

Utövaren gör exakt vad algoritmen säger åt honom att göra.

Fågelartisten är mycket förtroendefull. Hon ifrågasätter inte det du skriver i programmet. Om du till exempel glömmer att vända fågeln kommer den att krascha in i väggen. Därför måste du övervaka allt själv.

Dina framtida program kommer ofta inte att fungera som du tänkt dig. Misstag händer alla. Här är det viktigt att förstå att det inte är datorn som är dum, utan du har gjort fel i algoritmen. Var inte som dåliga programmerare, för vilka programmet alltid är skyldig till allt.

Låt oss nu gå vidare från det illustrativa exemplet till datorverkligheten. Vi skriver program för datorn, vilket betyder att datorn i vårt fall är utföraren. Kommandosystemet är standardfunktioner och konstruktioner av C-språket.

Vilket är huvudmålet med din undervisning i grunderna i programmering? Bemästra skickligheten i algoritmiskt tänkande. Det vill säga, lär dig att skriva ner lösningen på olika problem i form av en algoritm för en specifik utförare (i vårt fall en dator).

Så, för att sammanfatta:

Datorprogram– en algoritm för att lösa ett problem, skriven på ett programmeringsspråk.

En algoritm är en exakt beskrivning av ordningen på åtgärder som en utförare måste utföra för att lösa ett problem.

En exekutor är en person eller någon enhet som kan förstå och utföra en viss uppsättning kommandon.

Ordet "algoritm" kommer från namnet på den arabiske matematikern al-Khwarizmi från 900-talet, som formulerade reglerna för att utföra aritmetiska operationer.

Algoritm– en korrekt och begriplig instruktion till utföraren att utföra den slutliga sekvensen av kommandon som leder från de initiala data till det initiala resultatet.

Exempel: daglig rutin, matlagningsordning, instruktioner, etc.)

Algoritm exekutor– det är den som exekverar algoritmen (person, djur, maskin, dator).

Utförarens kommandosystem- detta är hela uppsättningen av kommandon som utföraren vet hur man utför (förstår). Algoritmen kan endast byggas från kommandon som ingår i systemet med exekveringskommandon.

Till exempel, utförare Roboten kan utföra kommandon framåt, bakåt, vänster, höger, måla. Den rör sig över ett cellfält som avgränsas av en vägg och innehåller väggar. Roboten kan inte gå igenom väggen.

Algoritmegenskaper:

1.Prestanda (lem)– förmågan att erhålla ett resultat från initialdata i ett begränsat antal steg. (Till exempel, när man kör algoritmen för att lägga till 2 siffror ska summan erhållas).

2.Mass karaktär– förmågan att tillämpa algoritmen på ett stort antal olika källdata. (Du kan till exempel lägga till två valfria siffror genom att känna till additionsalgoritmen.)

3.Determinism(säkerhet, noggrannhet) – varje kommando måste unikt bestämma utövarens handling.

4.Förståelighet– kommandot måste skrivas på ett språk som är förståeligt för datorn.

5.Diskrethet– dela upp algoritmen i separata kommandon.

Sätt att skriva algoritmen:

1) I naturligt språk – inspelning i form av separata kommandon på ett språk som är förståeligt för människor.

2) Grafik – på flödesschemats språk, med hjälp av geometriska former (ovala, rektangel, parallellogram, romb).

3) På ett algoritmiskt språk - ett språk för att skriva algoritmer för undervisning i programmering. Kommandon är skrivna på ryska.

4) På ett programmeringsspråk - ett program. Programmeringsspråk: Basic, Pascal, C, Visual Basic.

B7.Grundläggande algoritmiska strukturer: följande, förgrening, loop; bild på blockdiagram. Dela upp uppgifter i deluppgifter. Hjälpalgoritmer.

Algoritmiska mönster. Inom algoritmer kan grupper av steg urskiljas som skiljer sig åt i intern struktur - algoritmiska konstruktioner.

Grundläggande algoritmiska konstruktionerär linjär sekvens av steg (eller följande), förgrening och looping.

En algoritm där kommandon exekveras sekventiellt efter varandra anropas linjär algoritm.

Så här ser en linjär algoritm ut i blockschemaspråk:

Exempel: algoritm för att slå på datorn:

Slå på strömmen till datorn (tryck på knappen på överspänningsskydd).
Slå på monitorn och skrivaren.
Klick Strömknappen på systemenhet.
Vänta på laddning operativ system och skrivbordets utseende.
Börja jobba.

I den här algoritmen måste alla åtgärder utföras sekventiellt efter varandra: du kan inte börja arbeta om strömmen eller monitorn inte är påslagen.

In i den algoritmiska strukturen " förgrening» ingår skick, beroende på sanningen i villkoret, exekveras en eller annan sekvens av kommandon (serier).

Ett villkor är ett påstående som kan vara sant eller falskt. I villkoret jämförs två tal, två strängar, två variabler eller stränguttryck med varandra med hjälp av jämförelseoperatorer (>,<, =, >=, <=).

Inspelning på algoritmiskt språk: IfCondition Then Series 1 (If Skick sant, sedan sant Avsnitt 1, Om Skick falskt, då exekveras ingenting). Exempel: Om det är söndag idag, behöver du inte gå till skolan. Full form av förgrening

I algoritmiska strukturer cykel innehåller en serie kommandon som exekveras upprepade gånger. Denna sekvens av kommandon kallas slingans kropp.

Det finns två typer av cykliska algoritmiska strukturer:

motverkade slingor, där slingans kropp exekveras ett visst antal gånger;
villkorliga loopar, där slingans kropp exekveras så länge som villkoret är uppfyllt.

Slinga med disk– används när det är känt i förväg hur många repetitioner av slingkroppen som behöver utföras.

Algoritm och dess egenskaper.

Algoritm- en tydlig och exakt instruktion till utföraren att utföra den sista sekvensen av kommandon som leder från de initiala data till det önskade resultatet.

Algoritm exekutor- detta är objektet eller subjektet som algoritmen är utformad för att kontrollera.

Utförarens kommandosystem (SCS) är hela uppsättningen kommandon som utföraren kan utföra.

Algoritmens egenskaper: förståelighet, noggrannhet, ändlighet.

Klarhet: Algoritmen består endast av kommandon som ingår i utförarens SKI.

Noggrannhet: Varje kommando i kontrollalgoritmen bestämmer den entydiga handlingen hos utföraren.

Efterbehandling (eller prestanda): exekvering av algoritmen måste leda till ett resultat i ett begränsat antal steg.

Utförarens miljö: miljön i vilken utövaren verkar.

En viss sekvens av handlingar hos utövaren gäller alltid för vissa källdata. Till exempel, för att förbereda en maträtt enligt ett kulinariskt recept, behöver du lämpliga produkter (data). För att lösa ett matematiskt problem (att lösa en andragradsekvation) behöver du initiala numeriska data (ekvationskoefficienter).

Fullständig datauppsättning: en nödvändig och tillräcklig uppsättning data för att lösa uppgiften (få önskat resultat).

Metoder för att skriva algoritmer.

De vanligaste metoderna är: grafisk, verbal och i formen datorprogram.

Grafisk metod innebär användning av vissa grafiska symboler - block.

Blocknamn	Blockbeteckning	Innehåll
Bearbeta		Databehandling
Beslutsfattande		Ett logiskt block för att kontrollera sanningen eller falskheten i ett visst tillstånd
Dataöverföring		Inmatning eller utmatning av information
Starta, sluta		Start eller slut av programmet
Modifiering		Organisation av en cyklisk process - cykelhuvud

Samlingen av block bildar den sk algoritmflödesschema.

Verbal inspelning Algoritmer är främst fokuserade på den mänskliga utföraren och tillåter olika inspelning av instruktioner, men inspelningen måste vara ganska exakt.

När du skriver algoritmer i formuläret program datorer använder programmeringsspråk - system för kodning av instruktioner och regler för deras användning. Skrivalgoritmer i form av program kännetecknas av en hög grad av formalisering.

Algoritmer för att arbeta med kvantiteter. Grundläggande algoritmiska strukturer.

En kvantitet är ett enda informationsobjekt som har ett namn, ett värde och en typ.

Utföraren av algoritmer för att arbeta med kvantiteter kan vara en person eller en speciell teknisk anordning, till exempel en dator. En sådan artist måste ha minne för att lagra mängder.

Kvantiteter kan vara konstanta eller varierande.

Konstant värde (konstant)ändrar inte sitt värde under exekveringen av algoritmen. En konstant kan betecknas med sitt eget värde (siffrorna 10, 3,5) eller med ett symboliskt namn (tal ).

Variabelt värde kan ändra värdet under exekveringen av algoritmen. En variabel betecknas alltid med ett symboliskt namn (X, A, R5, etc.).

Typ av kvantitet definierar uppsättningen värden som ett värde kan ta och uppsättningen av åtgärder som kan utföras med det värdet. Grundläggande typer av kvantiteter: heltal, verkligt, symboliskt, logiskt.

Uttryck- en post som definierar sekvensen av åtgärder på kvantiteter. Ett uttryck kan innehålla konstanter, variabler, operationstecken och funktioner. Exempel:

A + B; 2*X-Y; K + L - sin(X)

Ett tilldelningskommando är ett exekveringskommando som resulterar i att en variabel får ett nytt värde. Kommandoformat:

variabelnamn>:=uttryck>

Tilldelningskommandot utförs i följande ordning: först beräknas det, sedan tilldelas det resulterande värdet till en variabel.

Exempel. Låt variabel A ha värdet 6. Vilket värde kommer variabel A att få efter att ha utfört kommandot: A:= 2 * A - 1?
Lösning. Att beräkna uttrycket 2*A - 1 med A=6 ger talet 11. Det betyder att det nya värdet på variabeln A blir lika med 11.

I det följande kommer det att antas att utföraren av algoritmer för att arbeta med kvantiteter är en dator. Vilken algoritm som helst kan byggas från kommandon uppgifter, inmatning, produktion, förgrening Och cykel.

Inmatningskommando- ett kommando genom vilket variabelvärden ställs in via inmatningsenheter (till exempel ett tangentbord).

Exempel: inmatning A - anger värdet för variabel A från datorns tangentbord.

Utdatakommando: Ett kommando som visar värdet av en kvantitet på en datorutmatningsenhet (som en bildskärm).

Exempel: slutsats X - värdet på X-variabeln visas på skärmen.

Filialkommando- delar upp algoritmen i två vägar beroende på något tillstånd; sedan går exekveringen av algoritmen till allmän fortsättning. Förgrening kan vara komplett eller ofullständig. Beskrivning av förgrening i blockdiagram och i algoritmiskt språk:

Här betyder en serie ett eller flera sekventiella kommandon; kv - slutet av förgrening.

Loop kommando säkerställer upprepad exekvering av en sekvens av kommandon (loopkropp) baserat på något villkor.

Slinga med förutsättning- en loop vars exekvering upprepas tills loopvillkoret är sant:

Slinga med parameter- upprepad exekvering av loopkroppen medan heltalsparametern går genom uppsättningen av alla värden från initial (In) till final (Ik):

Exempel. Två enkla bråk ges. Skapa en algoritm för att erhålla en bråkdel som är resultatet av deras division.
Lösning. I algebraisk form ser lösningen på problemet ut så här:
a/b: c/d = a*d/b*c = m/n
De initiala data är fyra heltalsstorheter: a, b, c, d. Resultatet är två heltal m och n.

alg dividera bråk
intakt a, b, c, d, m, n
starta inmatning a, b, c, d
m:=a*d
n:=b*c
utgång "Numerator=", m
utgång "Nämnare=", n
koi

Observera att för att mata ut text (valfri teckensekvens) måste den skrivas inom citattecken i kommandot slutsats.

Efimova O., Morozov V., Ugrinovich N. Kurs i datateknik med grunderna i datavetenskap. Handledning för gymnasiet. - M.: LLC "AST Publishing House"; ABF, 2000
Problembok-workshop i datavetenskap. I 2 volymer/Ed. I. Semakina, E. Henner. - M.: Laboratoriet för grundläggande kunskaper, 2001.
Ugrinovich N. Datavetenskap och informationsteknologi. 10-11 betyg - M.: Laboratory of Basic Knowledge, JSC "Moscow Textbooks", 2001

Uppgifter och tester på ämnet "Algorithms and executors"

Konstnärsledningsritare - Algoritmer 6:e klass
Lektioner: 4 inlämningsuppgifter: 9 prov: 1
2 uppgifter: 9 tester: 1

Kära elev!

Kunskaper om ämnet "Algorithms and Executors" är nödvändigt i första hand för vidare studier av programmering. Programmeringsspråket QBasic valdes som grund för att studera programmering. Vi övergav idén om att inkludera Visual Basic eller något annat objektorienterat programmeringsspråk i vår kurs, eftersom detta tillvägagångssätt ännu inte har använts i stor utsträckning i de flesta gymnasieskolor i Ryska federationen. Dessutom bygger objektorienterad programmering på principerna för klassisk Dos-programmering.

Vår kurs är utformad för det allmänna utbildningsprogrammet. När du förbereder dig för inträdesprov i informationsteknologi till universitet måste du bekanta dig med detaljerna för att studera programmering vid ett givet universitet. I vissa fall är det nödvändigt med en fördjupning av ett antal ämnen, till exempel "Arrayer". Du bör vara uppmärksam på detta när du studerar programmeringslitteratur, kanske du bör använda metodologiska rekommendationer om förberedelser inför prov, som för närvarande publiceras på de flesta lärosäten.

Sammanfattningsvis noterar vi att uppnå "aerobatics" i programmering endast är möjligt med konstant övning och att lösa specifika tillämpade problem.

Populär i kategorin: