Co je algoritmický model Algoritmus je jasný a přesný pokyn pro konkrétního interpreta, aby provedl konečnou sekvenci akcí vedoucí ke stanovenému cíli. Fáze činnosti od definování cíle (stanovení úkolu) po získání výsledku jsou následující: informační modelčinnosti interpreta. Takový model budeme nazývat algoritmický.
Řídící systém exekutora Abyste mohli sestavit skutečný plán - algoritmus, který se ukáže jako proveditelný, musíte přesně znát schopnosti exekutora. Tyto možnosti určuje systém příkazů vykonavatele (SCI). Při sestavování algoritmu není možné překročit rámec SQI. Toto je vlastnost srozumitelnosti algoritmu. Pro automat je SKI přísně definovanou konečnou množinou příkazů, které do něj konstruktéři vložili. Algoritmus je tedy přesným popisem jeho práce a automat vykonává práci formálně podle pokynů algoritmu. Pro ovládání automatu nebo počítače není těžké přijít s formalizovaným jazykem pro popis algoritmů. Takové jazyky se nazývají programovací jazyky a algoritmus prezentovaný v programovacím jazyce se nazývá program.
Příklad algoritmického modelu První hráč uhodne celé číslo z daného rozsahu čísel, například od 1 do 100. Druhý hráč musí toto číslo uhodnout v nejmenším počtu otázek. Algoritmus pro hádání čísla metodou polovičního dělení, zaměřený na člověka. Algoritmus hádání čísel Je dán: rozsah čísel od A do B Potřebuji: Uhodnout číslo X, které má hráč na mysli pomocí algoritmu polovičního dělení Začátek 1) Zeptejte se: Je X menší než průměrná hodnota mezi A a B? 2) Pokud je odpověď „ANO“, vezměte celočíselnou část průměrné hodnoty jako hodnotu B. 3) Pokud je odpověď „NE“, vezměte jako hodnotu A nejbližší celé číslo větší, než je průměr. 4) Jsou-li hodnoty A a B stejné, jejich celková hodnota je požadované číslo X. 5) Pokud se hodnoty A a B nerovnají, vraťte se ke kroku 1. Konec Tento algoritmus je zaměřen na lidský umělec, ne počítač.
Algoritmus "Poloviční dělení" Alg Poloviční dělení Int A, B, X Začátek Zadejte A, B, X Zatímco A B, opakujte Nc Pokud X (A + B) / 2 Pak B: \u003d Int ((A + B) / 2) Jinak A:=Cíl ((A+B)/2)+1 Kv Kts Výstup A Konec Začátek Začátek Konec Vstup A, B, X Výstup A AB X(A+B)/2 B:=TEST ((A+B )/2)A:=CÍL ((A+B)/2)+1 ne ano ne ano
Vývojový diagram Vývojový diagram je orientovaný graf, který ukazuje pořadí provádění příkazů algoritmu prováděcím programem. Bloky – vrcholy tohoto grafu – označují jednotlivé příkazy, které jsou zadávány interpretovi, a oblouky označují sled přechodů z jednoho příkazu na druhý. V obdélnících na vývojových diagramech se píší příkazy - akce, v kosočtvercích - podmínky, které určují směr dalšího provádění příkazů; v paralelogramech - příkazy pro vstup nebo výstup informace; v oválech – začátek nebo konec provádění algoritmu. Zde můžeme mluvit o dráze grafu během provádění algoritmu. Libovolná cesta začíná od vrcholu „Start“ a končí výstupem do vrcholu „End“ Uvnitř se cesta může lišit v závislosti na počátečních datech a na výsledcích kontroly podmínek. vývojový diagram - grafická podoba, algoritmický jazyk - dvě různé formy reprezentace algoritmického modelu.
Strukturální programování Struktura konstruovaného algoritmu je smyčka s vnořeným větvením. Jakýkoli algoritmus lze sestavit z kombinace tří základních algoritmických struktur: následování, větvení a smyčky. Toto tvrzení je základem techniky zvané strukturované programování. Moderní programovací jazyky usnadňují přechod od popisu algoritmu k programu, pokud je algoritmus strukturálně postaven. Nejracionálnějším modelem činnosti performera je proto strukturální algoritmický model.
Sledování algoritmu - model činnosti procesoru Pro kontrolu správnosti algoritmu není vůbec nutné překládat jej do programovacího jazyka a provádět testy na počítači. Algoritmus může člověk také otestovat – trasováním. Při ručním trasování osoba simuluje práci procesoru, provádí každý příkaz algoritmu a zadává výsledky provádění příkazů do tabulky trasování. Je to model toho, jak procesor pracuje při provádění programu. Program se provádí v krocích (první sloupec tabulky). Sloupec Algorithm Command zobrazuje obsah registru instrukcí procesoru. Kde je umístěn další příkaz. Sloupec "Proměnné" zobrazuje obsah paměťových buněk počítače (nebo paměťových registrů procesoru) přidělených hodnotám proměnných. Sloupec "Provedena akce" odráží akce provedené aritmeticko-logickou jednotkou procesoru.
Téma lekce: "Algoritmus jako model činnosti."
Účel: vysvětlit nové téma zajímavým a srozumitelným způsobem.
Seznámit studenty s tématem: „Pojem algoritmu. Typy algoritmů a jejich vlastnosti“;
Studenti by měli znát pojem algoritmus, vlastnosti algoritmů;
Studenti by měli být schopni uvést příklady algoritmů.
Během lekcí:
1. Organizační moment.
2.Studium nové téma.
Začněme se znovu zabývat konceptem algoritmu tím, že se podíváme na příklad. Předpokládejme, že chcete vystřihnout model auta z papíru. Výsledek bude do značné míry záviset na vašich dovednostech a zkušenostech. Dosažení svého cíle však bude mnohem snazší, pokud si nejprve nastíníte akční plán, například následující:
1. Prostudujte si obrázek vozu podle stávajícího modelu.
2. Nakreslete dveře, karoserii auta na papír.
3. Vystřihněte náčrty.
4. Pokuste se upevnit náčrty, opravit chyby.
5. Slepte části modelu.
Podle připraveného plánu každý člověk, i když nemá umělecké schopnosti, ale má trpělivost, určitě dosáhne dobrého výsledku. Podobný plán s Detailní popis akce nutné k získání očekávaného výsledku, nazývané algoritmus.
Pojem algoritmu. ( Uveďte další informace)
Vznik algoritmů je spojen se zrodem matematiky. Před více než 1000 lety (v roce 825) vytvořil vědec z města Khorezm Abdullah (nebo Abu Jafar) Mohammed bin Musa al-Khwarizmi knihu o matematice, ve které popsal metody provádění aritmetických operací na vícehodnotových číslech. Samotné slovo „algoritmus“ vzniklo v Evropě po překladu knihy tohoto středoasijského matematika do latiny, ve které bylo jeho jméno napsáno jako „Algoritmy“.
Algoritmus- popis sledu akcí (plánu), jejichž striktní provedení vede k řešení úkolu v konečném počtu kroků.
Algoritmizace- proces vývoje algoritmu (akčního plánu) pro řešení problému.
Příklady algoritmů:
Každé zařízení zakoupené v obchodě je dodáváno s návodem k jeho použití.
Každý řidič musí znát pravidla silničního provozu.
Hromadná výroba automobilů byla možná pouze tehdy, když byl vynalezen postup montáže automobilu na dopravník.
Vlastnosti algoritmů.
S algoritmy se setkáváme na každém kroku. Některé z nich děláme automaticky, aniž bychom o tom přemýšleli. Při provádění některých akcí ani nemáme podezření, že provádíme určitý algoritmus.
Tyto příklady nejsou nic jiného než algoritmus. Navzdory značnému rozdílu v podstatě jednání těchto příkladů v nich lze najít mnoho společného. Tyto Obecná charakteristika se nazývají vlastnosti algoritmu. Zvažme je.
diskrétnost(z latiny discretus - rozdělený, přerušovaný) - jedná se o rozdělení algoritmu na řadu samostatných dokončených akcí (kroků). Ve výše uvedených algoritmech je běžná potřeba striktního dodržování sledu akcí. Zkusme přeskupit druhou a třetí akci v prvním příkladu. Tento algoritmus můžete samozřejmě také spustit, ale dveře se pravděpodobně neotevřou. A pokud zaměníte, dejme tomu, pátý a druhý krok ve druhém příkladu, algoritmus se stane neproveditelným.
determinismus(z lat. určit - jistota, přesnost) - jakákoli akce algoritmu musí být v každém případě přesně a jednoznačně definována.
Pokud se například autobusy různých tras blíží k zastávce, musí být v algoritmu uvedeno konkrétní číslo trasy - 5. Kromě toho je nutné uvést přesný počet zastávek, které je třeba projet - řekněme tři.
Končetina- každá akce samostatně a algoritmus jako celek musí být schopen dokončit. V uvedených příkladech je každá popsaná akce skutečná a lze ji provést. Proto má algoritmus limitu, to znamená, že je konečný.
masový charakter- stejný algoritmus lze použít s různými počátečními daty.
Účinnost- v algoritmu nebyly žádné chyby.
Typy algoritmů.
Existují 4 typy algoritmů: lineární, cyklický, větvený, pomocný.
Lineární(sekvenční) algoritmus - popis akcí, které se provádějí jednou v daném pořadí.
Algoritmy pro odemykání dveří, vaření čaje, přípravu jednoho sendviče jsou lineární. Lineární algoritmus se používá při výpočtu aritmetického výrazu, pokud používá pouze operace sčítání a odčítání.
Cyklický algoritmus- popis akcí, které se mají opakovat stanovený počet opakování nebo dokud není splněna zadaná podmínka. Seznam opakovaných akcí se nazývá tělo smyčky.
Mnoho procesů v okolním světě je založeno na opakovaném opakování stejného sledu akcí. Jaro, léto, podzim a zima přichází každým rokem. Život rostlin prochází stejnými cykly po celý rok. Počítáním počtu celých otáček minutové nebo hodinové ručičky člověk měří čas.
Stav- výraz mezi slovem "pokud" a slovem "pak" a má hodnotu "pravda" nebo "nepravda".
Algoritmus větvení- algoritmus, ve kterém se v závislosti na stavu provádí jedna nebo druhá sekvence akcí.
Příklady větvených algoritmů: pokud začalo pršet, musíte otevřít deštník; pokud hrdlo bolí, pak by měla být procházka zrušena; pokud lístek do kina nestojí více než deset rublů, pak si kupte lístek a posaďte se v sále, jinak (pokud je cena lístku vyšší než 10 rublů) se vraťte domů.
V obecném případě bude schéma větvecího algoritmu vypadat takto: "pokud podmínka, pak ..., jinak ...". Tato reprezentace algoritmu se nazývá plná forma.
Neúplný formulář, ve kterém jsou vynechány akce: "pokud podmínka, tak...".
Algoritmus pomocníka- algoritmus, který lze použít v jiných algoritmech zadáním pouze jeho názvu.
Domácí práce. § šestnáct,
1. Vymyslete si vlastní příklady pro každý typ algoritmu.
2. Vytvořte algoritmus pro přecházení silnice se semaforem a bez něj.
Shrnutí lekce.
Děti, co jste se dnes naučili?
Dnes jsme se dozvěděli, co je to algoritmus, naučili jsme se typy a vlastnosti algoritmů
Obecní rozpočtová vzdělávací instituce
"Chubuklinskaya střední škola"
Zainsky městský obvod Republiky Tatarstán
Algoritmus jako model činnosti
(nákres lekce informatiky v 10. ročníku)
Učitel informatiky: Safiullina R.I.
Téma: Algoritmus jako model činnosti
Cíle: Zopakovat definici algoritmu, připomenout koncept modelu a definovat algoritmický model; Naučte se graficky znázorňovat jakoukoli činnost ve formě algoritmu; připomenout hlavní formy znázornění algoritmu ve formě vývojových diagramů. Rozvíjet schopnost naplánovat sled akcí k dosažení cíle. Formování kognitivního zájmu jako součást vzdělávací motivace.
Během vyučování
Organizace času
Zdravím studenty
Aktualizace získaných znalostí
co je to graf? Z čeho se skládá?
Který graf se nazývá neorientovaný (orientovaný)?
Co je to síť? Jaké jsou vlastnosti sítě?
Jaké systémy se nazývají hierarchické?
Jaká je výhoda tabulkové prezentace informací?
Co je to binární matice? Jaké informace obsahuje?
Řešení problému
č. 2 Láhev, sklenice, džbán a dóza obsahují mléko, limonádu, kvas a vodu. Je známo, že voda a mléko není v láhvi, nádoba s limonádou stojí mezi džbánem a nádobou s kvasem, v dóze není limonáda ani voda. Sklenice stojí poblíž sklenice a nádoby s mlékem. Kam se nalévá každá tekutina?
č. 3 V gymnastické soutěži Anya, Vera, Galya a Natasha obsadily první čtyři místa. Určete, kdo obsadil jaké místo, pokud je známo, že Galya je druhá, Natasha, i když se nestala vítězkou, se dostala mezi vítěze cen a Vera prohrála s Anyou.
Učení nového materiálu
Algoritmus je jasný a přesný pokyn pro konkrétního interpreta, aby dokončil závěrečnou sekvenci akcí vedoucích k vytyčenému cíli.
Fáze činnosti od definování cíle až po dosažení výsledku:
Příklady algoritmických modelů
První hráč uhodne celé číslo z daného rozsahu čísel, například od 1 do 100. Druhý hráč musí toto číslo uhodnout v nejmenším počtu otázek.
Pojďme napsat algoritmus pro hádání čísla metodou polovičního dělení, zaměřený na interpreta - osobu
Vzhledem k tomu: rozsah čísel od A do B
Nezbytné: hádejte číslo X, vytvořené hráčem, pomocí algoritmu polovičního dělení
Start
1. Zeptejte se: Je X menší než průměr mezi A a B?
2. Pokud je odpověď „ano“, vezměte jako hodnotu B celočíselnou část průměrné hodnoty
3. pokud je odpověď „ne“, vezměte jako hodnotu A nejbližší celé číslo větší, než je průměr
4. Pokud jsou hodnoty A a B stejné, je jejich celková hodnota požadované číslo X
5. Pokud se hodnoty A a B nerovnají, vraťte se ke kroku 1
Konec
Algoritmus uvádíme ve formě blokového diagramu.
Chcete-li zkontrolovat správnost algoritmu, musíte provést trasování.
|
Příkaz algoritmu |
Proměnné |
Popraven |
||||||
|
akce |
||||||||
|
Vstup A,B,X |
||||||||
Konsolidace studovaného materiálu
A) Na 48. straně učebnice je popsán algoritmus hledání největšího společného dělitele (Euklidův algoritmus), zaměřený na interpreta - osobu. Prezentujte jej ve formě blokového diagramu a v algoritmickém jazyce pro počítačový exekutor.
B) Po dokončení předchozího úkolu sledujte euklidovský algoritmus a najděte gcd čísel 128 a 56.
|
Úkon |
||||
| Dokument |
Co je algoritmický model? Proč může být algoritmus nazýván modelem a co modeluje? n Algoritmus je jasný a přesný příkaz pro konkrétního interpreta k dokončení konečné sekvence akcí vedoucích k cíli. To znamená, že cíle je dosaženo prostřednictvím činnosti nějakého interpreta.
Fáze činnosti: n n Definice cíle; Plánování práce výkonného umělce; Práce výkonného umělce; Získání výsledku. Kde je místo pro algoritmus? Algoritmus je podrobný plán práce interpreta, je to popis sledu akcí, které musí performer provést.
Proto je Algoritmus informačním modelem činnosti umělce. Takový model budeme nazývat algoritmický. Rýže. Fáze pohybu od cíle k výsledku. Stanovení cíle Konstrukce algoritmického plánu Model práce vykonavatele Práce vykonavatele Získání výsledku
Systém příkazů exekutora K sestavení skutečného plánu-algoritmu potřebujete znát schopnosti exekutora. Tyto možnosti určuje SCI. Při sestavování algoritmu nelze překročit rámec SCI. Je snazší sestavit algoritmus pro softwarově řízený automat než pro člověka. Pro automat je SCI přísně definovaná sada příkazů ve formalizovaném jazyce pro popis algoritmů. Takové jazyky se nazývají programovací jazyky a algoritmus se nazývá program. Lidské SCI nelze plně popsat.
Příklad algoritmického modelu. Úkol: Uhodnout celé číslo z daného rozsahu metodou polovičního dělení. První hráč uhodne celé číslo z daného rozsahu čísel, například od 1 do 100. Druhý hráč musí uhodnout číslo v nejmenším počtu otázek.
Algoritmus pro lidského umělce. Algoritmus hádání čísel Zadaný: Rozsah čísel od A do B Potřebuji: Uhodnout číslo X, které má hráč na mysli pomocí algoritmu polovičního dělení Začátek 1. Zeptejte se: Je X menší než průměr mezi A a B? 2. Pokud je odpověď "ano", vezměte jako hodnotu celočíselnou část průměrné hodnoty. 3. Pokud je odpověď „ne“, vezměte jako hodnotu A nejbližší celé číslo větší, než je průměr. 4. Jsou-li hodnoty A a B stejné, jejich celková hodnota je požadované číslo X. 5. Pokud se hodnoty A a B nerovnají, vraťte se k provedení odstavce 1. Konec
Algoritmus pro exekutor-počítač. Vývojový diagram Start Vstup A, B, X Ne A≠B Ano Ne 1 Pin A Konec
Algoritmus pro exekutor-počítač. Algoritmický jazyk Alg Bisection Int A, B, X Start Zadejte A, B, X Zatímco A≠B, opakujte Nc Pokud X≤(A+B)/2 Pak B: =INT((A+B)/2) Jinak A : \u003d CÍL ((A + B) / 2) + 1 Kč Závěr A Konec
Strukturální programování Struktura konstruovaného algoritmu je smyčka s vnořeným větvením. Jakýkoli algoritmus lze sestavit z kombinace tří základních algoritmických struktur: následovat, větvit a smyčku. Toto tvrzení je základem techniky zvané strukturované programování. Pokud je algoritmus postaven strukturálně, je snadné přejít od popisu algoritmu k programu.
Algoritmus trace - model procesoru. Pro kontrolu správnosti algoritmu není vůbec nutné jej překládat do programovacího jazyka. Algoritmus může člověk také otestovat – trasováním. Při ručním trasování osoba simuluje činnost procesoru provedením každé instrukce a zadáním výsledků instrukcí do tabulky trasování. Zvolme interval uhodnutých čísel od 1 do 8. Nechme hráče vymyslet číslo 3.
Krok č. Příkaz algoritmu Proměnné X A 3 1 Provedené akce B 1 Vstup A, B, X 2 A≠B 1 ≠ 8, ano 3 X ≤ (A+B)/2 3 ≤ 4, 5, ano 4 B: = CÍL ((A+B)/ 2) 5 A≠B 1 ≠ 4, ano 6 X ≤ (A+B)/2 3 ≤ 2,5, ne 3 1 8 4 B: = 4
7 A: =CÍL((A+B)/2+1) 3 8 A≠B 3 ≠ 4, ano 9 X ≤ (A+B)/2 3 ≤ 3,5, ano 10 V: =CÍL(( A+ B)/2) 11 A≠B 3 ≠ 3, ne 12 Pin A Odpověď: 3 3 4 3 A:=3 V:=3
Algoritmus trace - model procesoru. n n Program se provádí krok za krokem (první sloupec tabulky). Sloupec "Algorithm command" zobrazuje obsah registru příkazů procesoru, kde je umístěn další příkaz. Sloupec "Proměnné" zobrazuje obsah paměťových buněk přidělených proměnným. Sloupec "Provedena akce" odráží akce provedené aritmeticko-logickou jednotkou procesoru.
Závěr: n Algoritmus spolu s trasovací tabulkou tedy kompletně simuluje proces zpracování informací, který probíhá v počítači.
Systém základních pojmů Algoritmus - model činnosti Předmětem modelování je cílevědomá činnost performera. Lidský exekutor Automatický exekutor (včetně počítače) Neformalizované SCI Formy reprezentace algoritmů Blokové schéma Výukový algoritmický jazyk Programovací jazyk Algorithm tracing - postupné provádění algoritmu s testovací verzí výchozích dat. "Ruční trasování" - vyplnění tabulky trasování. Tabulka trasování je modelem činnosti procesoru během provádění algoritmu.
Domácí úkol § 16 přečtěte si, odpovězte na otázky 3, 4, 5, 8, 11 (jakékoli 3 otázky od dotazovaných)
Prezentovat jako vývojový diagram v prostředí Word Prezentovat tento algoritmus jako vývojový diagram pomocí automatických tvarů alg int celé číslo a, ba: =2 b: =0 nc až do a 10 a: =a+2 b: =b+3* a cc výstup b con