B6. Koncepcia algoritmu

Kľúčové slová:

• algoritmu
• vlastnosti algoritmu
  • diskrétnosť
  • jasnosť
  • istota
  • efektívnosť
  • masový charakter
• exekútor

• vlastnosti interpreta
  • rozsah úloh, ktoré treba vyriešiť
  • streda
  • prevádzkový režim
  • príkazový systém
• formálne vykonanie algoritmu

3.1.1. Koncepcia algoritmu

Každý človek v bežnom živote, pri štúdiu alebo v práci rieši obrovské množstvo problémov rôznej zložitosti. Komplexné problémy vyžadujú veľa premýšľania, aby sa našli riešenia; Jednoduché a známe úlohy človek rieši bez rozmýšľania, automaticky. Vo väčšine prípadov možno riešenie každého problému rozdeliť do jednoduchých etáp (krokov). Pre mnohé z týchto úloh (inštalácia softvéru, zostavenie skrine, vytvorenie webovej stránky, obsluha technického zariadenia, nákup letenky cez internet atď.) už boli vyvinuté a ponúkané podrobné pokyny, postupné ktorých realizácia môže viesť k požadovanému výsledku.

Príklad 1. Problém „Nájdite aritmetický priemer dvoch čísel“ sa rieši v troch krokoch:

• myslieť na dve čísla;
• pridajte dve čísla na mysli;
• výslednú sumu vydeľte 2.

Príklad 2. Úloha „Vložiť peniaze na váš telefónny účet“ je rozdelená do nasledujúcich krokov:

• prejdite na platobný terminál;
• vyberte telekomunikačného operátora;
• Zadajte telefónne číslo;
• skontrolujte správnosť zadaného čísla;
• vložiť bankovku do akceptora bankoviek;
• počkajte na správu o pripísaní peňazí na váš účet;
• dostať šek.

Príklad 3. Fázy riešenia problému „Nakreslite vtipného ježka“ sú znázornené graficky:

Hľadanie aritmetického priemeru, vkladanie peňazí na telefónny účet a kreslenie ježka sú na prvý pohľad úplne odlišné procesy. Majú však spoločnú vlastnosť: každý z týchto procesov je opísaný postupnosťou krátkych pokynov, ktorých prísne dodržiavanie vám umožňuje dosiahnuť požadovaný výsledok. Postupnosti inštrukcií uvedené v príkladoch 1-3 sú algoritmy na riešenie príslušných problémov. Vykonávateľom týchto algoritmov je osoba.

Algoritmus môže byť popisom určitej postupnosti výpočtov (príklad 1) alebo krokov nematematického charakteru (príklady 2-3). V každom prípade však pred jeho vývojom musia byť jasne definované počiatočné podmienky (počiatočné údaje) a to, čo sa má získať (výsledok). Dá sa povedať, že algoritmus je popis postupnosti krokov pri riešení problému, ktoré vedú od počiatočných údajov k požadovanému výsledku.

Vo všeobecnosti môže byť operačný diagram algoritmu znázornený nasledovne (obr. 3.1):

Ryža. 3.1.
Všeobecná schéma algoritmu

Algoritmy sú pravidlá sčítania, odčítania, násobenia a delenia čísel, gramatické pravidlá, pravidlá geometrických konštrukcií atď., ktoré sa učili v škole.

Animácie „Práca s algoritmom“, „Najväčší spoločný deliteľ“, „Najmenší spoločný násobok“ (http://school-collection.edu.ru/) vám pomôžu zapamätať si niektoré algoritmy študované na hodinách ruského jazyka a matematiky.

Príklad 4. Niektorý algoritmus vedie k tomu, že z jedného reťazca znakov sa získa nový reťazec takto:

1. Vypočíta sa dĺžka (v znakoch) zdrojového reťazca znakov.
2. Ak je dĺžka pôvodnej retiazky nepárna, potom sa k pôvodnej retiazke vpravo pridá číslo 1, inak sa retiazka nemení.
3. Symboly sa zamieňajú v pároch (prvý s druhým, tretí so štvrtým, piaty so šiestym atď.).
4. Číslo 2 sa pridá napravo od výsledného reťazca.

Výsledný reťazec je výsledkom algoritmu.

Takže, ak bol počiatočný reťazec A#B, potom výsledkom algoritmu bude reťazec #A1B2, a ak počiatočný reťazec bol ABC@, potom výsledkom algoritmu bude reťazec BA@B2.

3.1.2. Vykonávateľ algoritmu

Každý algoritmus je navrhnutý pre konkrétneho interpreta.

Existujú formálni a neformálni umelci. Formálny umelec vždy vykonáva rovnaký príkaz rovnakým spôsobom. Neformálny vykonávateľ môže vykonať príkaz rôznymi spôsobmi.

Pozrime sa podrobnejšie na súbor formálnych umelcov. Formalisti sú mimoriadne rôznorodí, ale pre každého z nich možno špecifikovať tieto charakteristiky: rozsah úloh, ktoré sa majú riešiť (účel), prostredie, systém velenia a spôsob činnosti.

Rozsah úloh, ktoré treba vyriešiť. Každý účinkujúci je vytvorený, aby riešil určitý okruh problémov – konštruovanie reťazcov symbolov, vykonávanie výpočtov, konštruovanie kresieb v rovine atď.

Prostredie umelca. Oblasť, prostredie, podmienky, v ktorých účinkujúci pôsobí, sa zvyčajne nazývajú prostredím daného interpreta. Zdrojové dáta a výsledky každého algoritmu vždy patria do prostredia interpreta, pre ktorého je algoritmus určený.

Systém príkazov vykonávateľa. Inštrukcia pre umelca na vykonanie samostatnej dokončenej akcie sa nazýva príkaz. Súbor všetkých príkazov, ktoré môže vykonať niektorý vykonávač, tvorí systém príkazov pre tohto vykonávateľa (SKI). Algoritmus je zostavený s prihliadnutím na schopnosti konkrétneho interpreta, inými slovami, v systéme príkazov interpreta, ktorý ho vykoná.

Prevádzkové režimy vykonávateľa. Pre väčšinu interpretov sú k dispozícii režimy priameho ovládania a ovládania programu. V prvom prípade účinkujúci čaká na príkazy od osoby a okamžite vykoná každý prijatý príkaz. V druhom prípade dostane interpret najprv kompletnú sekvenciu príkazov (program) a potom všetky tieto príkazy vykoná automaticky. Množstvo interpretov pracuje len v jednom z menovaných režimov.

Pozrime sa na príklady interpretov.

Príklad 5. Performer Korytnačka sa pohybuje na obrazovke počítača a zanecháva za sebou stopu vo forme čiary. Príkazový systém korytnačky pozostáva z dvoch príkazov:

Dopredu n (kde n je celé číslo) – spôsobí, že sa korytnačka pohne o n krokov v smere pohybu – v smere, ktorým smeruje jej hlava a telo;

Pravé m (kde m je celé číslo) – spôsobí zmenu smeru pohybu korytnačky o m stupňov v smere hodinových ručičiek.

Opakovanie záznamu k [<Команда1> <Команда2> ... <Командаn>] znamená, že postupnosť príkazov v zátvorkách sa bude opakovať k-krát.

Zamyslite sa nad tým, aké číslo sa objaví na obrazovke, keď korytnačka dokončí nasledujúci algoritmus.

Opakujte 12 [vpravo 4 5 vpred 20 vpravo 45]

Príklad 6. Systém vykonávacích príkazov Počítač pozostáva z dvoch príkazov, ktoré majú priradené čísla:

1 - odčítať 1
2 - vynásobte 3

Prvý z nich znižuje číslo o 1, druhý zvyšuje číslo 3-krát. Pri písaní algoritmov sa kvôli stručnosti uvádzajú iba čísla príkazov. Napríklad algoritmus 21212 znamená nasledujúcu postupnosť príkazov:

vynásobiť 3
odčítať 1
vynásobiť 3
odčítať 1
vynásobiť 3

Pomocou tohto algoritmu sa číslo 1 prevedie na 15: ((1-3-1)-3-1)-3 = 15.

Príklad 7. Performer Robot pôsobí na kockovanom poli, medzi susednými bunkami môžu byť steny. Robot sa pohybuje pozdĺž buniek poľa a môže vykonávať nasledujúce príkazy, ktorým sú priradené čísla:

1 - hore
2 - dole
3 - Správne
4 - vľavo

Pri vykonávaní každého takéhoto príkazu sa robot presunie do susednej bunky v naznačenom smere. Ak je v tomto smere medzi bunkami stena, robot je zničený. Čo sa stane s robotom, ak vykoná sekvenciu príkazov 32323 (tu čísla označujú čísla príkazov) a začne sa pohybovať z bunky A? Akú postupnosť príkazov by mal robot vykonať, aby sa presunul z bunky A do bunky B bez toho, aby sa pri náraze na steny zrútil?

Pri vývoji algoritmu:

1. identifikujú sa objekty vyskytujúce sa v probléme, stanovia sa vlastnosti objektov, vzťahy medzi objektmi a možné akcie s objektmi;
2. sú určené počiatočné údaje a požadovaný výsledok;
3. určuje sa postupnosť akcií výkonného umelca, čím sa zabezpečí prechod od počiatočných údajov k výsledku;
4. postupnosť akcií sa zaznamenáva pomocou príkazov zahrnutých v príkazovom systéme vykonávateľa.

Dá sa povedať, že algoritmus je modelom činnosti vykonávateľa algoritmu.

3.1.3. Vlastnosti algoritmu

Nie každý pokyn, postupnosť pokynov alebo akčný plán možno považovať za algoritmus. Každý algoritmus má nevyhnutne tieto vlastnosti: diskrétnosť, zrozumiteľnosť, určitosť, účinnosť a masový charakter.

Vlastnosť diskrétnosti znamená, že cesta k riešeniu problému je rozdelená do samostatných krokov (akcií). Každá akcia má zodpovedajúci pokyn (príkaz). Až po vykonaní jedného príkazu môže exekútor začať vykonávať ďalší príkaz.

Vlastnosť zrozumiteľnosti znamená, že algoritmus pozostáva len z príkazov zaradených do systému príkazov interpreta, teda z takých príkazov, ktoré interpret dokáže vnímať a podľa ktorých môže vykonávať požadované akcie.

Vlastnosť istoty znamená, že algoritmus neobsahuje príkazy, ktorých význam môže interpret nejednoznačne interpretovať; Situácie sú neprijateľné, keď po vykonaní nasledujúceho príkazu nie je pracovníkovi jasné, ktorý príkaz má vykonať v ďalšom kroku.

Vlastnosť účinnosti znamená, že algoritmus musí byť schopný získať výsledok po konečnom, možno veľmi veľkom počte krokov. V tomto prípade sa za výsledok považuje nielen odpoveď určená vyhlásením problému, ale aj záver o nemožnosti pokračovať v riešení tohto problému z akéhokoľvek dôvodu.

Vlastnosť hromadnej výroby znamená, že algoritmus musí poskytnúť možnosť jeho aplikácie na riešenie akéhokoľvek problému z určitej triedy problémov. Napríklad algoritmus na nájdenie koreňov kvadratickej rovnice by mal byť použiteľný na akúkoľvek kvadratickú rovnicu, algoritmus na prekročenie ulice by mal byť použiteľný kdekoľvek na ulici, algoritmus na prípravu lieku by mal byť použiteľný na prípravu akéhokoľvek jeho množstva, atď.

Príklad 8. Uvažujme jednu z metód, ako nájsť všetky prvočísla nepresahujúce n. Táto metóda sa nazýva „Eratosthenovo sito“, pomenované po starogréckom vedcovi Eratosthenesovi, ktorý ju navrhol.

Ak chcete nájsť všetky prvočísla nie väčšie ako dané číslo n, podľa metódy Eratosthenes musíte vykonať nasledujúce kroky:

1. zapíšte si všetky celé čísla od 2 do n za sebou (2, 3, 4, ..., n);
2. snímka 2 - prvé prvočíslo;
3. vyčiarknite zo zoznamu všetky čísla deliteľné posledným nájdeným prvočíslom;
4. nájdite prvé neoznačené číslo (označené čísla sú prečiarknuté čísla alebo čísla v rámčeku) a uzatvorte ho do rámčeka – bude to ďalšie prvočíslo;
5. opakujte kroky 3 a 4, kým nezostanú žiadne neoznačené čísla.

Vizuálnejšiu predstavu o spôsobe hľadania prvočísel môžete získať pomocou animácie „Sievo Eratosthenes“ (http://school-collection.edu.ru/).

Uvažovaná postupnosť akcií je algoritmus, pretože spĺňa nasledujúce vlastnosti:

• diskrétnosť - proces hľadania prvočísel je rozdelený do krokov;
• zrozumiteľnosť - každý príkaz je zrozumiteľný pre žiaka 9. ročníka, ktorý vykonáva tento algoritmus;
• istota - každý príkaz interpret interpretuje a vykonáva jednoznačne; existujú pokyny o poradí vykonávania príkazov;
• účinnosť - po určitom počte krokov sa dosiahne výsledok;
• hromadný charakter - postupnosť úkonov je použiteľná pre akúkoľvek prirodzenú n.

Uvažované vlastnosti algoritmu nám umožňujú presnejšie definovať algoritmus.

3.1.4. Možnosť automatizácie ľudských činností

Vývoj algoritmu je zvyčajne náročná úloha, ktorá vyžaduje od človeka hlboké znalosti, vynaliezavosť a veľa času.

Riešenie problému pomocou hotového algoritmu vyžaduje od interpreta iba striktné dodržiavanie daných pokynov.

Príklad 9. Z kôpky obsahujúcej ľubovoľný počet predmetov väčší ako tri sa dvaja hráči striedavo vezmú jeden alebo dva predmety. Víťazom je ten, kto môže pri svojom ďalšom ťahu vyzdvihnúť všetky zostávajúce predmety.

Zoberme si algoritmus, podľa ktorého prvý hráč určite zabezpečí výhru.

1. Ak je počet predmetov v kôpke násobkom 3, ustúpte súperovi, inak začnite hru.
2. Pri ďalšom ťahu vždy pripočítajte počet predmetov, ktoré vzal váš súper, k 3 (počet zostávajúcich predmetov musí byť násobkom 3).

Výkonný umelec sa nemusí ponoriť do zmyslu toho, čo robí, a neuvádza, prečo koná tak a nie inak, to znamená, že môže konať formálne. Schopnosť interpreta konať formálne poskytuje možnosť automatizácie ľudskej činnosti. Pre to:

1. proces riešenia problému je prezentovaný ako postupnosť jednoduchých operácií;
2. je vytvorený stroj (automatické zariadenie) schopný vykonávať tieto operácie v poradí špecifikovanom v algoritme;
3. osoba je oslobodená od rutinných činností, vykonávanie algoritmu je zverené automatickému zariadeniu.

Najdôležitejšie

Vykonávateľ je objekt (osoba, zviera, technické zariadenie) schopný vykonávať určitý súbor príkazov. Formálny umelec vždy vykonáva rovnaký príkaz rovnakým spôsobom. Pre každého formálneho interpreta môžete špecifikovať: rozsah úloh, ktoré sa majú vyriešiť, prostredie, príkazový systém a prevádzkový režim.

Algoritmus je popis postupnosti akcií určených pre konkrétneho interpreta, ktorý vedie od počiatočných údajov k požadovanému výsledku, ktorý má vlastnosti diskrétnosti, zrozumiteľnosti, istoty, účinnosti a masovosti.

Schopnosť interpreta konať formálne poskytuje možnosť automatizácie ľudskej činnosti.

Otázky a úlohy

1. Ako sa volá algoritmus?
2. Nájdite synonymá pre slovo „predpis“.
3. Uveďte príklady algoritmov, ktoré ste študovali v škole.
4. Kto môže byť vykonávateľom algoritmu?
5. Uveďte príklad formálneho umelca. Uveďte príklad, keď osoba vystupuje ako formálny umelec.
6. Aké príkazy by mal robot vykonávať funkcie: a) pokladníka v obchode; b) školník; c) ochranka?
7. Čo určuje rozsah úloh vykonávaných „počítačovým“ interpretom?
8. Zvážte textový procesor vo svojom počítači ako vykonávateľa. Popíšte rozsah úloh, ktoré rieši tento interpret a jeho prostredie.
9. Čo je tím, systém vykonávacích príkazov?
10. Uveďte hlavné vlastnosti algoritmu.
11. K čomu môže viesť absencia akejkoľvek vlastnosti v algoritme? Uveďte príklady.
12. Prečo je dôležité byť schopný formálne vykonať algoritmus?
13. Postupnosť čísel je skonštruovaná podľa nasledujúceho algoritmu: prvé dve čísla postupnosti sa rovnajú 1; Každé ďalšie číslo v poradí sa považuje za rovné súčtu dvoch predchádzajúcich čísel. Zapíšte si prvých 10 členov tejto postupnosti.
14. Niektoré algoritmy získajú nový reťazec z jedného reťazca znakov nasledovne. Najprv sa napíše pôvodný reťazec znakov, za ním sa napíše pôvodný reťazec znakov v opačnom poradí, potom sa napíše písmeno, ktoré nasleduje v ruskej abecede za písmenom, ktoré bolo v pôvodnom reťazci na poslednom mieste. Ak je posledné miesto v pôvodnom reťazci písmeno Z, potom písmeno A je zapísané ako ďalšie písmeno Výsledný reťazec je výsledkom algoritmu. Napríklad, ak pôvodný reťazec znakov bol DOM, potom výsledkom algoritmu bude reťazec DOMMODN. Daný reťazec znakov COM. Koľko písmen O bude v reťazci symbolov, ktoré sa získajú, ak použijete algoritmus na tento reťazec a potom znova použijete algoritmus na výsledok jeho práce?
15. Nájdite animáciu krokov Eratosthenovho algoritmu na internete. Použite Eratosthenov algoritmus na nájdenie všetkých prvočísel nepresahujúcich 50.
16. Aký bude výsledok vykonania korytnačky (pozri príklad 5) algoritmu?
    Opakujte 8 [vpravo 45 dopredu 45]
17. Napíšte si algoritmus pre spúšťač kalkulačky (príklad 6), ktorý nebude obsahovať viac ako 5 príkazov:
    a) prijímanie od čísla 3 číslo 16;
    b) prijímanie od čísla 1 číslo 25.
18. Systém príkazov vykonávateľa Konštruktor pozostáva z dvoch príkazov, ktoré majú priradené čísla:
    1 - priradiť 2
    2 - deliť 2

    Podľa prvého z nich sa k číslu vpravo pripočíta 2, podľa druhého sa číslo vydelí 2. Ako sa prevedie číslo 8, ak interpret vykoná algoritmus 22212? V príkazovom systéme tohto vykonávateľa vytvorte algoritmus, podľa ktorého sa číslo 1 prevedie na číslo 16 (algoritmus by nemal obsahovať viac ako 5 príkazov).

19. V ktorej bunke by sa mal nachádzať robotický robot (príklad 7), aby sa do nej mohol vrátiť po vykonaní algoritmu 3241?

MBOU "Stredná škola Glinnovskaja"

Novooskolský okres

Belgorodská oblasť

Plán - zhrnutie lekcie

(9. ročník)

„Algoritmy, koncepty algoritmov, vlastnosti algoritmov. Vykonávatelia algoritmu"

Pripravené:

Naučte sa informatiku

Tarasová N.G.

2011

Predmet: Pojem algoritmov, vlastnosti algoritmu. Vykonávatelia algoritmov, systém vykonávacích príkazov. Metódy na zaznamenávanie algoritmov. Formálne vykonávanie algoritmov.

Typ lekcie: zoznámenie sa s novým materiálom.

Ciele:

1. Podporovať rozvoj algoritmického myslenia;
2. Uveďte pojem algoritmu, hovorte o jeho vlastnostiach, uveďte klasifikáciu algoritmov;
3. Predstaviť formu záznamových algoritmov - vývojový diagram.

Vybavenie: projektor, prezentácia.

Počas vyučovania

1 org. Moment

Pozdrav, nástup, zavolanie.

2 Aktualizácia podporného materiálu

Chlapci, prosím, povedzte mi, ako rozumiete slovu algoritmus? Kde sa s týmto pojmom stretávame?

3 Prezentácia materiálu

Pôvod termínu „algoritmus“ súvisí s matematikou. História jeho vzniku je nasledovná. V 9. storočí žil v Bagdade vedec al(al)-Khorezmi (celým menom - Muhammad ben Musa al-Khorezmi, t.j. Muhammad syn Musu z Chorezmu), matematik, astronóm, geograf. V jednej zo svojich prác opísal desiatkovú číselnú sústavu a po prvý raz sformuloval pravidlá na vykonávanie aritmetických operácií s celými číslami a obyčajnými zlomkami. Arabský originál tejto knihy sa stratil, zostal však latinský preklad z 12. storočia, podľa ktorého sa západná Európa zoznámila so systémom desatinných čísel a pravidlami vykonávania aritmetických operácií.

Al-Khwarizmi sa snažil zabezpečiť, aby pravidlá, ktoré sformuloval, boli zrozumiteľné. Bolo to ťažké dosiahnuť v 9. storočí, keď ešte neboli vyvinuté matematické symboly (operačné znaky, zátvorky, písmenové symboly atď.). Dokáže si však vypracovať jasný štýl prísnych slovných pokynov, ktoré nedávali čitateľovi možnosť vyhnúť sa predpísaným či preskočiť akékoľvek úkony.

Pravidlá v knihách cm-Khorezmi v latinskom preklade začínali slovami „Algorizmi povedal“. V iných latinských prekladoch bol autor označovaný ako Algorithmus. Postupom času sa zabudlo, že autorom pravidiel je Algorizmi (Algorithmus) a tieto pravidlá sa začali nazývať algoritmy. Po mnoho storočí sa vyvíjali algoritmy na riešenie stále nových tried problémov, ale samotný koncept algoritmu nemal presnú matematickú definíciu.

V súčasnosti je pojem algoritmus objasnený a bol vytvorený v 20. storočí v rámci vedy nazývanej teória algoritmov.

Algoritmus - presné a zrozumiteľné pokyny výkonnému umelcovi na vykonanie sledu činností zameraných na vyriešenie úlohy.

Algoritmus - jasne organizovaná postupná činnosť vedúca ku konkrétnemu výsledku.

Vykonávateľ algoritmu je nejaký abstraktný alebo skutočnýsystém schopný vykonať činnosť predpísanú algoritmom (technickým, biologickým alebo biotechnickým).

Technický vedúci– bankomat;

Biologické - človek, živý organizmus;

Biotechnológia - umela inteligencia.

Vlastnosti algoritmov

Diskrétnosť (oddelenosť, diskontinuita) – algoritmus musí byť napísaný vo forme postupnosti krokov alebo etáp.

Zrozumiteľnosť vykonávateľ algoritmu musí vedieť, ako tento algoritmus vykonať.

Istota (determinizmus) každé pravidlo algoritmu musí byť jasné, jednoznačné a nenechávať priestor pre svojvôľu.

Vďaka tejto vlastnosti je vykonávanie algoritmu svojou povahou mechanické a nevyžaduje ďalšie pokyny.

Efektívnosť(konečnosť) Algoritmus musí viesť k riešeniu problému v konečnom počte krokov.

Hromadný charakter Algoritmus je vyvinutý vo všeobecnej forme, aby sa dal použiť na riešenie podobných problémov. V tomto prípade sa počiatočné údaje vyberajú z určitých oblastí, ktoré sa nazývajú oblasť použitia algoritmov.

Spôsoby písania algoritmov

Ak sú vlastnosti istoty a diskrétnosti zachované s určitou mierou presnosti, t.j. program môže preusporiadať kroky alebo obsahuje žiaduce, ale nie povinné kroky, potom to nie je algoritmus, alealgoritmický predpis.

Každý algoritmus je navrhnutý pre niečo konkrétneúčinkujúci. Môže to byť osoba, robot, počítač atď. Každý účinkujúci má svoj vlastný systém príkazov. Pri zostavovaní algoritmu je potrebné vziať do úvahy, pre ktorého interpreta je určený. Interpret môže vykonať algoritmus bez toho, aby sa ponoril do významu toho, čo robí, prečo to robí, a napriek tomu dosiahne požadovaný výsledok. V takýchto prípadoch sa hovorí, že algoritmus je vykonaný formálne.

Formuláre na zaznamenávanie algoritmov:

Verbálne je popis postupných fáz spracovania údajov. Algoritmus je ľubovoľná prezentácia v prirodzenom jazyku

Grafický - postupnosť vzájomne prepojených blokov, z ktorých každý zodpovedá vykonaniu jednej alebo viacerých akcií.

Takéto grafické znázornenie sa nazýva bloková schéma - orientovaný graf označujúci poradie vykonávania príkazov algoritmu.

Grafické formy záznamových algoritmov:

Základné algoritmické štruktúry

Nasledovanie (lineárny algoritmus) slučky

Vetvenie

Sledovanie – príkazy sa vykonávajú jeden po druhom v poradí, v akom sú zapísané v algoritme.((Príklad. Algoritmus na otváranie dverí do bytu: vyberte kľúč, vložte ho dokľúčovou dierkou, otočte požadovaný počet krát, vyberte kľúč, otvorte dvere. ZATVÁRAJTE DVERE)

Vetvenie - dáta ovplyvňujú priebeh algoritmu, t.j. v závislosti od stavuvykonajú sa určité akcie algoritmu.(Príklad, Algoritmus „dostať sa“ do vášho bytu: zavolajte do bytu; ak je niekto doma, počkajte, kým sa neotvoria dvere avstúpte do bytu, ak nikto nie je doma, získajte kľúč; ...)

Cyklus (opakovanie)- pri vykonávaní algoritmu určitýsúbor príkazov (Príklad.(Umývanie 10 tanierov: vezmite tanier, umyte ho, vložte do sušičky, vezmitetanier, umyte ho, vložte do sušičky atď., kým sa taniere neminú.)

4 Aplikácia získaných poznatkov

Úloha vykonávať príkazy algoritmu s a=1, b=2, c=3

Objekt, ktorý vykoná algoritmus, sa zvyčajne nazýva účinkujúci.

Exekútor- objekt, ktorý vykonáva algoritmus.

Úloha interpreta presne plniť pokyny algoritmu, niekedy bez premýšľania o výsledku a cieľoch, t.j. formálne. Ideálnymi interpretmi sú stroje, roboty, počítače...

Počítač je automatickým vykonávateľom algoritmov.

Algoritmus napísaný v počítačovom programovacom jazyku sa nazýva program.

Každý interpret je charakterizovaný životné prostredie(„biotop“) a príkazový systém.

Hlavné charakteristiky interpreta sú: prostredie, príkazový systém, elementárne akcie, poruchy.

streda(alebo prostredie) je „biotop“, súbor objektov, ktoré obklopujú účinkujúceho.

Každý vykonávateľ môže vykonávať príkazy len z určitého presne definovaného zoznamu – systému príkazov vykonávateľa. Volá sa množina všetkých príkazov, ktoré môže exekútor vykonať systém príkazov vykonávateľa(LYŽOVANIE). Pre každý príkaz musia byť špecifikované podmienky použiteľnosti (v ktorých stavoch prostredia môže byť príkaz vykonaný) a musia byť popísané výsledky vykonania príkazu.

Každému príkazu z príkazového systému interpreta je priradený špecifický elementárna akcia. Interpret môže byť reprezentovaný ako zariadenie s tlačidlovým ovládaním. Každé tlačidlo zodpovedá jednému príkazu pre účinkujúceho a stlačenie znamená vyvolanie tohto príkazu. Po zavolaní príkazu vykoná interpret elementárnu akciu zodpovedajúcu tomuto príkazu. Je dôležité poznamenať, že nás zaujíma výsledok, nie mechanizmus vykonania príkazu.

Neúspechy chyby vykonávateľa sa vyskytujú, keď je príkaz zavolaný v stave prostredia, ktorý je pre tento príkaz neprijateľný. Inými slovami, toto je prípad, keď pokus o vykonanie príkazu vedie k zlyhaniu.

Tréningoví vykonávatelia sú rôzne obrázky na obrazovke počítača, ktoré možno ovládať vydávaním príkazov. Používajú sa na učenie, ako skladať riadiace algoritmy.

Existuje mnoho rôznych vzdelávacích nástrojov určených pre hodiny informatiky. Majú rôzne, často vtipné názvy: Korytnačka, Robot, Kreslič, Klokan, Vysávač, Mravec, Cucaracha atď. Niektorí interpreti vytvárajú kresby na obrazovke, iní skladajú slová z kociek s písmenami, iní preťahujú predmety z jedného miesta na druhé. . Všetci títo interpreti sú riadení softvérom. Každý z nich je charakterizovaný určitým operačným prostredím, systémom ovládacích príkazov a prevádzkových režimov. S pomocou každého z týchto interpretov sa môžete naučiť vytvárať riadiace algoritmy.

Hlavné typy algoritmov (algoritmické štruktúry):

1. Lineárny algoritmus (nazývaný aj nasledujúci);

2. Cyklický algoritmus;

3. Algoritmus vetvenia;

Koncept algoritmu. Vykonávatelia algoritmov. Vlastnosti algoritmov

Pojem algoritmus je pre informatiku rovnako základný ako pojem informácie. Existuje mnoho rôznych definícií algoritmu, pretože tento pojem je dosť široký a používa sa v rôznych oblastiach vedy, techniky a každodenného života.

Algoritmus je jasná a presná postupnosť akcií, ktorá popisuje proces transformácie objektu z počiatočného stavu do konečného stavu.

Algoritmus je presný popis postupnosti akcií určených pre konkrétneho interpreta zameraných na riešenie daného problému.

Účinkujúci Algoritmus môže byť buď osoba (recepty na varenie, rôzne návody, algoritmy na matematické výpočty) alebo technické zariadenie. Rôzne stroje (počítače, priemyselné roboty, moderné domáce spotrebiče) sú formálnych vykonávateľov algoritmy. Formálny umelec nemusí pochopiť podstatu riešeného problému, ale musí presne vykonať postupnosť príkazov.

Algoritmus je možné napísať rôznymi spôsobmi (slovný popis, grafický popis - bloková schéma, program v niektorom z programovacích jazykov a pod.). Program je zapísaný algoritmusprogramovací jazyk .

Na vytvorenie algoritmu (programu) potrebujete vedieť:

kompletný súbor údajov počiatočnej úlohy (počiatočný stav objektu);

účel vytvorenia algoritmu (konečný stav objektu);

príkazový systém interpreta (teda súbor príkazov, ktorým interpret rozumie a môže ich vykonať).

Výsledný algoritmus (program) musí mať nasledujúcu sadu vlastností:

diskrétnosť (algoritmus je rozdelený na samostatné kroky - príkazy);

jednoznačnosť (každý príkaz určuje jedinú možnú akciu vykonávateľa);

jasnosť (všetky príkazy algoritmu sú zahrnuté v systéme príkazov vykonávateľa);

efektívnosť (herec musí problém vyriešiť v konečnom počte krokov).

Väčšina algoritmov má tiež vlastnosť masový charakter (pomocou rovnakého algoritmu môžete vyriešiť mnoho podobných problémov).

Spôsoby opisu algoritmov

Vyššie bolo uvedené, že ten istý algoritmus môže byť napísaný rôznymi spôsobmi. Algoritmus si môžete zapísať prirodzený jazyk. Takto používame recepty, návody atď. Nahrávať algoritmy určené pre formálnych interpretov, špeciálne programovacie jazyky. Je možné opísať akýkoľvek algoritmus graficky vo forme blokovej schémy. Na tento účel bol vyvinutý špeciálny notačný systém:

Označenie	Popis	Poznámky
	Začiatok a koniec algoritmu
	Vstup a výstup dát.	Výstup údajov sa niekedy označuje inak:
	Akcia	Vo výpočtových algoritmoch sa to používa na označenie priradenia
	Vidlička	Vidlica - komponent potrebný na realizáciu vetiev a slučiek
	Spustenie cyklu s parametrom
	Typický proces	V programovaní - procedúry alebo podprogramy
	Prechody medzi blokmi

Uveďme príklad popisu algoritmu na sčítanie dvoch veličín vo forme blokového diagramu:

Tento spôsob opisu algoritmu je pre ľudí najnázornejší a najzrozumiteľnejší. Preto sa algoritmy formálnych vykonávateľov zvyčajne najskôr vyvinú vo forme vývojového diagramu a až potom sa vytvorí program na jednom zprogramovacie jazyky .

Typické algoritmické štruktúry

Programátor má možnosť zostaviť a použiť atypické algoritmické štruktúry, čo však nie je potrebné. Akýkoľvek algoritmus, bez ohľadu na to, aký je zložitý, môže byť vyvinutý na základe troch typických štruktúr: sledovanie, vetvenie a opakovanie. V tomto prípade môžu byť štruktúry umiestnené postupne jedna po druhej alebo vnorené do seba.

Lineárna štruktúra (nasledujúca)

Najjednoduchšia algoritmická štruktúra je lineárne. V ňom sa všetky operácie vykonávajú raz v poradí, v akom sú zaznamenané.

Vetvenie

IN úplné rozvetvenie Existujú dve možnosti pre akcie interpreta v závislosti od hodnoty logického výrazu (podmienky). Ak je podmienka pravdivá, vykoná sa iba prvá vetva, inak iba druhá vetva.

Druhá vetva môže byť prázdna. Táto štruktúra sa nazýva neúplné rozvetvenie alebo obtok.

Z niekoľkých vetiev môžete zostaviť štruktúru „ výber“(viacnásobné vetvenie), ktoré si nebude vyberať z dvoch, ale z väčšieho počtu možností konania výkonného umelca v závislosti od niekoľkých podmienok. Je dôležité, aby bola vykonaná iba jedna vetva - v takejto štruktúre je poradie podmienok dôležité: ak je splnených niekoľko podmienok, potom bude fungovať iba jedna z nich - prvá zhora.

Cyklus (opakovanie)

Cyklusumožňuje organizovať viacero opakovaní rovnakej postupnosti príkazov- nazýva sa telom cyklu. V rôznych typoch cyklických algoritmov môže počet opakovaní závisieť od hodnoty logického výrazu (podmienky) alebo môže byť pevne zakódovaný v samotnej štruktúre. Existujú cykly: „ predtým», « Zbohom», slučky s počítadlom. V cykloch „until“ a „while“ môže pred telom cyklu ( slučka s predpokladom) alebo ukončiť cyklus ( slučka s dodatočnou podmienkou).

Cykly« predtým» - opakovanie tela cyklu kým nie je splnená podmienka:

Cykly « Zbohom» - opakovanie tela cyklu pokiaľ je splnená podmienka(pravda):

Slučky s počítadlom(s parametrom)– opakovanie tela cyklu určený počet krát:

Pomocný algoritmus (podprogram, postup)

Pomocný algoritmus je modul, ku ktorému je možné opakovane pristupovať z hlavného algoritmu. Použitie pomocných algoritmov môže výrazne znížiť veľkosť algoritmu a zjednodušiť jeho vývoj.

Metódy vývoja zložitých algoritmov

Existujú dva spôsoby vývoja zložitých algoritmov:

Metóda postupného rozpisovania úloh(„zhora nadol“) znamená, že pôvodná komplexná úloha je rozdelená na čiastkové úlohy. Každá z čiastkových úloh sa posudzuje a rieši samostatne. Ak sú niektoré z čiastkových úloh zložité, sú tiež rozdelené na čiastkové úlohy. Proces pokračuje, kým sa čiastkové úlohy nezredukujú na základné. Riešenia jednotlivých podproblémov sú potom spojené do jedného algoritmu na riešenie pôvodného problému. Metóda je široko používaná, pretože umožňuje niekoľkým programátorom súčasne vyvíjať všeobecný algoritmus a riešiť lokálne podproblémy. To je nevyhnutná podmienka pre rýchly vývoj softvéru.

Spôsob montáže(„zdola nahor“) spočíva vo vytváraní rôznych softvérových modulov, ktoré implementujú riešenie typických problémov. Pri riešení zložitého problému môže programátor použiť vyvinuté moduly ako pomocné algoritmy (postupy). V mnohých programovacie systémy Podobné sady modulov už existujú, čo výrazne zjednodušuje a urýchľuje tvorbu zložitého algoritmu.

Algoritmy a riadiace procesy

Kontrola - účelná interakcia objektov, z ktorých niektoré sú manažérmi, iné - riadené.

V najjednoduchšom prípade existujú dva takéto objekty:

Z pohľadu informatiky kontrolné akcie možno považovať za kontrolné informácie. Informácie je možné prenášať vo forme príkazov. Volá sa postupnosť príkazov na ovládanie objektu vedúci k vopred stanovenému cieľu riadiaci algoritmus. V dôsledku toho možno riadiaci objekt nazvať vykonávateľom riadiaceho algoritmu. V uvažovanom príklade ovládací objekt funguje „bez toho, aby sa pozrel“ na to, čo sa deje s ovládacím objektom ( ovládanie s otvorenou slučkou OTVORENÉ. Iná schéma riadenia môže brať do úvahy informácie o procesoch vyskytujúcich sa v riadiacom objekte:

V tomto prípade musí byť riadiaci algoritmus dostatočne flexibilný na to, aby analyzoval tieto informácie a rozhodoval o svojich ďalších akciách v závislosti od stavu riadiaceho objektu ( spätnou väzbou). Táto schéma ovládania sa nazýva ZATVORENÉ.

Procesy riadenia sú podrobnejšie študované a diskutované kybernetika. Táto veda tvrdí, že najrozmanitejšie procesy riadenia v spoločnosti, prírode a technike prebiehajú podobným spôsobom a podliehajú rovnakým princípom.

Na začiatok témy