Co bylo na minulých přednáškách z NPRG030/NPRG031 Programování I/II v roce 2016/17 ================================================================================== 25.5.2017: Řešení těžkých úloh: * Motivační úloha: páková baterie * nakreslení grafu - ...řešte jinou úlohu * hádání obrázku - ...zapojte přirozený výběr - genetické algoritmy, fitness, selekce, křížení, mutace - význam mutace * broučci BROUCCI2.PAS * broučci s pamětí BROUCCI.DPR - cil = zjistit výhodu paměti, - jak měřit – měřící bludiště - výsledky pro 1 a pro 3 stavy * broučci BCY * historka o magnetofonu - ...podívejte se z odstupu - nonius - VASI * OCR - ...hledejte řešení v určitém tvaru - větší počet bodů //a odolnost proti chybě * vodovodní baterie - řešení 18.05.2017: * ještě k vláknům: - race condition - thread safety !! - Random NENI thread-safe - zamykání: - lock - deadlock * "zkouškový" příklad - úloha počet způsobů přehnutí papíru * Hygiena programování: 1. oddělovat činnosti 1. analýza 2. design 3. GUI design 4. (hledání algoritmu) kódování 5. grafika/zvuky/texty 6. testování 7. dokumentace = ODDĚLOVAT !! Neodbočovat při řešení problému! - resources 2. pracovní deník - důležitý už kvůli psaní - rozhodnout se, co budu dělat teď - = gumová kačenka - evidovat časy (a učit se odhadovat) - záznam PROČ 3. správa versí CVS, SVN, GiT, Hg… - github 4. bug-list – bug tracking system 5. testy a test-driven programming - psát volání funkce dříve než funkci - assert - testy – TEST a počítat chyby - testovací procedury – automatické testy, ladění proti testům, testy výkonnosti, regresní testy - Ntest - asserty * String vs. StringBuilder 11.05.2017: * ještě k hashování - změna hashovací funkce - class Dictionary * "zkouškový" příklad - odpověď = analýza (a design): 0) upřesnění zadání 1) postřehy 2) zdůvodněná volba algoritmu (složitost atd.) 3) representace dat 4) dekomposice - rozklad řešení na části 5) diskuse * příklad příkladu: úloha ANKETA - zadání - kroky - data-flow diagram - celková složitost - možné paralelní provádění některých kroků * delegáty jako proměnná jako parametr funkce: +=, -= anonymní funkce * vlakna v C#: - Thread, t.Start - počet jader - kdy použít vlákno (aby nezamrzlo GUI) 04.05.2017: * Grafy: - representace: - matice sousednosti - matice vzdáleností - seznam hran - matice incidence - seznam následníků - trik se seznamem seznamů (jedno pole následníků a indexy) - = volit reprezentaci podle toho, jaké operace budeme provádět. * úlohy a algoritmy: * nejkratší vzdálenost (z A do B, z A do všech) - Dijkstrův algoritmus - předpoklady: nezáporně ohodnocený, souvislý - trvale a dočasně ohodnocené vrcholy - inicializace - krok - jakou reprezentaci použít (seznam následníků) - složitost O(|V|2+|E|) resp. - Floyd-Warshall (ze všech do všech) - předpoklady: ne záporné cykly - algoritmus, dynamické programování - jakou reprezentaci použít (matici vzdáleností) * minimální kostra - co je to - Kruskalův („hladový“) algoritmus (min. ze všech nepoužitých hran nevytvářejících cyklus) * topologické uspořádání (už jsem ukazoval): - test acykličnosti - jakou reprezentaci použít (seznam následníků) //- nejdelší cesta * Hashování - ukázka, jak si naprogramovat sám a jak záleží na hashovací funkci - program generující náhodná slova //- vliv hashovací funkce // i způsobu hledání náhradní pozice (lineární, kvadratický) 27.04.2017: * Ad Výjimky: diskuse o vhodnosti používání výjimek * Programování pomocí testů - Příklad: funkce na určení podílu dvou čísel zadaných ve stringu - Testování – vstup ručně, kontrola očima = pracné, pomalé, nespolehlivé - Nahradit zadávání vstupu kódem - Nahradit kontrolu výsledků kódem - Funkce na otestování jednoho volání - Očekávaný výsledek - Funkce na otestování jednoho volání - Funkce na otestování funkce - Počítání chyb - Porovnání jednoho výsledku - Přidávání testů (protože je to snadné) - Rozhodnutí,jak zacházet s chybami – výjimky nebo chybové kódy - Změna hlavičky funkce - Vracet chybový kód i výsledek – výsledek vs. var/out-parametry - unit-testy ve Visual Studiu - projet a solution, References * Pošta jako ukázka „těžkého příkladu“ - návrh programu pro kontrolu řešení 20.04.2017: * dynamické programování: Floydův–Warshallův algoritmus * C#: výjimky - přístup k chybám: testování PŘEDEMpředem vs. řešení POTOM - try-catch, catch(typVyjimky1 identifikator) - hierarchie, Exception, .Message, .StackTrace - throw - finally - vnořování chráněných bloků //- výjimky vs. chybové kódy, neviditelné GOTO * C#: aplikace s více okny: - dalsi okno - hlavni okno - show: Show() - dialog: ShowDialog(); - button.DialogResult - kontrola spravnosti: událost FormClosing: E.Cancel = true; - dosazení/čtení hodnot z komponent: property / modifier - Form.AcceptButton - Dispose okna po Show() a Close() => odchytit FormClosing, test Modal, abort a Hide(). * výstup pomocí šablon - System.Diagnostics.Process.Start(…); 13.04.2017: * Grafika v C# (WinForms) * Graphics - Získání - this.CreateGraphics() * Pen - Pens (properties) - New Pen * Color - Připravené (properties) * Pero – caps * PictureBox * Bitmap * Brush - Brushes (properties) - new SolidBrush * Color - FromARGB, RGB = vypočítaná barva * Bitmap.GetPixel, SetPixel - kopie - Zmena souradnic - Preklopeni x,y - Zvetseni - deformace - barevna slozka - světlost – převod na šedou - prah - Distribuce chyby - změna jasu a kontrastu //- reliéf * DrawString - Font 6.04.2017: * dynamické programování - příklad: Optimální uzávorkování násobení matic - složitost - příklad: Počet různých her odebírání zápalek pro daný počáteční počet - příklad: Nákupní vycházka po NYC * optimální vyhledávací strom - a jeho hledání dynamickým programováním * C#: aplikace s více okny (zacatek): - dalsi okno - hlavni okno - show: Show() 30.03.2017: * dynamické programování - příklad: editační vzdálenost a nejdelší společný podřetězec - lehčí příklad: 6 dětí do 3 skupin - řešení rozborem případů - ještě lehčí příklad: mrkev a petržel 10 záhonů - rekurentní vzorce - skládání řešení z řešení menších úloh stejného typu - části optimálního řešení jsou optimální řešení pod-úloh - výměna paměti za čas - příklad: Počet různých cest v orientovaném acyklickém grafu - algoritmus topologického uspořádání - příklad: nejdelší společný podřetězec - příklad: počet BVS o 6 vrcholech - snadná cesta: backtracking s ukládáním parametrů a výsledků 16.03.2017: Programování řízené událostmi (Event-driven programming) * programování řízené událostmi - princip * události – klávesnice, myš * jak probíhá zpracování události - hierarchie - polymorfismus * Visual Studio: - Designer, ToolBox, Property editor * Druhy properties - Oddělení designu a funkčního kódu * Syntaxe: partial class * Vytvoření obslužné procedury via propertie a via dbl-click - MessageBox * Sdílení obslužných metod - Sender - Přetypování - Is - Kalkulačka //* Timer // - Hodiny 13.03.2017: C#, .NET: * generické funkce, generické třídy, List * System.IO.StreamReader, System.IO.StreamWriter Diskrétní simulace: * Cílem zpravidla není jeden konkrétní případ, ale sledovat chování systému * Cílem NENÍ optimalizovat, jen odpovídat na otázku, jak by to dopadlo * V čem se bude lišit jiný model: - Procesy - Události - …a reakce na ně * Návrh modelu – obchodní dům * Procesy * Události * Stavový diagram - Kdo vyvolá změnu stavu - Jaké akce se při ní mají provést * => Popis, který je výsledkem (důležitější než program) http://ksvi.mff.cuni.cz/~holan/pas/obchod.txt http://ksvi.mff.cuni.cz/~holan/pas/obchod_data.txt 09.03.2017: Diskrétní simulace: * úloha s hromadou písku * Model - Zjednodušený, jen některé atributy - I rovnice je model - Co modelovat a co zanedbat - Co modelovat jak * Simulace spojitá vs. diskrétní Program: - TypUdalosti - C# enum - Udalost - Kalendar - Auto - Model * Písek v A, Písek v B * Čas * Fronta v A * Pouziti simulace pro zkoumani variant a OOP-zmena pomoci odvozene tridy = Model2 pro ruzny pocet aut = Model3 pro ruzny pocet aut a nakladacu 02.03.2017: * objekty - konstruktor - dědičnost - virtuální metody - polymorfismus - abstraktní třída, abstraktní metoda - staticke promenne a funkce (Console, Math) * namespaces - using * cteni vstupu - Console.ReadLine() - int.Parse() - Console.Read() - Int vs char - vlastni trida na cteni 23.02.2017: * Zápočty – program, zápočtový test * zkouška – písemka, ústní, jaká písemka * obsah – další algoritmy, meta-algoritmy * slajdy a zdrojové texty – na webu * jazyk – C#, MS Visual Studio - nový jazyk, ale známé konstrukce * objekty a OOP: - způsob uvažování o částech programu - CO x JAK - Historie (Simula 67, Smaltalk, OOP boom 90-tých let) - spojení dat a funkcí - zapouzdření – ukrývání vnitřku, díky tomu konsistentní stav - vzor x instance: třída x objekt //- příklad: komplexní čísla - příklad s tiskem slov na řádky dané šířky * C# a Microsoft Visual Studio - 1995 Java, bytecode - 2002 C#, .NET - Anders Hejlsberg - Nascom microcomputer: Blue Label Software Pascal -> PolyPascal -> Turbo Pascal - 1989 Borland - Borland Delphi chief architect - 1996 Microsoft - J++ - 2000- C# lead architect - program = sbírka objektů - metoda Main() - žádné "globální" metody ani proměnné, všechno patří nějaké třídě // - sin – Math – instance? // => static metody - syntaxe jazyka C# - rozdíly C# proti Pascalu 10. 1. 2017: * Vnější třídění - Základní operace: slučování (merge) - dvoufázové dvoucestné přirozené slučování - vylepšení: - jednofázové - vícecestné - předtřídění - obyčejně - pomocí haldy - pomocí dvou hald * Zbytky... - set of … - funkce jako parametry - proměnné pro funkce a jiné ošklivosti. - CHYBA - soubory - append - proměnná FileMode - Mark & Release - case Příklady - Lloydova šestka – co potřebujeme a jak to vyřešíme - Znaménka do 1 2 3 4 5 6 7 8 9 3. 1. 2017: * datové struktury - abstraktní typ, rozhraní - jak zatím umíme representovat seznam - stromy! * BVS - definice - vyhledání - přidání * příklad rekurse: tisk BVS * BVS - vymazání * Vyvážené stromy - Dokonale - AVL - Definice - logaritmická výška - Vyvažování – rotace - Kolikrát vyvažovat - B-stromy - Definice - operace * Odstraňování rekurse - nahradit iterací (k-té Fibbonacciho číslo) - jiný algoritmus (sčítat dvě předchozí) - vlastním zásobníkem - Ad QS: velikost zásobníku * perličky BP: - absolute, Mem - tick: longint absolute $0:$046c; { 18.2/sec } 20. 12. 2016: * vnitřní třídění (řazení, sorting) - složitost zvlášť v počtu porovnání a zvlášť v počtu přesunů - přímý výběr (selection sort) - přímé vkládání (insertion sort) - bublinkové třídění (bubble sort) - třídění přetřásáním (shake sort) - meze nesetříděné části - Shellovo třídění - stromové třídění - HeapSort - halda, definice - representace haldy v poli (obecně jakéhokoliv binárního stromu) - oprava po odebrání kořene - procedura VytvorHaldu(zac,kon) - postavení haldy - v lineárním čase - třídění sléváním (merge sort) - myšlenka - složitost - paměť - O(N), (lze pole indexů) - QuickSort - myšlenka - program - proč (ostré nerovnosti, neostrá nerovnost...) - složitost v nejhorším a průměrném případě - volba pivota - zásobník - QuicSort NETŘÍDÍ na místě ("in situ") * hledání k-tého prvku - postupným vybíráním - setříděním - QuickSort-like lineární algoritmus * pojem složitost úlohy - složitost úlohy vnitřního třídění založeného na porovnání dvou prvků - přihrádkové třídění (bucket sort) - ...s více průchody (radix sort) 13. 12. 2016: * HRY: - příklad odebírání zápalek - příklad řada čísel = konečné hry s úplnou informací - rekurentní definice prohrávající a vyhrávající pozice (kdyby neexistovala remíza) - strom hry //(nemusí být strom) - konečný počet sehrávek, u každé známý výsledek - důsledek: existence neprohrávající strategie - rekurentní definice -->> rekurzivní funkce - problém výpočtu: rychlost/pomalost - řešení problému: cache (ukládat již spočítané výsledky/ohodnocení stavů) - hry s ohodnocením: - hry s nulovým součtem //(- hry s nenulovým součtem - Vězňovo dilema) - algoritmus Minimax - příklad: odebírání z řady čísel - počítání směrem dolů - počítání směrem nahoru - negamax - opravdové hry: - příliš veliké - alfa-beta prořezávání - počítání do omezené hloubky a nahrazení statickou ohodnocovací funkcí - kaskádová metoda (čím dál větší hloubka) - okénko - příklad BP/CHESS - HEURISTIKA: - záleží na pořadí prohledávání (ale jen rychlost) - širší a užší význam - příklad heuristiky: - loupežníci - proskákat šachovnici koněm - nejdříve políčka s nejmenším počtem sousedů * Urychlení backtrackingu (prohledávání do hloubky) - ukládáním výsledků = viz výše - prořezávání * Obecně backtracking: umím vrátit krok nebo si pamatovat stav * N dam na šachovnici - hloupě (umisťovat dámu do šachovnice) - lépe (umisťovat dámu do sloupce) - nejlépe (obsazovat řádky a diagonály) 06. 12. 2016: * Dlouhá čísla motivace: spočítat e na 1000 míst * representace - nezáporná x i záporná - se znaménkem x doplněk - celá x desetinná - pevná x pohyblivá řádová čárka - pole x spojový seznam - odpředu x odzadu - obsah jednoho prvku - délka - kolik míst navíc - spočítat a ještě zkusit * příklad e (Leonhard Paul Euler 1707-1783) - odhad počtu kroků - potřebné operace - dosazení - sčítání - dělení integerem - přeskočení nul - test konce * odčítání - doplňkový kód * násobení * dělení… * postupné testování vytvářených funkcí („ladění zdola“) * Aritmetické notace (z minulé přednášky): ...vyhodnocení v různých notacích" - vyhodnocení POSTFIXu pomocí zásobníku - vyhodnocení PREFIXu rekursí - BYLO: vyhodnocení INFIXu rozkladem na podvýrazy - vyhodnocení INFIXu podle gramatiky ( = O(n) ) - předběžná deklarace forward * vytvoření stromu z různých notací * převody mezi notacemi (vytvořit strom a vypsat) * prohledávání do hloubky pomocí rekurze - proskákání šahcovnice koněm 29. 11. 2016: * Rekurse Příklady: - vyhodnocení výrazu (v infixové notaci) rozkladem na podvýrazy - permutace - variace - kombinace - Loupežníci / Batoh * abstraktní datový typ. Rozhraní (interface) - seznam, fronta, zásobník - Obecný algoritmus hledání. - Prohledávání do šířky (vlna) a do hloubky (backtracking) - realizace zásobníku a fronty v poli, cyklická fronta. - realizace zásobníku a fronty pomocí spojových seznamů (kam přidávat, odkud ubírat). * Ad spojové seznamy – vytvoření pomocí funkce * složitější dynamické struktury – stromy - vytvoření stromu funkcí (jako vytvoření seznamu) - vyhodnocení výrazu - výpis – průchod – notace PREFIX, INFIX, POSTFIX 22. 11. 2016: * dispose * halda a správce haldy - vrchol a seznam děr (Q: jak implementovat?) * jednosměrný lineární spojový seznam - projití všech prvků - přidávání prvků na začátek a na konec - ...a s ukazatelem na konec - mazání prvků ze začátku - ...a z konce * Kreslit si obrázky! * NIL a vsuvka o tabulce přerušení //* vytvoření seznamu pomocí funkce * Ad spojové seznamy – postup: - Přidání x do setříděného seznamu - Jak vypadá běžná situace - Jaké výjimečné situace musíme ošetřit - Prázdný seznam - Všechny prvky jsou větší (neexistuje předchůdce) - Všechny prvky jsou menší (neexistuje následník) - ...a běžná situace * Ad výjimečné situace a potíže spojových seznamů: - Předchůdce => obousměrný seznam - Prázdný seznam => hlava - Poslední prvek => cyklický seznam // * Spojové seznamy a vyhledávání se zarážkou – NYL * Rekurse - Co to je - Faktoriál - Klady a zápory - Odstrašující příklad: Fibonacci //* Náprava ukládáním výsledků * BP: Call stack * Příklady: - Hanojské věže - Vypsání všech kombinací 15. 11. 2016: * příklad přetečení pole do ostatních proměnných * příklad řešení úlohy pomocí podprogramů - dvacet nejčastějších slov ze souboru * record * dynamické proměnné - motivace - proměnné vyráběné podle potřeby za běhu programu, rekursivní data - implementace - ukazatele - NIL //- vsuvka o tabulce přerušení - new - dispose * jednosměrný lineární spojový seznam - projití všech prvků - přidávání prvků na začátek 01. 11. 2016: Nepořádně: * pole – proč (uložit víc hodnot, přístup k prvku určenému programem) - použití a deklarace - načtení, uložení, vypsání v opačném pořadí... Pořádně: * ordinální typy, výčtové typy, interval * pole pořádně - příklad: kódování - příklad: četnosti znaků => deklarace typu – type * for-cyklus - continue, break - dosazení do řídící proměnné (nedělat!) * vyhledávání v poli - lineárně - pomocí zarážky * typované konstanty v BP * znakové řetězce - ukončovací znak x délka - typ string //- řetězení - copy, pos * Rozmyslet: program, který vytiskne sám sebe * podprogramy: - motivace: - dělení programu na části (pro rozdělení, hledání i dělbu práce) - zabránění opakování - příklad Násobilka - procedury vs. funkce - parametry pořádně: * blok – const, type, var * konstanty * podprogramy - blok, procedura-funkce-program - lokální symboly, viditelnost identifikátorů - formální a skutečné parametry * předávání parametrů podprogramům: - hodnotou - odkazem //- konstantní parametry * kdy jsou proměnné stejného typu… a proč nelze definovat ppgm s parametrem array[] 18. 10. 2016: * příklady úloh a jejich složitost - vyhledávání v krabici s účtenkami - vyhledávání v telefonním seznamu * typ boolean * zkrácené vyhodnocování = Př: číst čísla dokud není -1 nebo sqrt(x)=2 * PGM monotonie * typ char - požadavky na kódování číslic a písmen - hodnota znaku - Hornerovo schema * PGM načítání čísla * textové soubory - pojem - standardní vstup, standardní výstup - přesměrování vstupu a výstupu - oddělovač řádek, ukončovač souboru - příkaz read - příkaz write * Eof-EoLn x SeekEoLn (přeskočí whitespaces) a SeekEof (nic kromě whitespaces) * POZOR na eof v Win x Linux!! (CodEx) - typ text v BP (assign, reset/rewrite, close) - proč zavírat soubory = příklad * direktivy kompilátoru - {$I-}, IOResult 11. 10. 2016: * Příklad: nalezení maximální hodnoty z posloupnosti čísel ukončené -1 - 1) přečtení - volba cyklu while/repeat-until - 2) výstup - invariant - a) nastavení na začátku b) udržení v cyklu * čísla v počítači * (přesná a nepřesná) => integer a real * typ integer - operátory, priority, funkce - representace v paměti - doplňkový kód * typ real, operátory, funkce, problémy s porovnáním * složitost algoritmů - pojem, k čemu - složitost jako funkce velikosti vstupních dat - časová, paměťová, přelévání mezi nimi - v nejhorším, v průměrném případě - asymptotická složitost, O() - příklady a jejich složitosti - algoritmus vlny a výměna paměti za čas - test prvočíselnosti - umocňování na N-tou – rychlý algoritmus 4.10.2016: * o čem to bude * pokus o vymezení pojmů programování, program, algoritmus * algoritmy: - sčítání dvou čísel v desítkové soustavě - Euklidův - nejkratší cesta koněm na šachovnici - algoritmus vlny - hledání v bludišti - backtracing * typické vlastnosti algoritmu * dokazování správnosti algoritmu - korektnost - částečná správnost - invariant - priklad s lamanim cokolady - konečnost - metoda s ohodnocením stavů výpočtu * formalizovaný zápis algoritmů - pojem proměnné, typ - přiřazovací příkaz, příkazy vstupu a výstupu - řízení běhu programu - pomocí skoku - strukturované programování - podmíněný příkaz - složený příkaz - cykly while a repeat-until * příklady: - vypsat větší ze dvou čísel zadaných jako vstup - vypsat největší ze tří čísel zadaných jako vstup