2 Z, Zk

NPRG030 Programování I NPRG031 Programování II

3/2 Z ----2/2 Z, Zk

Pavel Töpfer Katedra softwaru a výuky informatiky MFF UK MFF Malostranské nám., 4. patro, pracovna 404 [email protected] http://ksvi.mff.cuni.cz/~topfer

Pavel Töpfer, 2015

Programování I - 1

1

Cvičení NPRG030 Programování I podle studijních skupin 40+75, 41, 42, 43 Út, St, Čt v počítačové učebně SW2

Výběrová skupina cvičení NPRG030 Programování I pro pokročilé ze všech studijních skupin Út 9:00-10:30 S8 (Mareš) nahrazuje normální cvičení

NPRG047 Praktikum z programování pro začátečníky volitelný předmět navíc, nenahrazuje cvičení NPRG030 praktické procvičování základů – ladění programů na počítači Čt 17:20-18:50 SW2 (Töpfer) St 17:20-18:50 SW2 (Holan)

Pavel Töpfer, 2015


2

Algoritmizace - metody řešení úloh na počítači – algoritmy, datové struktury, programovací techniky Správnost algoritmu - konečnost, správné výsledky Efektivita algoritmu (složitost algoritmu) - časová (počet vykonaných operací) - prostorová (paměť potřebná na uložení dat) Programovací jazyk zápis algoritmu v programovacím jazyce = program - syntaxe (gramatika) - sémantika (význam) Programování jako „řemeslo“ - práce v integrovaném prostředí (editor + překladač + ladicí prostředky) - návrh testovacích dat, proces ladění programu Pavel Töpfer, 2015


3

Náplň zimního semestru Programovací jazyk: - deklarace (proměnné, konstanty, typy, inicializované proměnné) - jednoduché a strukturované datové typy (čísla, znaky, logické hodnoty, pole, znakové řetězce, záznamy) - jednoduché a strukturované příkazy (dosazovací příkaz, podmíněný příkaz, cyklus, složený příkaz) - textové soubory (včetně formátování výstupních dat) - procedury a funkce (lokalita identifikátorů, způsoby předávání parametrů, rekurze) - ukazatel, dynamicky alokované proměnné, dynamické datové struktury, lineární spojové seznamy, stromy - základní parametry překladače - návěští a příkazy skoku

Pavel Töpfer, 2015


4

Základní algoritmy a programovací techniky: - dělitelnost čísel, Eukleidův algoritmus - test prvočíselnosti, Eratosthenovo síto - Hornerovo schéma, poziční číselné soustavy - algoritmy vyhledávání v poli (sekvenční, binární, zarážka) - jednoduché třídění v poli - vnější třídění - halda, operace na haldě - práce s maticemi (základní operace) - operace s lineárními spojovými seznamy - implementace zásobníku a fronty v poli a spojovým seznamem - aritmetika s vyšší přesností („dlouhá čísla“ v poli a v LSS) - binární stromy, vyhledávací stromy, vyvažování (AVL, B-stromy) - aritmetické notace, převody a vyhodnocování - použití rekurze – backtracking, metoda „Rozděl a panuj“ - prohledávání do hloubky a do šířky - faktorové množiny Pavel Töpfer, 2015


5

Aktivní znalost integrovaného vývojového prostředí - editor, překlad, výpočet, trasování, sledování hodnot proměnných - ladění programů, testování správnosti (Borland Pascal nebo Free Pascal)

Pavel Töpfer, 2015


6

Řešte soustavu N lineárních rovnic o M neznámých. Spočítejte hodnotu Ludolfova čísla s přesností na 100 desetinných míst.

Zašifrujte zadaný textový soubor zvolenou metodou. Naprogramujte jednoduchý textový editor.

Vykreslete graf zadané reálné funkce jedné reálné proměnné. Rozmístěte na šachovnici osm šachových dam tak, aby se žádné dvě navzájem neohrožovaly.

Určete všechny způsoby, jimiž lze zaplatit zadanou částku pomocí známé sady platidel. Nalezněte v bludišti nejkratší cestu z daného místa ven. Pavel Töpfer, 2015


7

P.Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vydání 2007 (190,- Kč) učebnice přímo určená pro tento základní kurz programování, pokrývá většinu učiva algoritmů v obou semestrech (nevykládá syntaxi programovacího jazyka) P.Satrapa: Pascal pro zelenáče, Neocortex Praha 2000-2005 nebo jiná učebnice Pascalu J.Drózd, R.Kryl: Začínáme s programováním, GRADA Praha 1992 učebnice základů Pascalu a programování, vhodná pro začátečníky, nepokrývá celé učivo (nedostupná) P.Töpfer: Základy programování v úlohách, Scientia Praha 1997 učebnice základů programování, předváděny formou řešených příkladů, určena pro úplné začátečníky (první třetina ZS) P.Töpfer, D.Töpferová: Programování - Sbírka úloh, Fortuna 1998 sbírka jednoduchých i těžších úloh na procvičování P.Töpfer: Programování - Rekurze, Fortuna Praha 1998 výklad nejobtížnější partie v ZS - rekurze Pavel Töpfer, 2015


8

Vývoj programu 1. algoritmus programovací jazyk 2. program textový editor 3. zdrojový text programu překladač 4.a) syntaktická chyba zpět na opravu zdrojového textu 4.b) bez syntaktických chyb  přeložený program spustit se vstupními daty 5.a) běhová chyba (příp. zacyklení výpočtu) ladicí prostředky, testování, zpět na opravu zdrojového textu 5.b) bez běhové chyby posouzení výsledků 6.a) podezřelé výsledky  logická chyba ladicí prostředky, testování, zpět na opravu zdrojového textu 6.b) dobré výsledky ověřit správnost opakovaně pro různá testovací vstupní data Pavel Töpfer, 2015


9

Největší společný dělitel X, Y – dvě kladná celá čísla  určit největší společný dělitel NSD(X,Y) Algoritmy: 1. NSD(X,Y) = největší z celých čísel od 1 do X (X < Y), které je dělitelem obou čísel X a Y – postupně zkoušet, nejlépe v pořadí od X k 1 do nalezení prvního takového společného dělitele 2. Určit prvočíselné rozklady čísel X a Y – jejich maximální společná část určuje NSD(X,Y) Např. 396 = 2.2.3.3.11, 324 = 2.2.3.3.3.3  NSD(396, 324) = 2.2.3.3 = 36

Pavel Töpfer, 2015


10

3. Eukleidův algoritmus Idea:

když X < Y když X > Y když X = Y

NSD(X,Y) = NSD(X,Y-X) NSD(X,Y) = NSD(X-Y,Y) NSD(X,Y) = X

Příklad: NSD(396,324) = NSD(72,324) = NSD(72,252) = NSD(72,180) = NSD(72,108) = NSD(72,36) = NSD(36,36) = 36 Algoritmus: dokud X  Y dělej od většího z čísel X, Y odečti menší z čísel X, Y

Pavel Töpfer, 2015


11

Správnost Eukleidova algoritmu 1. Konečnost - na začátku výpočtu i stále v jeho průběhu je X>0, Y>0 - v každém kroku výpočtu se hodnota X+Y sníží alespoň o 1  nejpozději po X+Y krocích výpočet skončí, je tedy konečný 2. Parciální (částečná) správnost - pro X = Y zjevně platí NSD(X,Y) = X - ukážeme, že pro X > Y platí NSD(X,Y) = NSD(X-Y,Y): Nechť N=NSD(X,Y), tedy N dělí X a zároveň N dělí Y. Proto také N dělí X-Y a je tedy N společným dělitelem X-Y a Y. Pokud by neplatilo, že N=NSD(X-Y,Y), musí existovat A>1 tak, že N.A=NSD(X-Y,Y). Tedy N.A dělí X-Y i Y, takže N.A dělí i jejich součet, což je X. Jelikož N.A dělí Y a zároveň N.A dělí X, je N.A společným dělitelem X, Y, což je spor s tím, že N=NSD(X,Y). Proto N=NSD(X-Y,Y). Pavel Töpfer, 2015


12

Efektivita algoritmu (složitost algoritmu) - časová počet vykonaných operací  rychlost výpočtu programu - prostorová (paměťová) velikost datových struktur využívaných algoritmem  paměť potřebná na uložení dat při výpočtu programu Kritéria pro hodnocení kvality algoritmu a programu (příp. praktické použitelnosti programu). Obě kritéria mohou mířit proti sobě (nelze najednou optimalizovat paměť i čas), musíme zvolit, čemu dáme přednost (dnes obvykle čas).

Funkce vyjadřující počet vykonaných operací (resp. velikost potřebné paměti) v závislosti na velikosti vstupních dat. Jako velikost vstupních dat obvykle stačí uvažovat např. počet zpracovaných čísel, nikoliv konkrétní hodnoty (jedná-li se o hodnoty „standardní“ velikosti). Obecně by se musela uvažovat velikost vstupních dat v bitech. Pavel Töpfer, 2015


13

Funkce časové a prostorové složitosti jsou většinou rostoucí (nad většími daty bývá výpočet delší). Přesné vyjádření funkce časové složitosti (např. 3.N 2 + 2.N – 4) je jednak obtížné, jednak většinou zbytečné. Podstatná je řádová rychlost růstu této funkce pro rostoucí N. Zanedbáme pomaleji rostoucí členy a konstanty  asymptotická časová složitost O(N 2). Symbol „velké O“ f = O(g)   c  n0  n > n0 : f(n) < c.g(n) tzn. funkce f se dá shora odhadnout funkcí g (až na multiplikativní konstantu a pro dostatečně velká n) Opačný odhad (zdola): f = (g) Přesný odhad: f = (g)  f = O(g)  f = (g)

Pavel Töpfer, 2015


14

Asymptotická časová složitost Typické asymptotické časové složitosti algoritmů: O(1), O(log N), O(N), O(N.log N), O(N 2), O(N 3), …, O(2N) Hledáme algoritmus s co nejmenší asymptotickou časovou složitostí, tedy co nejrychlejší pro velká N. Pro malá N může být třeba i horší než nějaký jiný algoritmus, ale pro malá N to nevadí, doba výpočtu je vždy dostatečně krátká. - polynomiální – obvykle zvládnutelné i pro velká N - exponenciální – pro větší N časově nezvládnutelné, použitelné jen v případě, že vstupní data budou vždy malá

Pavel Töpfer, 2015


15

Exponenciální časová složitost Příklad: Ke zpracování vstupních dat velikosti N algoritmus vykoná 2N operací. Rychlost počítače: 109 operací za sekundu (řádově GHz – dnešní PC).

N 20 30 40 50 60 70 80 90 100

doba výpočtu 1 ms 1s 17 min 11 dní 31 let 3.104 let 3.107 let 3.1010 let 3.1013 let

Pro vyšší N (cca 50) je algoritmus prakticky nepoužitelný. Nepomůže nám ani rychlejší počítač! Pavel Töpfer, 2015


16

Složitost algoritmu v různých případech Pro každá vstupní data velikosti N nemusí trvat výpočet stejně dlouho, rozdíl může být jen v konstantě, nebo i v asymptotické složitosti Časová složitost algoritmu v nejhorším případě = maximální počet operací vykonaných algoritmem pro nějaká data velikosti N  nejčastěji používaná pro hodnocení algoritmů Časová složitost algoritmu v nejlepším případě = minimální počet operací vykonaných algoritmem pro nějaká data velikosti N  prakticky se nepoužívá

Časová složitost algoritmu v průměrném případě = průměrný (očekávaný) počet operací vykonaných algoritmem pro data velikosti N (průměr pro všechna možná vstupní data velikosti N)  dobře charakterizuje kvalitu algoritmu, ale je obtížné odvodit ji Pavel Töpfer, 2015


17

Složitost problému - složitost nejlepšího algoritmu (z hlediska časové složitosti), kterým lze řešit daný problém Nelze odvodit ze složitosti nějakého konkrétního algoritmu ani třeba všech běžně známých algoritmů, charakterizuje problém obecně (jaký nejlepší algoritmus řešící problém může v principu existovat)  odvození je obtížné, pro řadu problémů neznáme. Příklady: 1. Nalézt maximum z daných N čísel  časová složitost problému O(N) - existuje algoritmus s časovou složitostí O(N) … triviální - nemůže existovat algoritmus s lepší časovou složitostí … maximem může být kterékoliv z N čísel, takže na každé se musí algoritmus podívat 2. Seřadit daných N čísel podle velikosti (problém třídění)  časová složitost problému O(N. log N) - existuje algoritmus s časovou složitostí O(N. log N) … např. heapsort - nemůže existovat algoritmus s lepší časovou složitostí … oboje si ukážeme později Pavel Töpfer, 2015


18

Vyhledávání

1. sekvenční průchod daty velikosti N  časová složitost O(N)

2. půlení intervalů (binární vyhledávání) - data musí být uspořádaná - vždy porovnat hledanou hodnotu s prostředním prvkem zkoumaného úseku, polovinu úseku „zahodit“ - postupně dostáváme úseky délky N, N/2, N/4, N/8, …, 1 - po K krocích zbývá úsek velikosti N/2K , hledáme K takové, aby N/2K = 1  počet půlení K = log2N , tedy časová složitost algoritmu O(log N) Příklad: pražský telefonní seznam bytových stanic - cca 430 000 jmen (bylo v roce 1995) - rychlost hledajícího člověka 1 jméno za sekundu - sekvenční hledání: 5 dní a nocí x binární hledání: 20 sekund Pavel Töpfer, 2015


19

Třídění dat (řazení) – seřadit N údajů podle velikosti - přímé metody (např. „přímý výběr“ = opakovaný výběr minima)  časová složitost O(N 2) - lepší algoritmy (např. „turnaj“ v binárním stromu)  časová složitost O(N. log N) Příklad: rychlost výpočtu 1 porovnání dat za 1 mikrosekundu

N 100 100 000

algoritmus O(N 2) 0.01 s 2.8 hod

algoritmus O(N. log N) 0.6 ms 1.7 s

Závěr: - pro malá N není rozdíl doby výpočtu podstatný - pro hodně velká N může být zajímavý, i když O(N 2) je vcelku příznivá složitost algoritmu Pavel Töpfer, 2015


20

2 Z, Zk

Recommend Documents