Programování pro deskriptivní geometrii Luboš Moravec Katedra didaktiky matematiky Matematicko-fyzikální fakulta Univerzita Karlova v Praze Gymnázium Na Pražačce, Praha
21. 10. 2013
Luboš Moravec (KDM MFF UK)
Programování pro DG
21. 10. 2013
1 / 10
Doporučená literatura
algoritmy a datové struktury Töpfer, P.: Algoritmy a programovací techniky, Prometheus, Praha používá Pascal
Wróblewski, P.: Algoritmy: Datové struktury a programovací techniky, Computer Press, Praha používá C++
jazyk Python Swaroop C. H.: A Byte of Python, dostupné online Švec J.: Učebnice jazyka Python, dostupné online pro starší verzi Pythonu
Downey A.: Think Python, dostupné online Pilgrim M: Ponořme se do Pythonu 3, dostupné online a další
Luboš Moravec (KDM MFF UK)
Programování pro DG
21. 10. 2013
2 / 10
Algoritmus podle jména matematika al-Chwárizmího postup, resp. návod jak vyřešit daný problém pro rozličné hodnoty jeho parametrů příklady písemné sčítání, násobení, dělení konstrukce trojúhelníka podle věty sss řešení soustavy rovnic sčítací metodou cesta do školy psaní slova na mobilu přesazování begonií otevírání dveří apod.
zajímá nás konečnost správnost složitost (efektivita) Luboš Moravec (KDM MFF UK)
Programování pro DG
21. 10. 2013
3 / 10
Složitost algoritmu
základní dělení paměťová náročnost algoritmu na obsazenou paměť v průběhu výpočtu vyjadřuje nárůst paměti použité v průběhu výpočtu v závislosti na velikosti dat v současnosti je paměti relativní dostatek, avšak její kapacita není nekonečná
časová vyjadřuje nárůst doby výpočtu v závislosti na velikosti dat nepříznivá může vést k nepoužitelnosti algoritmu pro větší data
někdy lze např. zajistit lepší časovou složitost za cenu zhoršení paměťové budeme se snažit je odhadovat a porovnávat tak naše algoritmy
Luboš Moravec (KDM MFF UK)
Programování pro DG
21. 10. 2013
4 / 10
Časová složitost soustředíme se především na asymptotickou složitost tedy na složitost pro nekonečně velká data pro malá data může být jiná
rozlišujeme složitost v nejlepším případě v průměrném případě v nejhorším případě
symbol O(n) složitost vyjadřujeme funkcí, obvykle nás zajímá jen nejsilnější člen výrazu pro data velikosti n tedy např.: O(n) = log n O(n) = n O(n) = n · log n O(n) = n2 O(n) = 2n Luboš Moravec (KDM MFF UK)
Programování pro DG
21. 10. 2013
5 / 10
Příklad vyhledání údaje v setříděné posloupnosti dat číslo v telefonním seznamu záznam v kartotéce kapitola v knize
možnosti postupné hledání od začátku do konce v nejhorším případě O(n) zvětší-li se data 100×, i čas výpočtu se 100× prodlouží použijeme-li dvakrát rychlejší počítač, výpočet bude trvat poloviční dobu
vyhledávání půlením intervalů v nejhorším případě O(log2 n) zvětší-li se data 100× čas vzroste 6,64× použijeme-li dvakrát rychlejší počítač, výpočet bude trvat 2n × kratší dobu
naopak, pokud bychom měli algoritmus s exponenciální složitostí (např. prohledávání všech možností při šachu), zrychlení počítače by na rychlost výpočtu mělo jen nepatrný vliv Luboš Moravec (KDM MFF UK)
Programování pro DG
21. 10. 2013
6 / 10
Složitost problému
vedle složitosti algoritmu můžeme také zjišťovat složitost problému stanoví, jak nejrychleji lze daný problém řešit bez ohledu na známost algoritmu dané rychlosti
Luboš Moravec (KDM MFF UK)
Programování pro DG
21. 10. 2013
7 / 10
Programovací jazyk
způsob zápisu algoritmu různé filosofie, různé přístupy pro počítač tvoříme zdrojový kód (obvykle prostý textový soubor) kompilované jazyky (Pascal, C++) překládají zdrojový kód do strojového a vytváří samostatně spustitelný binární kód rychlejší náročnější na technické porozumění dané platformě
interpretované (PHP, Python, Java) program (běhové prostředí) provádí zadané instrukce bez překladu nutnost nainstalovaného běhového prostředí obvykle pomalejší nezávislé na platformě
Luboš Moravec (KDM MFF UK)
Programování pro DG
21. 10. 2013
8 / 10
Proč Python
moderní a používaný stručný, jasný, výstižný, přímočarý, pragmatický syntaxe nutí k přehlednému kódu vysoko položený – bez technických podrobností umožňuje soustředit se na algoritmus, ne na překlad do jazyka snadno dostupný včetně základního IDE multiplatformní rozumí si s češtinou
Luboš Moravec (KDM MFF UK)
Programování pro DG
21. 10. 2013
9 / 10
Hello world! vypíše na obrazovku Hello world! Python print(’Hello world!’) Pascal begin write(’Hello world!’); end. Java public class HelloWorld { public static void main(String[] args) { System.out.println("Hello world!"); } } Luboš Moravec (KDM MFF UK)
Programování pro DG
21. 10. 2013
10 / 10
