- korektní = dělat, co chceme
- efektivní = rychlé
- čitelné = aby ostatní prog. tomu porozuměli
- Algoritmus = postup pro vyřešení určitého typu problémů
- vlastnosti algoritmů
- jasný vstup a výstup
- obecnost = pro řešení typové úlohy ne konkrétní
- determinovanost
- každý krok je jasně a přesně definován
- konečnost = algoritmus někdy skončí
- elementárnost = skládá se z jednoduchých kroků
- (efektivita)
- programování = zápis algoritmu pro počítač
- REPL (read-eval-print loop)
python -i filename.py interaktivní načtení programu do interpretu- PEP8 (link)
- umocňování
**
- celočíselné dělení
// (NE int(x / 10)!!)
range(10) == [0, ..., 10]- procedura = fce, která má vedlejší efekty
- čistá fce = nemá vedlejší efekty (změna globální proměnné, I/O funkce, random, změna proměnných mimo scope funkce)
- predikát = čistá fce, která vrací
True/False
- DRY (don’t repeat yourself)
Doporučení pro psaní funkcí
nejprve ujasnit specifikaci (vstupně/výstupní chování)
- jaké potřebuje vstupy?
- co bude výstupem funkce?
funkce by měly být krátké
- jedna myšlenka
- pár úrovní zanoření
Největší společný dělitel
Euklidův algoritmus
- Jestliže
a > b, pak platí, že gcd(a, b) = gcd(a - b, b)
Lepší algoritmus
gcd(a, b) = gcd(a mod b, b)
list comprehension = s = [2 * x for x in range(10)]
!!!Nikdy nepoužívat implicitní parametry s měnitelnými proměnnými - listy !!!
Řetězce jsou neměnné!
Formátování řetězců: pyformat.info
"{:d}".format(123)
.split()
.join()
precodnition = Vstupní podmínka algoritmu
postconditoin = Výstupní podmínka algoritmu
Algoritmus je korektní, pokud pro všechny stupy splňující vstupní podmínku skončí a jeho efekt splňuje výstupní podmínku.
assert slouží pro ověření chyby programátora, ne vstupu uživatele!
Abstraktní datový typ (uživatelský pohled na data)
- rozhraní
- popis operací, které chceme provádět
Konkrétní datová struktura (implementační pohled na data)
- implementace
- přesný popis uložení dat v paměti
- definice funkcí pro práci s těmito daty
- seznam
- Jednosměrný zřetězený seznam: data + další prvek
- Obousměrně zřetězený seznam: data + další prvek + předchozí prvek
- Dynamické pole: Mám danou velikost, avšak můžu tuto velikost měnit.
- zásobník
- fronta; prioritní fronta
- množina
- slovník (asociativní pole)
- souvislý úsek paměti
- všechny prvky mají stejnou velikost
- indexování je velmi rychlé
- nedá se snadno rozšiřovat
v pythonu
konstatní:
- indexování
list[i]
- délka
len(list)
- odstranění prvku z konce
list.pop()
- přidávání prvků na konec
seznam.append(prvek)
Lineární:
- kopie seznamu (i části
list[x:y])
- hledání prvku v seznamu
in nebo .index
- mazání nebo přidávání prvků uprostřed nebo na začátku
- spojování seznamů pomocí
+
- LIFO (Last In First Out)
- operace:
- push (vložení)
- pop (odstranění)
- top (náhled na vrchní prvek)
- empty
- FIFO (First In First Out)
- operace
- enqueue (vložení)
- dequeue (odstranění)
- front (náhled na přední prvek)
- empty
- použití knihovny
collections
- datový typ
deque (oboustranná fronta)
- vložení append
- odebírání
popleft
- neuspořádaná kolekce dat bez vícenásobných prvků
- operace
- neuspořádaná množina dvojic (klíč, hodnota)
- klíče jsou unikání
- operace jako u množiny (insert, find, delete)
- navíc přístup k hodnotě pomocí klíče
- klíče jsou neměnné, ale hodnoty se smí měnit
- datový typ složený z více položek různých typů
- typicky fixní počet
- často rozšíření struktur
- kombinují data funkce (metody)
- dědičnost, polymorfismus
V obecném seznamu
- vstup: seznam čísel (objektů) + dotaz(číslo)
- výstup: odpověď
True/False, jestli je číslo v seznamu
- alt. výstup: index čísla v seznamu
- časová složitost: cca délka seznamu
in, seznam.index()
V seřazeném seznamu:
- vstup: seřazený seznam čísel (objektů) + dotaz(číslo)
- výstup: odpověď
True/False, jestli je číslo v seznamu, případně index prvku
- rozumné řešení: půlení intervalů (
log N)
- půlení intervalu
- podíváme se na prostřední prvek seznamu
- podle jeho hodnoty buď skončíme, nebo pokračujeme doleva nebo doprava
- udržujeme si ,,dolní“ a ,,horní“ mez
- funkce, která délce vstupu přiřazuje počet kroků
- typicky nejhorší případ
- co jsou
- základní kroky, které počítáme
- velikost vstupu
Asymptotická časová složitost: viz haskell (Big O notation)
Select sort: nejmenší prvek na správné místo, nejmenší prvek zbytku na správné místo, …
- best case = worst case = O(n^2)
Insert sort: seřazená část a neseřazená část, vezmu jeden prvek z neseřazené části a zařadím do seřazené části
- best case = O(n)
- worst case = O(n^2)
Bubble sort: very bad
Quick sort: pivot (jeden prvek) a rozdělím seznam na menší než pivot, pivot a větší než pivot
- worst case = O(n^2)
- avg case = O(n log n) (závisí na výběru pivota
Merge sort: rozdělíme seznam na dvě poloviny, rekurzivně seřadíme vzniklé menší seznamy, spojíme do jednoho (merge)
- worst case = O(n log n) = nejlepší, co jde
my_list.sorted() = modifikuje list
sorted(my_list) = vytvoří nový list
- odkaz sám na sebe
- při vymýšlení algoritmu můžeme předpokládat, že menší instanci někdo vyřeší za nás
- Báze = Dostatečně jednoduché vstupy musíme vyřešit přímo.
- Rekurzivní volání musí být v nějakém smyslu jednodušší než aktuální problém.
(Korekurze (corecursion) - něco jiného pro pokročilé)
- rekurzivní funkce se nemusí vola přímo, ale i skrz jinou funkci
- nakreslit kmen
- nakreslit dva menší stromečky (pootočené)
- vrátit se zpátky
- velikost zásobníku volání je nějak omezena (stack overflow)
- každý rekurzivní program je možno přepsat jako iterativní pomocí zásobníku
- rekurzivní volání je to poslední, co se ve funkci stane
- lze snadno nahradit cyklem, bez použití zásobníku
- některé kompilátory/interprety toto optimalizující samy
- Hánosjké věže
- Sierpińský trojúhelník
- Program, který vypíše sám sebe
- List item
- hodnota má 2 složky: jedna typu A, druhá typu B
- ntice, záznamy (
record,struct)
- hodnota je buď typu A nebo typu B
- (tagged) Union, variant
- (disjuktní) sjednocení
Union[X, Y]
- buď hodnota typu X nebo typu Y
- možno i více typů:
Union[X, Y, Z]
- problém splnění omezení (constraint satisfaction problem)
- komunikace se systémem
sys.argv = seznam parametrů z příkazové řádkysys.stdin, sys.stdout, sys.stderrsys.exit = ukončí program, jestli program skončil v pořádku nebo ne
- vrací seznam souborů odpovídající danému POSIXovému vzoru
- práce se souborovým systémem
time.time = aktuální čas float v sekundách od 1.1.1970 0.00 UTC
- jednoduchý modul pro vytváření grafických uživatelských rozhraní - GUI
- source code
- -> lexing (lexical analysis) & parsing (syntatical analysis)
- -> AST (Abstract Syntax Tree)
- -> Intermediate code
- -> bytecode (sortof readable) -> interpret
- -> machine code