4 Flashcards
(14 cards)
Co je to algoritmus
Přesný návod nebo postup, kterým můžeme vyřešit určitý typ úlohy. Algoritmus musí být konečný, výpočetní metoda nemusí být
Jaké má vlastnosti algoritmus
Konečnost - každý algoritmus musí skončit pro každý vstup
Obecnost — algoritmus musí být co nejvíce obecný
Determinovanost — každý krok algoritmu musí být pevně definován( když algoritmus pustíme 1000x se stejnýma vstupními daty dostaneme stejný výsledek
Výstup — musí mít aspoň jeden výstup
Co je to rekurzivní algoritmus
Algoritmus který volá sám sebe ale ne do nekonečna. Je tam nějaká podmínka kdy se má ukončit. Každý rekurzivní algoritmus lze přepsat bez rekurze
Jak se dělí rekurze
Na přímou/nepřímou a lineární/stromovou
Přímá podprogram vola sám sebe
Nepřímá podprogram vola jinou metodu a ta pak vola zase ten podprogram (kruh)
Lineární podprogram volá sám sebe jen jednou
Stromová - s každým dalším voláním sama sebe se podprogram vola víckrát
Co je to hladový algoritmus
Řeší problém obchodního cestujícího.
Algoritmus nahodnoti prvky a vybere vždy ten nejlepší prvek pak jde dal a opakuje dokud nedojde nakonec. Jakmile je jedno rozhodnutí učiněno uz se nevezme zpátky. (Algoritmus nekontroluje jestli sel správnou cestou )
Co je to algoritmus typu rozděl a panuj
Algoritmus rozdělí problém na menší podproblemy a ty pak řeší rekurzivně nebo iterativně nakonec se často sloučí ( používá se třeba pro quicksort)
Co je to pravděpodobnostní algoritmus
Provádí některá rozhodnutí náhodně snaží se najít řešení co nejrychleji .
Pros hejny vstup má rozdílné výsledky , musí se pustit vícekrát abychom došli k nějakému rozumnému řešení .muze to byt ale kratší než deterministicky
Co je to algoritmus dynamického programování
Rozdělí problémy na složité a jednoduché. Složité pak využívají výsledku těch jednoduchých a řeší se tak lépe.
Co je to heuristický algoritmus
Nema za cíl najít přesné řešení, jen co nejbližší . Používá se kdyz máme nedostatek zdrojů pro přesné algoritmy
Jaké máme metody zrychlování algoritmů
Předzpracování dat
Odstranění rekurze
Optimalizace výpočtu pro hardware ( dobrá práce s paměti )
Odstranění duplicitního kódu
Optimalizace zdrojového kódu
Co je verifikace algoritmu jaky je rozdíl oproti testování
Princip je že máme nějaký program a popis jeho předpokládaného chování
Verifikace pak ma dokázat že je program správný vzhledem k zadaným predikátům .
Oproti Testivani dokazujeme nepřítomnost chyby ne přítomnost
Jaké máme predikáty
Vstupní - vstupní filtr (omezuje jaká data a Va jaké formě jsou aby mohli do programu )
Výstupní říká jak vypadá vnitřek programu po ukončení, proměnné a cykly
Jaké máme vektory
Vstupní vektor - vstupní proměnné
Vektor programu - vnitřní pomocné proměnné , mezivýsledky
Výstupní vektor - výstupní data v momentě ukončení
Jaké máme korektnosti
Parciální dochází k verifikaci programu vzhledem k predikátům rozděleného do menších částí
Totální dochází k verifikaci celého programu vzhledem k predikátům
