Načítání stránky…

Nároky algoritmu

Připravit hodinu Všechny formáty

Žák posuzuje, jak se s rostoucí velikostí vstupu mění časové a paměťové nároky algoritmu, a umí to vztáhnout k výstupu RVP G. Nejde o měření konkrétního počítače ani o sítě, ale o to, zda řešení při zdvojnásobení dat „jen trochu zpomalí“, nebo se stane nepoužitelným. Druhé hledisko je srozumitelnost: kratší nebo chytřejší zápis nemusí být vhodnější, pokud ho třída nedokáže ověřit.

Klikněte a tvořte

Získejte přípravu zdarma

Vyberte formát. Jedním kliknutím otevřete tvorbu na téma Nároky algoritmu (II. ročník) — ScioBot ho připraví za vás.

Připravit hodinu

Další formáty na jedno kliknutí

Téma si můžete upravit. Předmět a ročník už jsou vyplněné — stačí si vybrat, co chcete vytvořit.

O tématu

Porovnání dvou řešení stejného problému (např. hledání maxima, součtu, řazení nebo hledání v seznamu) žáci opírají o stejné vstupy různé délky a o pozorování z krokování a ladění. Vyberou algoritmus podle zvoleného hlediska — čas, paměť, nebo čitelnost — a umí říct, co by na algoritmu změnili, aby se hledisko zlepšilo, aniž by se ztratila správnost.

Zobecnění znamená, že totéž pravidlo (lineární průchod, zbytečné vnořené cykly, zbytečné kopírování seznamu) přenesou na podobnou úlohu, ne že recitují vzorce složitosti bez vztahu k datům.

Graf růstu počtu operací podle velikosti vstupu
Ukázka měření rekurzivního lineárního hledání
Porovnání dvou algoritmů řazení na stejném poli
Zdroje obrázků
  1. Cmglee · CC BY-SA 4.0
  2. John William Stafford · CC BY-SA 4.0
  3. Marcellolarocca · CC BY-SA 4.0

Předpoklady

  • Vlastnosti algoritmu, zápis postupu a rozklad na kroky
  • Větvení a cykly: kolikrát se tělo cyklu provede
  • Seznamy: délka vstupu a průchod prvky
  • Testování a ladění: vliv vstupních dat na běh

Klíčové pojmy

Velikost vstupu

Číslo, které vystihuje, kolik dat algoritmus zpracovává (délka seznamu, počet čísel). Nároky se hodnotí vůči této velikosti, ne vůči „rychlosti notebooku“.

Časové nároky

Kolik základních kroků (porovnání, přiřazení, průchod prvkem) algoritmus udělá, když vstup roste. Žák to odhadne z počtu opakování cyklů, ne z hodinových údajů procesoru.

Paměťové nároky

Kolik pomocných hodnot nebo kopií dat algoritmus navíc potřebuje. Nový seznam stejné délky je jiný nárok než několik proměnných.

Porovnání podle hlediska

Dvě správná řešení se mohou lišit časem, pamětí i srozumitelností. Výběr „lepšího“ platí jen k zvolenému kritériu a k charakteru vstupu.

Vliv vstupních dat

Stejný kód se chová jinak u prázdného, krátkého, dlouhého nebo už seřazeného vstupu. To souvisí s běhovým chováním a s testováním, ne jen se syntaxí.

Vylepšení algoritmu

Úprava, která sníží zbytečnou práci (druhý průchod, vnořený cyklus navíc, kopírování celého seznamu), aniž se změní výsledek pro stejné vstupy.

Srozumitelnost jako hledisko

Řešení, které třída dokáže krokovat a obhájit, může být vhodnější než kratší zápis, který nikdo neověří — zejména u školních úloh a údržby kódu.

Nápady na aktivity

  1. Rozhodování

    Volba algoritmu podle velikosti vstupu

    Žáci porovnají dvě řešení pro různě velké vstupy a vyberou vhodnější podle času, paměti nebo srozumitelnosti. U každé volby rozhodnou, která vlastnost je pro danou situaci důležitá.

  2. Kvíz

    Porovnání časové a paměťové náročnosti

    Žáci vyberou, které ze dvou řešení bude pro zadaný rozsah vstupu vhodnější. Otázky se zaměří na odhad růstu nároků a na důvody volby.

  3. Postup

    Růst nároků při zvětšování vstupu

    Žáci seřadí kroky úvahy, jak se s rostoucím vstupem mění časové nebo paměťové nároky algoritmu a jak z toho odvodit vhodnější řešení.

  4. Pexeso a spojovačka

    Situace a vhodnější algoritmické řešení

    Žáci přiřadí popis situace, například velikost vstupu či omezení paměti, k vhodnějšímu ze dvou řešení a jeho zdůvodnění.

  5. Rozřazování

    Řešení podle hlavního omezení

    Žáci roztřídí popisy algoritmických řešení podle toho, zda jsou vhodnější při důrazu na čas, paměť nebo srozumitelnost, a porovnají důvody zařazení.

  6. Logický řetěz

    Jak velikost vstupu mění volbu řešení

    Žáci skládají řetězce příčiny a důsledku: větší vstup zvyšuje nároky řešení, což vede k jiné volbě algoritmu podle času, paměti nebo srozumitelnosti.

Časté miskoncepce

  • Častá chyba

    „Můj program je rychlejší, protože na mém počítači doběhl dřív.“

    Jak na to

    Nechte oba programy zpracovat stejné tři vstupy (např. 10, 1 000 a 10 000 prvků) a porovnejte počet kroků nebo počet průchodů cyklem, ne stopky jednoho stroje.

  • Častá chyba

    „Když je v kódu míň řádků, je algoritmus méně náročný.“

    Jak na to

    Dejte vedle sebe krátký zápis s vnořenými cykly a delší s jedním průchodem; žáci spočítají, kolikrát se vnitřní tělo provede při n prvcích.

  • Častá chyba

    „Seznam délky n vždycky potřebuje n² kroků.“

    Jak na to

    Ukažte hledání maxima (jeden průchod) a naivní porovnání každého s každým; žáci přiřadí, který vzor patří ke které úloze.

  • Častá chyba

    „Optimalizace znamená smazat komentáře a zkrátit názvy proměnných.“

    Jak na to

    Opravte na konkrétním kódu zbytečné druhé procházení seznamu; komentáře nechte a ptejte se, zda se výsledek a počet průchodů změnily.

Úkoly pro žáky

  • Porovnávací tabulka: dvě implementace (např. součet v jednom cyklu vs. opakované sčítání od začátku); sloupce n, počet kroků, pomocná paměť, srozumitelnost, doporučení.

  • Úprava kódu: dostanou funkční, ale zbytečně náročný postup (kopie seznamu v každé iteraci); navrhnou vylepšení a ověří stejnými testovacími vstupy.

Hodnocení

Žák na dvou správných řešeních stejné úlohy uvede, jak se nároky mění s délkou vstupu, a vybere vhodnější podle zadaného hlediska (čas, paměť, nebo srozumitelnost).

Žák navrhne jednu konkrétní úpravu algoritmu, která sníží zbytečnou práci, a ověří, že výsledky na připravených vstupech zůstanou stejné.

Očekávané výstupy

  • RVP G žák ve vztahu k charakteru a velikosti vstupu hodnotí nároky algoritmů; porovná algoritmy podle různých hledisek, vybere pro řešený problém ten nejvhodnější; vylepší algoritmus podle zvoleného hlediska; zobecní řešení pro širší třídu problémů

Zdroje

Učíte Nároky algoritmu trochu jinak?

Popište ScioBotu vlastními slovy, co s žáky chcete zvládnout a kolik máte času. Materiál přizpůsobí vašemu ŠVP, třídě i žákům se speciálními vzdělávacími potřebami.

Napsat ScioBotu

Prozkoumejte další témata