| § 2.1. Algoritmi i izvršitelji
Lekcija 14
§ 2.1. Algoritmi i izvršitelji
Ključne riječi:
Algoritam
svojstva algoritma (diskretnost; razumljivost; određenost; učinkovitost; masovni karakter)
izvršitelj
karakteristike izvođača (raspon zadataka koje treba riješiti; okruženje; način rada; sustav zapovijedanja)
formalno izvođ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 pronašli rješenje; osoba rješava jednostavne i poznate zadatke bez oklijevanja, automatski. 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 ormarića, izrada web stranice, rukovanje tehničkim uređajem, kupnja zrakoplovne karte putem interneta, itd.) već su razvijene i ponuđene upute korak po korak, sa sekvencijalnim čijom izvedbom 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) zbrojiti dva zamišljena broja;
3) dobiveni 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) odabrati telekom operatera;
3) unesite broj telefona;
4) provjeriti ispravnost upisanog broja;
5) ubaciti novčanicu u akceptor novčanica;
6) prič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 na prvi su pogled potpuno različiti procesi. Ali imaju jednu zajedničku stvar: svaki od ovih procesa opisan je nizovima kratkih uputa, točno slijedeći koje će vam omogućiti da dobijete željeni rezultat. Slijedovi instrukcija dani 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 slijeda izrač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 uvjeti (početni podaci) i ono što se želi dobiti (rezultat). Možemo reći da je algoritam opis slijeda koraka u rješavanju problema, koji vodi od početnih podataka do traženog rezultata.
Općenito, shema algoritma može se prikazati na sljedeći način (slika 2.1).
Riža. 2.1. Opća shema algoritma
Algoritmi su pravila zbrajanja, 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 na 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 duljina (u znakovima) izvornog niza znakova.
2. Ako je duljina izvornog lanca neparna, tada se izvornom lancu s desne strane dodjeljuje broj 1, inače se lanac ne mijenja.
3. Simboli se izmjenjuju u parovima (prvi - s drugim, treći - s četvrtim, peti - sa šestim, itd.).
4. Desno od rezultirajućeg lanca dodijeljen je broj 2.
Rezultirajući lanac rezultat je algoritma.
Dakle, ako je početni lanac bio A # V, tada će rezultat algoritma biti lanac # A1B2, a ako je izvorni lanac bio ABC @, tada će rezultat algoritma biti lanac BA @ B2.
2.1.2. Izvršitelj algoritma
Svaki algoritam je dizajniran za određenog izvođača.
Izvršitelj je neki objekt (čovjek, životinja, tehničko sredstvo) sposoban izvršiti određeni skup naredbi.
Razlikovati formalni i neformalni izvođači... Formalni izvršitelj uvijek izvodi istu naredbu 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 neobično raznoliki, ali za svakog od njih mogu se navesti sljedeće karakteristike: raspon zadataka koji se rješavaju (namjena), okruženje, sustav zapovijedanja i način rada.
Raspon zadataka koje treba riješiti... Svaki izvođač je stvoren za rješavanje određenog niza zadataka - izgradnju lanaca simbola, izvođenje proračuna, crtanje crteža na ravnini itd.
Umjetničko okruženje... Područje, okruženje, uvjeti u kojima izvođač djeluje obično se nazivaju okruženjem danog izvođača. Početni podaci i rezultati bilo kojeg algoritma uvijek pripadaju okruženju izvršitelja kojem je algoritam namijenjen.
Sustav zapovijedi izvršitelja... Uputa izvođaču da izvrši zasebnu dovršenu radnju naziva se naredba. Ukupnost svih naredbi koje može izvršiti određeni izvođač čini sustav naredbi za ovog izvođača (SKI). Algoritam se sastavlja uzimajući u obzir sposobnosti određenog izvođača, drugim riječima, u sustavu naredbi 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 izravnog upravljanja i upravljanja programom. U prvom slučaju, izvršitelj očekuje naredbe od osobe i odmah izvršava svaku primljenu naredbu. U drugom slučaju, izvršitelju se najprije zada kompletan slijed naredbi (program), a zatim sve te naredbe izvršava u automatskom načinu rada. Određeni broj izvođača radi samo u jednom od ovih načina.
Razmotrimo primjere izvođača.
Primjer 5. Umjetnik Kornjača se kreće po zaslonu računala, ostavljajući trag u obliku linije.
Sustav naredbi kornjače sastoji se od sljedećih naredbi:
1. Naprijed n (gdje je n cijeli broj) - uzrokuje da se kornjača kreće 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. Izvršiteljev sustav naredbi Kalkulator se sastoji od dvije naredbe kojima su dodijeljeni 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 naredbi. Na primjer, algoritam 21212 znači sljedeći niz naredbi:
Pomnožite sa 3
oduzeti 1
pomnoži sa 3
oduzeti 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 kockastom polju između čijih susjednih ćelija mogu biti zidovi. Robot se kreće po ćelijama polja i može izvršiti sljedeće naredbe, kojima su dodijeljeni brojevi:
1 - gore
2 - dolje
3 - desno
4 - lijevo
Kada se svaka takva naredba izvrši, robot se pomiče u susjednu ćeliju u navedenom smjeru. Ako u tom smjeru postoji zid između stanica, tada je robot uništen.
Što se događa s robotom ako izvrši slijed naredbi 32323 (ovdje brojevi označavaju brojeve naredbi), počevši od ćelije A? Koji slijed naredbi bi robot trebao izvršiti kako bi se kretao iz ćelije A u ćeliju 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 s objektima;
2) utvrđuju se početni podaci i traženi rezultat;
3) određuje se slijed radnji izvođača, koji osigurava prijelaz s početnih podataka na rezultat;
4) slijed radnji se bilježi pomoću naredbi uključenih u sustav naredbi izvođača.
Možemo reći da je algoritam model aktivnosti izvršitelja algoritama.
2.1.3. Svojstva algoritma
Ne može se svaka uputa, slijed uputa ili akcijski plan smatrati algoritmom. Svaki algoritam nužno ima sljedeća svojstva: diskretnost, razumljivost, određenost, učinkovitost i masovnost.
Svojstvo diskretnosti znači da je način rješavanja problema podijeljen u zasebne korake (radnje). Svaka radnja odgovara receptu (naredbi). Tek nakon što izvrši jednu naredbu, izvršitelj može prijeći na sljedeću naredbu.
Svojstvo razumljivosti znači da se algoritam sastoji samo od naredbi koje su uključene u sustav naredbi izvršitelja, odnosno od takvih naredbi koje izvršitelj može uočiti i prema kojima može izvršiti tražene radnje.
Svojstvo izvjesnosti znači da u algoritmu nema naredbi čije značenje izvršitelj može protumačiti dvosmisleno; neprihvatljive su situacije kada nakon izvršenja sljedeće naredbe izvršitelju nije jasno koju naredbu sljedeće izvršiti. Zbog toga je rezultat algoritma jedinstveno određen skupom početnih podataka: ako se algoritam primjenjuje nekoliko puta na isti skup početnih podataka, tada je izlaz uvijek isti rezultat.
Svojstvo izvedbe 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 dati mogućnost njegove primjene za rješavanje bilo kojeg problema iz određene klase problema. Na primjer, algoritam za pronalaženje korijena kvadratne jednadžbe trebao bi biti primjenjiv na bilo koju kvadratnu jednadžbu, 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 znanstvenika Eratostena (III. st. pr. Kr.) koji ju je predložio.
Da biste pronašli sve proste brojeve koji nisu veći od zadanog broja n, slijedeći Eratostenovu metodu, trebate izvesti sljedeće korake:
1) napiši redom sve prirodne brojeve od 2 do n (2, 3, 4, ..., n);
2) zatvoriti u okvir 2 - prvi prosti broj;
3) izbrisati s popisa sve brojeve djeljive zadnjim pronađenim prostim brojem;
4) pronađite prvi neoznačeni broj (označeni brojevi su precrtani brojevi ili brojevi zatvoreni u okvir) i zatvorite ga u okvir - to će biti sljedeći prost broj;
5) ponovite korake 3 i 4 dok ne bude neoznačenih brojeva.
Vizualniji prikaz metode za pronalaženje prostih brojeva možete dobiti uz pomoć animacije "Eratostenovo sito" (180279) smještene u Jedinstvenoj zbirci 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 naredbu izvođač interpretira i izvršava nedvosmisleno; postoje upute o redoslijedu izvršavanja naredbi;
djelotvornost- nakon određenog broja koraka postiže se rezultat;
masovni karakter- slijed radnji je primjenjiv za bilo koji prirodni n.
Razmatrana svojstva algoritma omogućuju precizniju definiciju algoritma.
Algoritam je opis niza radnji namijenjenih određenom izvođaču, koji vodi od početnih podataka do traženog rezultata, koji ima svojstva diskretnosti, razumljivosti, određenosti, djelotvornosti i masovnosti.
2.1.4. Sposobnost automatizacije ljudskih aktivnosti
Razvoj algoritma obično je dugotrajan zadatak koji od osobe zahtijeva duboko znanje, domišljatost i dugotrajnost.
Rješenje problema prema gotovom algoritmu zahtijeva od izvođača samo strogo pridržavanje zadanih uputa.
Primjer 9. Iz hrpe koja sadrži bilo koji, više od tri, broj bilo kojeg predmeta, dva igrača naizmjence uzimaju jedan ili dva predmeta. Pobjednik je onaj koji svojim sljedećim potezom može pokupiti sve preostale predmete.
Razmotrimo algoritam prema kojemu će prvi igrač sigurno sebi osigurati pobjedu.
1. Ako je broj predmeta u hrpi višestruki od 3, onda prepustite potez protivniku, inače započnite igru uzimajući 1 ili 2 predmeta tako da broj predmeta bude višekratnik 3.
2. Svaki put, sljedećim potezom, dopunite broj predmeta koje je protivnik uzeo na 3 (broj preostalih predmeta mora biti višekratnik 3).
Izvođač možda ne ulazi u značenje onoga što radi, i ne argumentira zašto radi to, a ne drugačije, odnosno može djelovati formalno. Izvođačeva sposobnost formalnog djelovanja daje sposobnost automatizacije ljudskih aktivnosti. Za ovo:
1) proces rješavanja problema prikazan je u obliku niza najjednostavnijih operacija;
2) stvoren je stroj (automatski uređaj) koji je sposoban izvoditi te operacije u slijedu navedenom u algoritmu;
3) osoba je oslobođena rutinskih aktivnosti, izvršenje algoritma povjereno je automatskom uređaju.
NAJVAŽNIJA STVAR
Izvršitelj- neki predmet (čovjek, životinja, tehničko sredstvo) sposoban izvršiti određeni skup naredbi.
Formalni izvršitelj uvijek izvodi istu naredbu na isti način. Za svakog formalnog izvođača možete navesti: raspon zadataka koje treba riješiti, okruženje, sustav zapovijedanja i način rada.
Algoritam- opis slijeda radnji namijenjenih određenom izvođaču, koji vodi od početnih podataka do traženog rezultata, koji ima svojstva diskretnosti, razumljivosti, određenosti, djelotvornosti i masovnosti.
Izvođačeva sposobnost glume formalno pruža mogućnost automatizacije ljudskih aktivnosti.
Pitanja i zadaci
1. Pročitajte materijale prezentacije za odlomak sadržan u elektroničkom prilogu udžbenika. Dopunjuje li prezentacija informacije u tekstu odlomka? Koje slajdove možete dodati svojoj prezentaciji?
2. Što se zove algoritam?
3. Pronađite sinonime za riječ "recept".
4. Navedite primjere algoritama koje učite u školi.
5. Tko može biti izvršitelj algoritma?
6. Navedite primjer formalnog izvođača. Navedite primjer kada osoba djeluje kao formalni izvršitelj.
7. Što određuje raspon zadataka izvršitelja "računala"?
8. Razmotrite program za obradu teksta na vašem računalu kao izvršitelja. Opišite niz zadataka koje rješava ovaj izvođač i njegovo okruženje.
9. Što je naredba, sustav naredbi izvršitelja?
10. Koje bi naredbe trebao imati robot koji obavlja funkcije:
a) blagajnik u trgovini;
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 izvođenja algoritma?
14. Niz brojeva se gradi prema sljedećem algoritmu: prva dva broja niza uzimaju se jednakima 1; svaki sljedeći broj u nizu uzima se jednak zbroju dva prethodna broja. Zapišite prvih 10 članova ovog niza. Saznajte kako se zove ovaj niz.
15. Neki algoritam dobiva novi niz iz jednog niza simbola na sljedeći način. Prvo se ispisuje izvorni 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 izvornom lancu. Ako je u izvornom lancu slovo "I" na posljednjem mjestu, tada je slovo "A" napisano kao sljedeće slovo. Rezultirajući lanac rezultat je algoritma. Na primjer, ako je izvorni niz znakova bio "DOM", tada će rezultat algoritma biti niz "DOMMODN". Zadan niz znakova "COM". Koliko će slova "O" biti u lancu znakova, što će se pokazati ako algoritam primijenite na ovaj lanac, a zatim ponovno 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. Što ć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) dobivanje od broja 3 broja 16;
b) dobivanje od broja 1 broja 25.
19. Sustav naredbi konstruktora izvršitelja sastoji se od dvije naredbe kojima se dodjeljuju brojevi:
1 - dodijeliti 2
2 - podijeliti sa 2
Prema prvom od njih broju s desne strane dodjeljuje se 2, a prema drugom broj je djeljiv s 2. Kako će se broj 8 pretvoriti ako izvršitelj izvrši algoritam 22212? Izradite algoritam u sustavu naredbi ovog izvršitelja, prema kojem će se broj 1 pretvoriti u broj 16 (algoritam ne smije sadržavati više od 5 naredbi).
20. U kojoj bi ćeliji trebao biti izvršitelj Robot (primjer 7) da bi se vratio u nju nakon izvršenja algoritma 3241?
Besplatni softver:
Sustav Kumir - Skup obrazovnih svjetova (preuzmite arhivu programa sa stranice) ili posjetite stranicu Kumir ((http://www.niisi.ru/kumir/)
Riječ "algoritam" dolazi od imena arapskog matematičara al-Khwarizmija iz 9. stoljeća, koji je formulirao pravila za izvođenje aritmetičkih operacija.
Algoritam- točna i razumljiva uputa izvođaču da izvrši konačni slijed naredbi koji vodi od početnih podataka do početnog rezultata.
Primjeri: dnevna rutina, postupak kuhanja, upute itd.)
Izvršitelj algoritma Je onaj koji izvršava algoritam (čovjek, životinja, stroj, računalo).
Sustav zapovijedi izvršitelja- to je cijeli skup naredbi koje izvođač zna izvesti (razumije). Algoritam se može izgraditi samo od naredbi uključenih u sustav naredbi izvršitelja.
Na primjer, izvođač Robot može izvršavati naredbe naprijed, natrag, lijevo, desno, preslikati. Kreće se oko staničnog polja, omeđenog zidom i koji sadrži zidove. Robot ne može proći kroz zid.
Svojstva algoritma:
1.Učinkovitost (ud)- mogućnost dobivanja rezultata iz početnih podataka u konačnom broju koraka. (Na primjer, kada se izvodi algoritam zbrajanja, 2 broja bi trebala dobiti zbroj).
2.Masovni karakter- mogućnost primjene algoritma na veliki broj različitih ulaznih podataka. (Na primjer, možete dodati bilo koja 2 broja, poznavajući algoritam zbrajanja.)
3.Determinizam(sigurnost, točnost) - svaki tim mora nedvosmisleno definirati radnju izvođača.
4.Shvatljivost- naredba mora biti napisana na jeziku razumljivom računalu.
5.Diskretnost- dijeljenje algoritma u zasebne naredbe.
Metode snimanja algoritma:
1) Na prirodnom jeziku - snimanje u obliku zasebnih naredbi na jeziku razumljivom osobi.
2) Grafički - na jeziku blok dijagrama, koristeći geometrijske oblike (oval, pravokutnik, paralelogram, romb).
3) U algoritamskom jeziku - jezik za pisanje algoritama za nastavu programiranja. Ekipe su snimljene 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 mogu se razlikovati skupine koraka koje se razlikuju po svojoj unutarnjoj strukturi – algoritamske konstrukcije.
Osnovne algoritamske konstrukcije su linearni slijed 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čunala:
- Uključite napajanje računala (pritisnite gumb na štitniku od prenapona).
- Uključite monitor, pisač.
- Pritisnite gumb za napajanje na jedinici sustava.
- Pričekajte dok se operativni sustav ne učita i pojavi se radna površina.
- Baci se 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, ovisno o istinitosti uvjeta, izvršava se jedan ili drugi slijed naredbi (serija).
Uvjet je izjava koja može biti istinita ili lažna. U uvjetu se dva broja, dva niza, dvije varijable ili izrazi niza međusobno uspoređuju pomoću operacija usporedbe (>,<, =, >=, <=).
U algoritamskim strukturama ciklus uključuje niz naredbi koje se izvršavaju više puta. Ovaj slijed 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;
- uvjetne 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 analizirat ćemo neke od teorijskih koncepata koji formaliziraju pojam programiranja. Ujedno ćemo preciznije formulirati glavni zadatak vašeg treninga.
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 Snimka zaslona igrališta na code.org
Nadam se da ćeš uspjeti. Sada ćemo, koristeći ovaj primjer, opisati nekoliko osnovnih pojmova:
- izvršitelj;
- sustav izvršnih naredbi;
- algoritam.
U igrački kontroliramo crvenu pticu. Zadatak svake faze: dovesti pticu do svinje. Ptica može izvršavati određene naredbe, na primjer: krenuti naprijed, skrenuti lijevo, skrenuti desno itd.
Osoba, stroj ili uređaj koji može izvršiti određene naredbe naziva se izvršitelj. U ovoj igrački, očito, izvođač je ptica. Zove se skup naredbi koje izvođač razumije i zna izvesti sustav zapovijedi izvršitelja.
Slijed naredbi koje izvršitelj mora izvršiti da bi riješio problem naziva se algoritam.
Potrebno je usredotočiti se na nekoliko točaka.
Izvođač može izvršiti samo one naredbe koje su uključene u njegov sustav naredbi.
To znači, na primjer, da ne možete pisati izvođaču ptica: "Idi na svinju!" Točnije, možete zapisati, ali ništa se neće dogoditi, tk. izvršitelj takvih naredbi ne zna.
Možete napisati postojeće naredbe bilo kojim redoslijedom koji smatrate ispravnim. Vaš zadatak kao programera je podijeliti veliki složeni zadatak u male zasebne korake, od kojih će svaki biti jasan izvršitelju. Zavadi pa vladaj opet radi.
Izvođač radi točno ono što mu algoritam nalaže.
Izvođač ptica je vrlo povjerljiv. Ne dovodi u pitanje ono što napišete u programu. Ako, na primjer, zaboravite rasklopiti pticu, ona će se zabiti u zid. Stoga se o svemu morate pobrinuti sami.
Vaši budući programi često neće raditi onako kako ste namjeravali. Greške se događaju 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, od ilustrativnog primjera, prijeđimo na računalne stvarnosti. Mi pišemo programe za računalo, što znači da je računalo u našem slučaju izvršitelj. Sustav naredbi - standardne funkcije i konstrukcije jezika C.
Koji je glavni zadatak vašeg podučavanja osnova programiranja? Ovladajte vještinom algoritamskog razmišljanja. Odnosno, naučite kako zapisati rješenje raznih problema u obliku algoritma za određenog izvođača (u našem slučaju, računalo).
Dakle, da rezimiramo:
Kompjuterski program- algoritam za rješavanje problema, napisan u programskom jeziku.
Algoritam - točan opis redoslijeda radnji koje mora izvršiti izvođač kako bi riješio problem.
Izvršitelj - osoba ili neki uređaj koji može razumjeti i izvršiti određeni skup naredbi.
Koncept algoritma. Izvršitelji algoritama. Svojstva algoritma
Koncept algoritma jednako je temeljan 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 raznim područjima znanosti, tehnologije i svakodnevnog života.
Algoritam je razumljiv i precizan slijed radnji koji opisuje proces transformacije objekta iz početnog stanja u konačno stanje.
Algoritam je precizan opis niza radnji usmjerenih na rješavanje zadanog problema, namijenjen određenom izvođaču.
Izvođač algoritam može biti ili osoba (recepti, razne upute, algoritmi za matematičke izračune) ili tehnički uređaj. Razni strojevi (računala, industrijski roboti, moderni kućanski aparati) su formalni izvođači algoritmi. Formalni izvršitelj nije dužan razumjeti bit problema koji se rješava, ali je potrebno točno izvršenje slijeda 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 .
Za izradu algoritma (programa) morate znati:
kompletan skup početnih podataka problema (početno stanje objekta);
svrha izrade algoritma (konačno stanje objekta);
sustav naredbi izvršitelja (odnosno skup naredbi koje izvršitelj razumije i može izvršiti).
Rezultirajući algoritam (program) mora imati sljedeći skup svojstava:
diskretnost (algoritam je podijeljen u zasebne korake - naredbe);
jednoznačnost (svaka naredba određuje jedinu moguću radnju izvođača);
razumljivost (sve naredbe algoritma uključene su u sustav naredbi izvršitelja);
učinkovitost (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, upute itd. Za algoritme snimanja namijenjene 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 sustav notacije:
|
Oznaka |
Opis |
Bilješke (uredi) |
|
Početak i kraj algoritma | ||
|
|
Unos i izlaz podataka. |
Izlaz podataka se ponekad naziva drugačije:
|
|
|
Akcijski |
U računskim algoritmima to je zadatak |
|
|
Vilica |
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 |
Navedimo primjer opisa algoritma za zbrajanje dviju veličina 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 dizajnirati i koristiti netipične algoritamske strukture, međutim, to nije potrebno. Bilo koji proizvoljno složen algoritam može se razviti na temelju tri tipične strukture: sukcesije, grananja i ponavljanja. U tom slučaju, strukture se mogu poredati jedna za drugom ili ugniježditi jedna u drugu.
Linearna struktura (slijedite)
Najjednostavnija algoritamska struktura je linearni. U njemu se sve operacije izvode jednom redom kojim su napisane.
Grananje
V potpuno grananje postoje dvije opcije za radnje izvršitelja, ovisno o vrijednosti logičkog izraza (uvjeta). Ako je uvjet istinit, tada će se izvršiti samo prva grana, inače ć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 konstruirati strukturu “ izbor"(Višestruko grananje), koji će birati ne između dvije, već iz većeg broja opcija za radnje izvršitelja, ovisno o nekoliko uvjeta. Bitno je da se izvrši samo jedna grana - u takvoj strukturi redoslijed uvjeta postaje važan: ako je zadovoljeno nekoliko uvjeta, tada će raditi samo jedan od njih - prvi odozgo.
Ciklus (ponavljanje)
Ciklusomogućuje vam organiziranje višestrukih ponavljanja istog slijeda naredbi- zove se tijelo ciklusa. U raznim vrstama algoritama za petlju, broj ponavljanja može ovisiti o vrijednosti logičkog izraza (uvjeta) ili može biti tvrdo kodiran u samoj strukturi. Postoje ciklusi: " prije», « dok», ciklusa s brojačem. U petljama "prije" i "while" logički izraz (uvjet) može prethoditi tijelu petlje ( petlja preduvjeta) ili završiti petlju ( petlja naknadnog uvjeta).
Ciklusi« prije"- ponavljanje tijela ciklusa dok se ne ispuni uvjet:
Ciklusi « dok"- ponavljanje tijela ciklusa dok je uvjet ispunjen(pravi):
Kontra petlje(s 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. Korištenje pomoćnih algoritama može značajno smanjiti veličinu algoritma i pojednostaviti njegov razvoj.
Metode razvoja složenih algoritama
Postoje dvije metode za razvoj složenih algoritama:
Metoda uzastopnog detaljiranja zadataka("Top-down") je da je izvorni 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 svedu na elementarne. Rješenja pojedinih podproblema tada se skupljaju u jedan algoritam za rješavanje izvornog problema. Metoda se široko koristi jer omogućuje nekoliko programera da istovremeno razviju opći algoritam koji rješava lokalne podzadatke. To je preduvjet za brzi razvoj softverskih proizvoda.
Način montaže("Bottom-up") je stvaranje 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 mnogim programski sustavi Već postoje slični skupovi modula, što uvelike pojednostavljuje i ubrzava stvaranje složenog algoritma.
Upravljački algoritmi i procesi
Kontrolirati - svrsishodna interakcija objekata, od kojih su neki kontrolirani, drugi su kontrolirani.
U najjednostavnijem slučaju, postoje dva takva objekta:
Sa stajališta informatike kontrolne radnje mogu se smatrati kontrolnim informacijama. Informacije se mogu prenijeti u obliku naredbi. Slijed naredbi za upravljanje objektom, koji vodi do unaprijed određenog cilja, naziva se kontrolni algoritam... Prema tome, kontrolni objekt se može nazvati izvršiteljem kontrolnog algoritma. U gornjem primjeru, kontrolni objekt radi "bez gledanja" što se događa s kontrolnim objektom ( kontrola otvorene petlje otvorena... Druga upravljačka shema može uzeti u obzir informacije o procesima koji se događaju 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 znanost tvrdi da se najrazličitiji procesi upravljanja u društvu, prirodi i tehnologiji odvijaju na sličan način, pokoravaju istim principima.
Na početak teme
MBOU "Srednja škola Glinnovskaya"
Novooskolsky okrug
Belgorod regija
Plan – nacrt lekcije
(9. razred)
“Algoritmi, koncepti algoritma, svojstva algoritma. Izvršitelji algoritma"
Pripremio:
Učite informatiku
Tarasova N.G.
2011
Tema: Pojam algoritama, svojstva algoritma. Izvršitelji algoritma, sustav naredbi izvršitelja. Metode za snimanje algoritama. Formalno izvođenje algoritama.
Vrsta lekcije: upoznavanje s novim gradivom.
Ciljevi:
- Promicati razvoj algoritamskog mišljenja;
- Dajte pojam algoritma, razgovarajte o svojstvima, dajte klasifikaciju algoritama;
- Uvesti oblik pisanja algoritama - blok dijagram.
Oprema: projektor, prezentacija.
Tijekom nastave
1 org. Trenutak
Pozdrav, slijetanje, prozivka.
2 Ažuriranje referentnog materijala
Dečki, recite mi, molim vas, kako razumijete riječ algoritam? Gdje se moramo nositi s ovim konceptom?
3 Prezentacija materijala
Porijeklo pojma "algoritam" povezuje se s matematikom. Povijest njegovog nastanka je sljedeća. U 9. stoljeću u Bagdadu je živio znanstvenik al (al) -Horezmi (puno ime - Muhammad bin Musa al-Khorezmi, tj. Muhamed sin Musa iz Horezma), matematičar, astronom, geograf. U jednom od svojih djela opisao je decimalni brojevni sustav i po prvi put formulirao pravila za izvođenje aritmetičkih operacija nad cijelim brojevima i običnim razlomcima. Arapski izvornik ove knjige je izgubljen, ali je ostao latinski prijevod iz 12. stoljeća prema kojemu se Zapadna Europa upoznala s decimalnim brojevnim sustavom i pravilima za izvođenje računskih operacija.
Al-Khwarizmi je nastojao učiniti razumljivim pravila koja je formulirao. To je bilo teško postići u 9. stoljeću, kada još nije bila razvijena matematička simbolika (znakovi operacija, zagrade, slovne oznake itd.). Ipak, uspijeva razviti jasan stil strogog verbalnog recepta koji čitatelju ne daje 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 se naziva Algoritam. S vremenom se zaboravilo da je Algorizmi (Algoritam) autor pravila, te su se ta pravila počela zvati algoritmi. Stoljećima su se razvijali algoritmi za rješavanje sve više i više klasa problema, ali sam pojam algoritma nije imao točnu matematičku definiciju.
Trenutno je pojam algoritma razjašnjen i napravljen u XX. stoljeću u okviru znanosti koja se zove teorija algoritama.
Algoritam - precizne i razumljive upute izvođaču da izvrši niz radnji usmjerenih na rješavanje zadatka.
Algoritam - jasno organizirana sekvencijalna radnja koja vodi do određenog rezultata.
Izvršitelj algoritma je neki apstraktan ili stvaransustav sposoban za obavljanje radnje propisane algoritmom (tehničkim, biološkim ili biotehničkim).
Tehnički izvršitelj- bankomat;
Biološki - osoba, živi organizam;
Biotehnika - umjetna inteligencija.
Svojstva algoritma
Diskretnost (razdvajanje, diskontinuitet) - algoritam treba napisati kao slijed koraka ili faza.
Shvatljivost izvršitelj algoritma mora znati kako izvršiti ovaj algoritam.
Sigurnost (determinizam) svako pravilo algoritma treba biti jasno, nedvosmisleno i ne ostavljati mjesta proizvoljnosti.
Zbog ovog svojstva, izvođenje algoritma je mehaničke prirode i ne zahtijeva dodatne upute.
Učinkovitost(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 kako bi se mogao primijeniti za rješavanje sličnih problema. U ovom slučaju, izvorni podaci se biraju iz nekih područja, koja se nazivaju područjem primjene algoritama.
Metode snimanja algoritama
Ako se svojstva sigurnosti i diskretnosti očuvaju s određenim stupnjem točnosti, t.j. 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, računalo itd. svaki izvođač ima svoj sustav zapovijedanja. Prilikom sastavljanja algoritma morate uzeti u obzir za kojeg je izvođača dizajniran. Izvođač može provesti 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.
Obrasci za snimanje algoritama:
Verbalno je opis uzastopnih faza obrade podataka. Algoritam je proizvoljan prikaz na prirodnom jeziku
Grafički - 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
Slijedite (linearni algoritam) petlje
Grananje
slijediti - naredbe se izvršavaju jedna za drugom redoslijedom kojim su zapisane u algoritmu. ((Primjer. Algoritam za otvaranje vrata stana: uzmite ključ, umetnite gaključanicu, okrenite potreban broj puta, uzmite ključ, otvorite vrata. zatvori vrata)
Grananje - podaci utječu na tijek algoritma, t.j. ovisno o stanjuizvode se određene radnje algoritma.(Primjer, algoritam "ulaska" u vaš stan: pozovite stan; ako je netko kod kuće, prič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 naredbi. (Primjer.(Pranje 10 tanjura: uzmi tanjur, operi, stavi u sušilicu, uzmitanjur, operite, stavite u sušilicu itd. dok ne ostanete bez tanjura.)
4 Primjena stečenog znanja
Zadatak izvršiti naredbe algoritma s a = 1, b = 2, c = 3
