| § 2.1. Algoritmi i izvršioci
Lekcija 14
§ 2.1. Algoritmi i izvršioci
Ključne riječi:
Algoritam
svojstva algoritma (diskretnost; razumljivost; određenost; efektivnost; masovni karakter)
izvršilac
karakteristike izvođača (opseg zadataka koje treba riješiti; okruženje; način rada; komandni sistem)
formalno izvršenje algoritma
2.1.1. Koncept algoritma
Svaka osoba u svakodnevnom životu, u školi ili na poslu, rješava ogroman broj problema najrazličitije složenosti. Složeni problemi zahtijevaju puno razmišljanja kako bi se pronašli rješenje; osoba bez oklijevanja, automatski rješava jednostavne i poznate zadatke. U većini slučajeva, rješenje svakog problema može se podijeliti na jednostavne korake (korake). Za mnoge od ovih zadataka (instaliranje softvera, sastavljanje ormara, kreiranje web stranice, rukovanje tehničkim uređajem, kupovina avio karte putem interneta, itd.) već su razvijena i ponuđena uputstva korak po korak, sa sekvencijalnim čijim izvođenjem možete doći do željenog rezultata.
Primjer 1. Zadatak "Pronađi aritmetičku sredinu dva broja" rješava se u tri koraka:
1) pomisli na dva broja;
2) sabirati dva zamišljena broja;
3) dobijeni iznos podijelite sa 2.
Primjer 2. Zadatak "Uplatite novac na telefonski račun" podijeljen je u sljedeće korake:
1) idite na terminal za plaćanje;
2) izabrati telekom operatera;
3) upisati broj telefona;
4) proveri tačnost unetog broja;
5) ubaci novčanicu u akceptor novčanica;
6) sačekati poruku o uplati novca na račun;
7) primiti ček.
Primjer 3. Faze rješavanja problema "Nacrtaj smiješnog ježa" prikazane su grafički:
Pronalaženje aritmetičke sredine, polaganje novca na telefonski račun i crtanje ježa su na prvi pogled potpuno različiti procesi. Ali imaju jednu zajedničku stvar: svaki od ovih procesa je opisan nizovima kratkih uputstava, čije će precizno praćenje omogućiti da dobijete željeni rezultat. Sekvence instrukcija date u primjerima 1-3 su algoritmi za rješavanje odgovarajućih problema. Izvršitelj ovih algoritama je čovjek.
Algoritam može predstavljati opis određenog niza proračuna (primjer 1) ili koraka nematematičke prirode (primjeri 2-3). Ali u svakom slučaju, prije njegovog razvoja moraju biti jasno definirani početni uslovi (početni podaci) i ono što se želi dobiti (rezultat). Možemo reći da je algoritam opis niza koraka u rješavanju problema, koji vodi od početnih podataka do traženog rezultata.
Općenito, šema algoritma se može predstaviti na sljedeći način (slika 2.1).
Rice. 2.1. Opća šema algoritma
Algoritmi su pravila sabiranja, oduzimanja, množenja i dijeljenja brojeva koji se uče u školi, mnoga gramatička pravila, pravila geometrijskih konstrukcija itd.
Animacije "Rad s algoritmom" (193576), "Najveći zajednički djelitelj" (170363), "Najmanji zajednički višekratnik" (170390) pomoći će vam da zapamtite neke od algoritama naučenih u lekcijama ruskog jezika i matematike (http:/ /sc.edu.ru /).
Primjer 4. Neki algoritam dovodi do činjenice da se iz jednog niza znakova dobiva novi niz na sljedeći način:
1. Izračunava se dužina (u znakovima) originalnog niza znakova.
2. Ako je dužina originalnog lanca neparna, tada se originalnom lancu s desne strane dodjeljuje broj 1, inače se lanac ne mijenja.
3. Simboli se zamjenjuju u parovima (prvi - sa drugim, treći - sa četvrtim, peti - sa šestim, itd.).
4. Desno od rezultirajućeg lanca dodijeljen je broj 2.
Rezultirajući lanac je rezultat algoritma.
Dakle, ako je početni lanac bio A # V, onda će rezultat algoritma biti lanac # A1B2, a ako je originalni lanac bio ABC @, onda će rezultat algoritma biti lanac BA @ B2.
2.1.2. Algoritam executor
Svaki algoritam je dizajniran za određenog izvođača.
Izvršilac je neki objekat (čovek, životinja, tehničko sredstvo) sposoban da izvrši određeni skup komandi.
Razlikovati formalni i neformalni izvođači... Formalni izvršilac uvijek izvodi istu komandu na isti način. Neformalni izvođač može izvršiti naredbu na različite načine.
Razmotrimo detaljnije skup formalnih izvođača. Formalni izvođači su neuobičajeno raznoliki, ali se za svakog od njih mogu navesti sljedeće karakteristike: opseg zadataka koji se rješavaju (svrha), okruženje, sistem komandovanja i način rada.
Raspon zadataka koje treba riješiti... Svaki izvođač je kreiran za rješavanje određenog niza zadataka - izgradnju lanaca simbola, izvođenje proračuna, crtanje crteža na ravni, itd.
Umetničko okruženje... Područje, okruženje, uslovi u kojima izvođač djeluje obično se nazivaju okruženjem datog izvođača. Početni podaci i rezultati bilo kog algoritma uvek pripadaju okruženju izvršioca kome je algoritam namenjen.
Komandni sistem izvršitelja... Instrukcija izvođaču da izvrši zasebnu završenu radnju naziva se komanda. Ukupnost svih naredbi koje može izvršiti određeni izvođač čini sistem naredbi za ovog izvođača (SKI). Algoritam se sastavlja uzimajući u obzir mogućnosti određenog izvođača, drugim riječima, u sistemu komandi izvođača koji će ga izvršiti.
Načini rada izvođača... Za većinu izvođača omogućeni su načini direktne kontrole i programske kontrole. U prvom slučaju, izvršilac očekuje komande od osobe i odmah izvršava svaku primljenu komandu. U drugom slučaju, izvršiocu se prvo daje kompletan niz naredbi (program), a zatim sve te komande izvršava u automatskom režimu. Jedan broj izvođača radi samo u jednom od ovih načina.
Razmotrimo primjere izvođača.
Primjer 5. Umetnik Kornjača se kreće po ekranu računara, ostavljajući trag u obliku linije.
Komandni sistem kornjače sastoji se od sljedećih naredbi:
1. Naprijed n (gdje je n cijeli broj) - uzrokuje da se kornjača kreće za n koraka u smjeru kretanja - u smjeru u kojem su joj glava i tijelo okrenuti;
2. Desno m (gdje je m cijeli broj) - uzrokuje promjenu smjera kretanja kornjače za m stupnjeva u smjeru kazaljke na satu.
Snimanje Ponovi k [<Команда1> <Команда2> ... <Командаn>]
znači da će se niz naredbi u zagradama ponoviti k puta.
Razmislite kakav će se oblik pojaviti na ekranu nakon što Kornjača izvede sljedeći algoritam.
Ponovite 12 [Desno 45 Naprijed 20 Desno 45]
Primjer 6. Sistem komandi izvršioca Kalkulator se sastoji od dve komande, kojima se dodeljuju brojevi:
1 - oduzmi 1
2 - pomnožite sa 3
Prvi od njih smanjuje broj za 1, drugi povećava broj za 3 puta. Prilikom snimanja algoritama, radi sažetosti, naznačeni su samo brojevi komandi. Na primjer, algoritam 21212 znači sljedeći niz naredbi:
Pomnožite sa 3
oduzmi 1
pomnoži sa 3
oduzmi 1
pomnoži sa 3
Ovaj algoritam pretvara broj 1 u 15:
((1 3 - 1) 3 - 1) 3 = 15.
Primjer 7. Izvršitelj Robot djeluje na kariranom polju, između susjednih ćelija koje mogu biti zidovi. Robot se kreće po ćelijama polja i može izvršiti sljedeće komande, kojima se dodjeljuju brojevi:
1 - gore
2 - dolje
3 - desno
4 - lijevo
Kada se svaka takva naredba izvrši, robot se pomiče u susjednu ćeliju u određenom smjeru. Ako u ovom smjeru postoji zid između ćelija, tada je robot uništen.
Šta se dešava sa robotom ako izvrši niz komandi 32323 (ovde brojevi označavaju brojeve komandi), počevši od ćelije A? Koju sekvencu komandi robot treba da izvrši da bi se kretao od ćelije A do ćelije B, a da se ne uruši zbog sudara sa zidovima?
Prilikom razvoja algoritma:
1) ističu se objekti koji se pojavljuju u zadatku, utvrđuju se svojstva objekata, odnosi između objekata i moguće radnje sa objektima;
2) utvrđuju se početni podaci i traženi rezultat;
3) utvrđuje se redosled radnji izvođača koji obezbeđuje prelazak sa početnih podataka na rezultat;
4) redosled radnji se snima pomoću komandi koje su uključene u sistem komandi izvođača.
Možemo reći da je algoritam model aktivnosti izvršioca algoritama.
2.1.3. Svojstva algoritma
Ne može se svaka instrukcija, niz instrukcija ili akcioni plan smatrati algoritmom. Svaki algoritam nužno ima sljedeća svojstva: diskretnost, razumljivost, određenost, efikasnost i masovnost.
Svojstvo diskretnosti znači da je način rješavanja problema podijeljen u zasebne korake (akcije). Svaka radnja odgovara nalogu (naredbi). Tek nakon završetka jedne naredbe, izvršilac može preći na sljedeću komandu.
Svojstvo razumljivosti znači da se algoritam sastoji samo od naredbi koje su uključene u sistem komandi izvršioca, odnosno od onih naredbi koje izvršilac može da uoči i prema kojima može izvršiti tražene radnje.
Sigurnost imovine znači da u algoritmu ne postoje naredbe čije značenje može biti dvosmisleno protumačeno od strane izvršioca; neprihvatljive su situacije kada nakon izvršenja naredne komande izvršiocu nije jasno koju naredbu da izvrši. Zbog toga je rezultat algoritma jedinstveno određen skupom početnih podataka: ako se algoritam primjenjuje nekoliko puta na isti skup početnih podataka, onda je izlaz uvijek isti rezultat.
Svojstvo performansi znači da bi algoritam trebao dati rezultat nakon konačnog, moguće vrlo velikog broja koraka. U ovom slučaju, rezultat se smatra ne samo odgovorom zbog konstatacije problema, već i zaključkom da je nemoguće iz bilo kojeg razloga nastaviti rješavanje ovog problema.
Svojstvo masovnog karaktera znači da algoritam treba da pruži mogućnost njegove primene za rešavanje bilo kog problema iz određene klase problema. Na primjer, algoritam za pronalaženje korijena kvadratne jednačine trebao bi biti primjenjiv na bilo koju kvadratnu jednačinu, algoritam za prelazak ulice trebao bi biti primjenjiv bilo gdje na ulici, algoritam za pripremu lijeka trebao bi biti primjenjiv za pripremu bilo koje njegove količine , itd.
Primjer 8. Razmotrimo jednu od metoda za pronalaženje svih prostih brojeva koji ne prelaze neki prirodni broj n. Ova metoda se naziva "Eratostenovo sito" po imenu starogrčkog naučnika Eratostena (III vek pne) koji ju je predložio.
Da biste pronašli sve proste brojeve koji nisu veći od datog broja n, slijedeći Eratostenovu metodu, trebate izvršiti sljedeće korake:
1) ispisati u red sve prirodne brojeve od 2 do n (2, 3, 4, ..., n);
2) staviti u okvir 2 - prvi prost broj;
3) izbrisati sa liste sve brojeve deljive poslednjim pronađenim prostim brojem;
4) pronađite prvi neobeleženi broj (označeni brojevi su precrtani brojevi ili brojevi u okviru) i stavite ga u okvir - to će biti sledeći prost broj;
5) ponovite korake 3 i 4 sve dok ne bude neoznačenih brojeva.
Vizuelniji prikaz metode pronalaženja prostih brojeva možete dobiti uz pomoć animacije "Eratostenovo sito" (180279) koja se nalazi u Jedinstvenoj kolekciji digitalnih obrazovnih resursa.
Razmatrani slijed radnji je algoritam, budući da zadovoljava svojstva:
diskretnost- proces pronalaženja prostih brojeva podijeljen je na korake;
razumljivost- svaka naredba je razumljiva učeniku 8. razreda koji izvodi ovaj algoritam;
sigurnost- svaku komandu izvođač interpretira i izvršava nedvosmisleno; postoje uputstva o redosledu izvršavanja komandi;
efektivnost- nakon određenog broja koraka postiže se rezultat;
masovni karakter- redoslijed radnji je primjenjiv za bilo koji prirodni n.
Razmatrana svojstva algoritma omogućavaju precizniju definiciju algoritma.
Algoritam je opis niza radnji namenjenih određenom izvođaču, koje vode od početnih podataka do traženog rezultata, koji ima svojstva diskretnosti, razumljivosti, određenosti, efektivnosti i masovnosti.
2.1.4. Sposobnost automatizacije ljudskih aktivnosti
Razvoj algoritma je obično dugotrajan zadatak koji od osobe zahtijeva duboko znanje, domišljatost i dugotrajnost.
Rješenje problema prema gotovom algoritmu zahtijeva od izvođača samo striktno pridržavanje datih uputstava.
Primjer 9. Iz gomile koja sadrži bilo koji, više od tri, broj bilo kojeg predmeta, dva igrača naizmjenično uzimaju jedan ili dva predmeta. Pobjednik je onaj koji svojim sljedećim potezom može pokupiti sve preostale predmete.
Razmotrimo algoritam po kojem će prvi igrač sigurno sebi osigurati pobjedu.
1. Ako je broj predmeta u gomili višestruki od 3, onda prepustite potez protivniku, u suprotnom započnite igru uzimajući 1 ili 2 predmeta tako da broj predmeta bude višestruki od 3.
2. Svaki put, svojim sljedećim potezom, dopunite broj predmeta koje je protivnik uzeo na 3 (broj preostalih objekata mora biti višestruki od 3).
Izvođač možda ne ulazi u značenje onoga što radi, i ne argumentuje zašto to radi, a ne drugačije, odnosno može djelovati formalno. Sposobnost izvođača da djeluje formalno pruža sposobnost automatizacije ljudskih aktivnosti. Za ovo:
1) proces rešavanja problema je predstavljen u obliku niza najjednostavnijih operacija;
2) kreira se mašina (automatski uređaj) koja je sposobna da ove operacije obavlja redosledom koji je naveden u algoritmu;
3) osoba je oslobođena rutinskih aktivnosti, izvršavanje algoritma je povjereno automatskom uređaju.
NAJVAŽNIJE
Izvršitelj- neki objekat (čovek, životinja, tehničko sredstvo) koji je sposoban da izvrši određeni skup komandi.
Formalni izvršilac uvijek izvodi istu komandu na isti način. Za svakog formalnog izvođača možete navesti: raspon zadataka koje treba riješiti, okruženje, komandni sistem i način rada.
Algoritam- opis redosleda radnji namenjenih konkretnom izvođaču, koji vodi od početnih podataka do traženog rezultata, koji ima svojstva diskretnosti, razumljivosti, određenosti, efektivnosti i masovnosti.
Sposobnost izvođača da glumi formalno pruža mogućnost automatizacije ljudskih aktivnosti.
Pitanja i zadaci
1. Pročitajte materijale prezentacije za paragraf koji se nalazi u elektronskom prilogu udžbenika. Da li prezentacija nadopunjuje informacije u tekstu pasusa? Koje slajdove možete dodati svojoj prezentaciji?
2. Šta se zove algoritam?
3. Pronađite sinonime za riječ "recept".
4. Navedite primjere algoritama koje učite u školi.
5. Ko može biti izvršilac algoritma?
6. Navedite primjer formalnog ugovarača. Navedite primjer kada osoba djeluje kao formalni izvršilac.
7. Šta određuje opseg zadataka izvršioca „računara“?
8. Razmotrite program za obradu teksta na vašem računaru kao izvršilac. Opišite niz zadataka koje rješava ovaj izvođač i njegovo okruženje.
9. Šta je naredba, sistem komandi izvršioca?
10. Koje komande treba da ima robot koji obavlja funkcije:
a) blagajnik u prodavnici;
b) domar;
c) zaštitar?
11. Navedite glavna svojstva algoritma.
12. Do čega može dovesti nedostatak nekog svojstva u algoritmu? Navedite primjere.
13. Koja je važnost mogućnosti formalnog izvršenja algoritma?
14. Niz brojeva se gradi prema sljedećem algoritmu: prva dva broja niza se uzimaju jednakima 1; svaki sljedeći broj u nizu uzima se jednak zbiru prethodna dva broja. Zapišite prvih 10 članova ovog niza. Saznajte kako se zove ovaj niz.
15. Neki algoritam dobija novi niz iz jednog niza simbola na sledeći način. Prvo se upisuje originalni lanac znakova, nakon čega se ispisuje originalni lanac znakova obrnutim redoslijedom, zatim se upisuje slovo koje slijedi u ruskoj abecedi nakon slova koje je bilo na posljednjem mjestu u originalnom lancu. Ako je u originalnom lancu slovo "I" na posljednjem mjestu, onda je slovo "A" napisano kao sljedeće slovo. Rezultirajući lanac je rezultat algoritma. Na primjer, ako je originalni niz znakova bio "DOM", tada će rezultat algoritma biti string "DOMMODN". Dat je niz znakova "COM". Koliko će slova "O" biti u lancu znakova, što će se ispostaviti ako algoritam primijenite na ovaj lanac, a zatim ponovo primijenite algoritam na rezultat njegovog rada?
16. Pronađite na internetu animaciju koraka Eratostenovog algoritma. Pronađite sve proste brojeve do 50 koristeći Eratostenov algoritam.
17. Šta će biti rezultat izvršenja algoritma od strane Kornjače (vidi primjer 5)?
18. Zapišite algoritam za izvršni kalkulator (vidi primjer 6), koji ne sadrži više od 5 naredbi:
a) dobijanje od broja 3 broja 16;
b) dobijanje od broja 1 broja 25.
19. Sistem komandi konstruktora izvršioca sastoji se od dve komande, kojima se dodeljuju brojevi:
1 - dodijeliti 2
2 - podijeliti sa 2
Prema prvom od njih, broju na desnoj strani pripisuje se 2, a prema drugom broj je djeljiv sa 2. Kako će se pretvoriti broj 8 ako izvršilac izvrši algoritam 22212? Kreirajte algoritam u komandnom sistemu ovog izvršioca, prema kojem će se broj 1 pretvoriti u broj 16 (algoritam ne smije sadržavati više od 5 naredbi).
20. U kojoj ćeliji treba biti izvršilac Robot (primjer 7) da bi se vratio u nju nakon izvršenja algoritma 3241?
Besplatni softver:
Kumir sistem - Skup obrazovnih svjetova (preuzmite programsku arhivu sa stranice) ili posjetite stranicu Kumir ((http://www.niisi.ru/kumir/)
Riječ "algoritam" potiče od imena arapskog matematičara al-Khwarizmija iz 9. stoljeća, koji je formulisao pravila za izvođenje aritmetičkih operacija.
Algoritam- tačna i razumljiva instrukcija izvođaču da izvrši konačni niz naredbi koji vodi od početnih podataka do početnog rezultata.
Primjeri: dnevna rutina, postupak kuhanja, upute itd.)
Algoritam executor Je onaj koji izvršava algoritam (čovek, životinja, mašina, kompjuter).
Komandni sistem izvršitelja- ovo je čitav skup naredbi koje izvođač zna da izvede (razumije). Algoritam se može izgraditi samo od naredbi uključenih u sistem komandi izvršioca.
na primjer, izvođač Robot može izvršavati komande naprijed, nazad, lijevo, desno, farbati. Kreće se oko polja ćelije, omeđenog zidom i koji sadrži zidove. Robot ne može proći kroz zid.
Svojstva algoritma:
1.Efikasnost (ud)- mogućnost dobijanja rezultata iz početnih podataka u konačnom broju koraka. (Na primjer, kada se izvodi algoritam sabiranja, 2 broja bi trebala dobiti zbroj).
2.Masovni karakter- mogućnost primjene algoritma na veliki broj različitih početnih podataka. (Na primjer, možete dodati bilo koja 2 broja, poznavajući algoritam sabiranja.)
3.Determinizam(sigurnost, tačnost) - svaki tim mora nedvosmisleno definirati radnju izvođača.
4.Shvatljivost- komanda mora biti napisana na jeziku razumljivom računaru.
5.Diskretnost- razdvajanje algoritma u zasebne komande.
Metode snimanja algoritama:
1) Na prirodnom jeziku - snimanje u obliku posebnih naredbi na jeziku razumljivom osobi.
2) Grafički - na jeziku blok dijagrama, koristeći geometrijske oblike (oval, pravougaonik, paralelogram, romb).
3) Na algoritamskom jeziku - jezik za pisanje algoritama za nastavu programiranja. Timovi se snimaju na ruskom jeziku.
4) U programskom jeziku - program. Programski jezici: Basic, Pascal, C, Visual Basic.
B7 Osnovne algoritamske strukture: praćenje, grananje, petlja; sliku na blok dijagramima. Podjela zadataka na podzadatke. Pomoćni algoritmi.
Algoritamske konstrukcije. Unutar algoritama se mogu razlikovati grupe koraka koji se razlikuju po unutrašnjoj strukturi – algoritamske konstrukcije.
Osnovne algoritamske konstrukcije su linearni niz koraka (ili sekvenciranja), grananja i petlje.
Poziva se algoritam u kojem se naredbe izvršavaju uzastopno jedna za drugom linearni algoritam.
Ovako izgleda linearni algoritam na jeziku blok dijagrama:
Primjer: algoritam za uključivanje računara:
- Uključite napajanje računara (pritisnite dugme na štitniku od prenapona).
- Uključite monitor, štampač.
- Pritisnite dugme za napajanje na sistemskoj jedinici.
- Sačekajte dok se operativni sistem ne učita i pojavi se radna površina.
- Na posao.
U ovom algoritmu sve se radnje moraju izvoditi uzastopno jedna za drugom: ne možete započeti rad ako napajanje ili monitor nisu uključeni.
Algoritamska struktura" grananje„Uključeno stanje, u zavisnosti od istinitosti uslova, izvršava se jedan ili drugi niz naredbi (serija).
Uslov je izjava koja može biti istinita ili lažna. U uslovu se dva broja, dva niza, dvije varijable ili izrazi stringova međusobno upoređuju korištenjem operacija poređenja (>,<, =, >=, <=).
U algoritamskim strukturama ciklus uključuje niz naredbi koje se izvršavaju više puta. Ovaj niz naredbi se zove tijelo ciklusa.
Ciklične algoritamske strukture su dvije vrste:
- brojač ciklusa, u kojem se tijelo petlje izvršava određeni broj puta;
- uslovne petlje, u kojem se tijelo petlje izvršava sve dok je uvjet ispunjen.
Ciklus sa brojačem- koristi se kada se unaprijed zna koliko se ponavljanja tijela ciklusa mora izvesti.
Molimo obustavite AdBlock na ovoj stranici.
U ovoj lekciji analiziraćemo neke od teorijskih koncepata koji formalizuju koncept programiranja. Istovremeno ćemo preciznije formulisati glavni zadatak vaše obuke.
Za početak predlažem da se malo poigrate sa sljedećom dječjom igračkom. Dovršite prvih pet zadataka, vratite se i nastavite čitati lekciju.
Slika 1 Snimak ekrana polja za igru na code.org
Nadam se da ćeš uspjeti. Sada ćemo, koristeći ovaj primjer, opisati nekoliko osnovnih koncepata:
- izvršilac;
- sistem izvršnih komandi;
- algoritam.
U igrački kontrolišemo crvenu pticu. Zadatak svake faze: dovesti pticu do svinje. Ptica može izvršavati određene komande, na primjer: krenuti naprijed, skrenuti lijevo, skrenuti desno itd.
Osoba, mašina ili uređaj koji može izvršiti određene komande naziva se izvršilac. U ovoj igrački, očigledno, izvođač je ptica. Poziva se skup naredbi koje izvođač razumije i zna da izvede sistem komandi izvršioca.
Niz naredbi koje izvršitelj mora izvršiti da bi riješio problem naziva se algoritam.
Potrebno je fokusirati se na nekoliko tačaka.
Izvođač može izvršiti samo one naredbe koje su uključene u njegov komandni sistem.
To znači, na primjer, da ne možete pisati izvođaču ptica: "Idi do svinje!" Tačnije, možete zapisati, ali ništa se neće dogoditi, tk. izvršilac takvih komandi ne zna.
Možete pisati postojeće naredbe bilo kojim redoslijedom koji smatrate ispravnim. Vaš zadatak kao programera je da podijelite veliki složeni zadatak na male odvojene korake, od kojih će svaki biti jasan izvršiocu. Zavadi pa vladaj opet radi.
Izvođač radi upravo ono što mu algoritam nalaže.
Izvođač ptica je vrlo povjerljiv. Ne dovodi u pitanje šta pišete u programu. Ako, na primjer, zaboravite rasklopiti pticu, ona će se zabiti u zid. Stoga o svemu morate voditi računa sami.
Vaši budući programi često neće raditi onako kako ste namjeravali. Greške se dešavaju svima. Važno je shvatiti da ovo nije kompjuterska budala, ali ste pogriješili u algoritmu. Nemojte biti kao loši programeri koji uvijek imaju krivnju za program.
Sada, sa ilustrativnog primjera, pređimo na kompjutersku stvarnost. Mi pišemo programe za računar, što znači da je računar u našem slučaju izvršitelj. Sistem komandi - standardne funkcije i konstrukcije jezika C.
Koji je glavni zadatak Vašeg podučavanja osnova programiranja? Savladajte vještinu algoritamskog razmišljanja. Odnosno, naučite kako zapisati rješenje različitih problema u obliku algoritma za određenog izvođača (u našem slučaju, kompjuter).
Dakle, da rezimiramo:
Računarski program- algoritam za rješavanje problema, napisan u programskom jeziku.
Algoritam - tačan opis redosleda radnji koje mora izvršiti izvođač da bi rešio problem.
Izvršitelj - osoba ili neki uređaj koji može razumjeti i izvršiti određeni skup naredbi.
Koncept algoritma. Algoritamski izvršioci. Svojstva algoritma
Koncept algoritma je fundamentalan za informatiku kao i koncept informacije. Postoji mnogo različitih definicija algoritma, budući da je ovaj koncept prilično širok i koristi se u različitim oblastima nauke, tehnologije i svakodnevnog života.
Algoritam je razumljiv i precizan niz radnji koji opisuje proces transformacije objekta iz početnog stanja u konačno stanje.
Algoritam je precizan opis niza radnji usmjerenih na rješavanje datog problema, namijenjen određenom izvođaču.
Performer algoritam može biti ili osoba (recepti, razna uputstva, algoritmi za matematičke proračune) ili tehnički uređaj. Postoje razne mašine (računari, industrijski roboti, savremeni kućni aparati). formalni izvođači algoritmi. Formalni izvršilac nije obavezan da razumije suštinu problema koji se rješava, ali je potrebno tačno izvršenje niza naredbi.
Algoritam se može napisati na različite načine (verbalni opis, grafički opis - blok dijagram, program na nekom od programskih jezika, itd.). Program je algoritam napisanprogramski jezik .
Da biste kreirali algoritam (program), morate znati:
kompletan skup početnih podataka problema (početno stanje objekta);
svrha kreiranja algoritma (konačno stanje objekta);
sistem komandi izvršioca (tj. skup komandi koje izvršitelj razume i može da izvrši).
Rezultirajući algoritam (program) mora imati sljedeći skup svojstava:
diskretnost (algoritam je podijeljen u zasebne korake - komande);
nedvosmislenost (svaka komanda određuje jedinu moguću radnju izvođača);
razumljivost (sve komande algoritma su uključene u sistem komandi izvršioca);
efikasnost (izvođač mora riješiti problem u konačnom broju koraka).
Većina algoritama također ima svojstvo masovni karakter (koristeći isti algoritam, mnogi slični problemi se mogu riješiti).
Metode za opisivanje algoritama
Gore je napomenuto da se isti algoritam može napisati na različite načine. Algoritam se može napisati prirodni jezik. Kao takvi koristimo recepte, uputstva itd. Za snimanje algoritama namijenjenih formalnim izvođačima, specijal programski jezici... Bilo koji algoritam se može opisati grafički u obliku blok dijagrama... Za to je razvijen poseban sistem notacije:
|
Oznaka |
Opis |
Bilješke (uredi) |
|
Početak i kraj algoritma | ||
|
|
Unos i izlaz podataka. |
Izlaz podataka se ponekad naziva drugačije:
|
|
|
Akcija |
U računskim algoritmima, ovo je zadatak |
|
|
Viljuška |
Vilica - komponenta potrebna za implementaciju grana i petlji |
|
|
Početak ciklusa s parametrom | |
|
|
Tipičan proces |
U programiranju, procedurama ili potprogramima |
|
|
Prijelazi između blokova |
Dajemo primjer opisa algoritma za zbrajanje dvije veličine u obliku blok dijagrama:
Ovakav način opisivanja algoritma je najgrafičniji i najrazumljiviji za ljude. Stoga se algoritmi formalnih izvršitelja obično prvo razvijaju u obliku blok dijagrama, a tek onda kreiraju program na jednom odprogramski jezici .
Tipične algoritamske strukture
Programer ima sposobnost da dizajnira i koristi netipične algoritamske strukture, međutim, to nije neophodno. Svaki proizvoljno složen algoritam može se razviti na osnovu tri tipične strukture: sukcesije, grananja i ponavljanja. U ovom slučaju, strukture se mogu poredati jedna za drugom ili ugniježditi jedna u drugu.
Linearna struktura (prati)
Najjednostavnija algoritamska struktura je linearno. U njemu se sve operacije izvode jednom redom kojim su napisane.
Grananje
V potpuno grananje postoje dve opcije za radnje izvršioca, u zavisnosti od vrednosti logičkog izraza (uslova). Ako je uslov tačan, tada će se izvršiti samo prva grana, u suprotnom će se izvršiti samo druga grana.
Druga grana može biti prazna. Ova struktura se zove nepotpuno grananje ili prelazak.
Iz nekoliko grana moguće je izgraditi konstrukciju “ izbor"(Višestruko grananje), koji će birati ne između dvije, već iz većeg broja opcija za radnje izvršitelja, ovisno o nekoliko uslova. Bitno je da se izvrši samo jedna grana - u takvoj strukturi redosled uslova postaje važan: ako je nekoliko uslova zadovoljeno, onda će samo jedan od njih raditi - prvi odozgo.
Ciklus (ponavljanje)
Ciklusomogućava vam da organizirate višestruka ponavljanja istog niza naredbi- zove se telo ciklusa. U različitim tipovima algoritama petlje, broj ponavljanja može ovisiti o vrijednosti logičkog izraza (uslova) ili može biti tvrdo kodiran u samoj strukturi. Postoje ciklusi: " prije», « ćao», ciklusi sa brojačem. U petljama "before" i "while" logički izraz (uslov) može prethoditi tijelu petlje ( preduslovna petlja) ili završiti petlju ( naknadna petlja).
Ciklusi« prije"- ponavljanje tijela ciklusa dok se ne ispuni uslov:
Ciklusi « ćao"- ponavljanje tijela ciklusa dok je uslov ispunjen(tačno):
Counter loops(sa parametrom)- ponavljanje tijela petlje određeni broj puta:
Pomoćni algoritam (potprogram, procedura)
Algoritam pomoćnika je modul kojem se može pristupiti više puta iz glavnog algoritma. Upotreba pomoćnih algoritama može značajno smanjiti veličinu algoritma i pojednostaviti njegov razvoj.
Metode za razvoj složenih algoritama
Postoje dvije metode za razvoj složenih algoritama:
Metoda sekvencijalnog detaljiranja zadataka("Top-down") je da je originalni složeni problem podijeljen na podzadatke. Svaki od podproblema razmatra se i rješava zasebno. Ako je neki od podzadataka težak, oni se također dijele na podzadatke. Proces se nastavlja sve dok se podzadaci ne svode na elementarne. Rješenja pojedinačnih podproblema se zatim skupljaju u jedan algoritam za rješavanje originalnog problema. Metoda se široko koristi jer omogućava nekoliko programera da istovremeno razviju opći algoritam koji rješava lokalne podzadatke. Ovo je preduslov za brzi razvoj softverskih proizvoda.
Način montaže("Bottom-up") je kreiranje skupa softverskih modula koji implementiraju rješenje tipičnih zadataka. Prilikom rješavanja složenog problema programer može koristiti razvijene module kao pomoćne algoritme (procedure). U mnogima sistemi za programiranje Već postoje slični skupovi modula, što uvelike pojednostavljuje i ubrzava stvaranje složenog algoritma.
Upravljački algoritmi i procesi
Kontrola - svrsishodna interakcija objekata, od kojih su neki kontrolisani, drugi su kontrolirani.
U najjednostavnijem slučaju, postoje dva takva objekta:
Sa stanovišta informatike kontrolne akcije se mogu smatrati kontrolnom informacijom. Informacije se mogu prenijeti u obliku naredbi. Poziva se niz naredbi za kontrolu objekta, koji vodi do unaprijed određenog cilja kontrolni algoritam... Prema tome, kontrolni objekat se može nazvati izvršiocem kontrolnog algoritma. U gornjem primjeru, kontrolni objekt radi "bez gledanja" šta se dešava sa kontrolnim objektom ( kontrola otvorene petlje otvoren... Druga kontrolna shema može uzeti u obzir informacije o procesima koji se dešavaju u kontrolnom objektu:
U tom slučaju, algoritam upravljanja mora biti dovoljno fleksibilan da analizira ove informacije i donese odluku o svojim daljnjim radnjama ovisno o stanju kontrolnog objekta ( povratna kontrola). Ova kontrolna shema se zove zatvoreno.
Detaljnije se proučavaju procesi upravljanja. kibernetika... Ova nauka tvrdi da se najraznovrsniji procesi upravljanja u društvu, prirodi i tehnologiji odvijaju na sličan način, poštuju iste principe.
Na početak teme
MBOU "Glinnovskaya srednja škola"
Novooskolsky okrug
Belgorod region
Plan - nacrt lekcije
(9. razred)
“Algoritmi, koncepti algoritma, svojstva algoritma. Algoritamski izvršioci"
Pripremljen od:
Učite informatiku
Tarasova N.G.
2011
Tema: Pojam algoritama, svojstva algoritma. Izvršioci algoritama, sistem komandi izvršioca. Metode za snimanje algoritama. Formalno izvođenje algoritama.
Vrsta lekcije: upoznavanje sa novim materijalom.
Ciljevi:
- Promovirati razvoj algoritamskog mišljenja;
- Dajte koncept algoritma, razgovarajte o svojstvima, dajte klasifikaciju algoritama;
- Uvesti oblik pisanja algoritama - blok dijagram.
Oprema: projektor, prezentacija.
Tokom nastave
1 org. Momenat
Pozdrav, sletanje, prozivka.
2 Ažuriranje referentnog materijala
Ljudi, recite mi, molim vas, kako razumete reč algoritam? Gdje imamo posla sa ovim konceptom?
3 Prezentacija materijala
Porijeklo pojma "algoritam" povezuje se s matematikom. Istorija njegovog nastanka je sledeća. U 9. vijeku u Bagdadu je živio naučnik al (al)-Horezmi (puno ime - Muhammad bin Musa al-Horezmi, tj. Muhamed sin Musa iz Horezma), matematičar, astronom, geograf. U jednom od svojih radova opisao je decimalni brojevni sistem i po prvi put formulisao pravila za izvođenje aritmetičkih operacija nad cijelim brojevima i običnim razlomcima. Arapski original ove knjige je izgubljen, ali je ostao latinski prijevod iz 12. vijeka, prema kojem se Zapadna Evropa upoznala sa decimalnim brojevnim sistemom i pravilima za izvođenje računskih operacija.
Al-Khwarizmi je nastojao da pravila koja je formulirao učini razumljivim. To je bilo teško postići u 9. vijeku, kada matematička simbolika (znakovi operacija, zagrade, slovne oznake, itd.) još nije bila razvijena. Ipak, uspijeva razviti jasan stil strogog verbalnog recepta koji čitatelju nije davao priliku da odstupi od propisanog ili preskoči bilo koju radnju.
Pravila u knjigama vidi-Khorezmi u latinskom prijevodu počinjala su riječima "Algorizmi je rekao". U drugim latinskim prijevodima, autor je nazvan Algoritam. Vremenom se zaboravilo da je Algorizmi (Algoritam) autor pravila, te su se ta pravila počela zvati algoritmi. Vjekovima su se razvijali algoritmi za rješavanje sve više i više klasa problema, ali sam koncept algoritma nije imao tačnu matematičku definiciju.
Trenutno je pojam algoritma razjašnjen i napravljen u XX veku u okviru nauke koja se zove teorija algoritama.
Algoritam - precizne i razumljive upute izvođaču da izvrši niz radnji u cilju rješavanja zadatka.
Algoritam - jasno organizovana sekvencijalna radnja koja vodi do određenog rezultata.
Izvršilac algoritma je neki apstraktan ili stvaransistem sposoban da izvrši radnju propisanu algoritmom (tehničkom, biološkom ili biotehničkom).
Tehnički izvršilac- bankomat;
Biološki - osoba, živi organizam;
Biotehnika - Veštačka inteligencija.
Svojstva algoritma
Diskretnost (razdvajanje, diskontinuitet) - algoritam treba napisati kao niz koraka ili faza.
Shvatljivost Izvršilac algoritma mora znati kako da izvrši ovaj algoritam.
Sigurnost (determinizam) svako pravilo algoritma treba da bude jasno, nedvosmisleno i da ne ostavlja prostora za proizvoljnost.
Zbog ovog svojstva, izvođenje algoritma je mehaničke prirode i ne zahtijeva dodatne upute.
Efikasnost(konačnost) algoritam bi trebao dovesti do rješenja problema u konačnom broju koraka.
Masovni karakter algoritam je razvijen na opći način tako da se može primijeniti za rješavanje sličnih problema. U ovom slučaju, izvorni podaci se biraju iz nekih područja, koja se nazivaju područje primjene algoritama.
Metode snimanja algoritama
Ako su svojstva sigurnosti i diskretnosti sačuvana sa određenim stepenom tačnosti, tj. u programu je moguća permutacija koraka ili sadrži poželjne, ali ne i obavezne korake, onda ovo nije algoritam, većalgoritamski recept.
Svaki algoritam je dizajniran za određeno izvođač. To može biti osoba, robot, kompjuter itd. svaki izvođač ima svoj komandni sistem. Prilikom sastavljanja algoritma morate uzeti u obzir za kojeg izvođača je dizajniran. Izvođač može izvesti algoritam bez udubljivanja u značenje onoga što radi, za ono što radi, a ipak će dobiti željeni rezultat. U takvim slučajevima se kaže da se algoritam izvršava formalno.
Forme za snimanje algoritama:
Verbalno je opis uzastopnih faza obrade podataka. Algoritam je proizvoljna prezentacija na prirodnom jeziku
Graphic - niz međusobno povezanih blokova, od kojih svaki odgovara izvršenju jedne ili više radnji.
Takav grafički prikaz naziva se blok dijagram - usmjereni graf koji označava redoslijed izvršavanja instrukcija algoritma.
Grafički oblici algoritama snimanja:
Osnovne algoritamske strukture
Pratite (linearni algoritam) petlje
Grananje
Pratiti - komande se izvršavaju jedna za drugom onim redom kojim su napisane u algoritmu. ((Primjer. Algoritam za otvaranje vrata stana: uzmite ključ, ubacite gaključaonicu, okrenite potreban broj puta, uzmite ključ, otvorite vrata. zatvori vrata)
Grananje - podaci utiču na tok algoritma, tj. zavisno od stanjaizvode se određene radnje algoritma.(Primjer, algoritam "ulaska" u vaš stan: pozovite stan; ako je neko kod kuće, sačekajte da se otvore vrata iuđite u stan, ako nema nikoga kod kuće, uzmite ključ; ...)
Ciklus (ponavljanje)- u procesu izvršavanja algoritma, određeniskup komandi. (Primjer.(Pranje 10 tanjira: uzmi tanjir, operi, stavi u sušilicu, uzmitanjir, operite, stavite u sušilicu itd. dok ne ostanete bez tanjira.)
4 Primjena stečenog znanja
Zadatak izvrši komande algoritma sa a = 1, b = 2, c = 3
