PRG031 Programování II

Co bylo na přednáškách

středa 14:00 S3

1. přednáška 23.února
2. přednáška 2.března
3. přednáška 9.březnaa
4. přednáška 16.března
5. přednáška 23.března
6. přednáška 30.března
7. přednáška 6.dubna
8. přednáška 13.dubna
9. přednáška 20.dubna
10. přednáška 27.dubna
11. přednáška 4.května
11.května rektorský a děkanský den
12. přednáška 18.května
13. přednáška 25.května

1. přednáška 23.února
   • Náplň letního semestru
   • Pascal a C
   • Poznámky k testům a zkouškám
   • Návrh vstupních a výstupních dat, metody ladění, hlavní program a podprogramy
   • Funkční gramotnost jako jeden z předpokladů přežití v naší (postmoderní) společnosti - o matfyzu nemluvě
   • Datové soubory a práce s nimi
   • Vnější třídění - charakteristika úlohy. Oprávněnost omezení se na skvenční přístup k souborům. Počet přístupů na disk je vhodnou mírou složitosti pro porovnávání algoritmů vnějšího třídění.
   • Definice běhu, myšlenka algoritmu přirozeného slučování
   • Datový typ stream, který umožňuje testovat, co "příště přečtu".
     Programová jednotka obsahující podprogramy pro práci se streamy (otevření, kopie prvku, kopie běhu, slévaní běhů atd. )
   • Implementace algoritmu přirozeného slučování pomocí streamů
   • Rozmyslete - algoritmus, který slévá "jednice do dvojic", ..... , 2^(n-1)-tice do 2ⁿ-tic, není motivací pro algoritmus přirozeného slévání, ale neúnosně pomalým algoritmem, jehož implentace je složitější než u algoritmu přirozeného slučování.
   • Vylepšení - bude ještě podrobněji
     • při slévání rovnou rozděluji do více souborů
     • zvětšování délky běhů (a tedy i zmenšování jejich počtu) předtříděním ve vnitřní paměti
     • použití více pásek
   Zpět začátek
2. přednáška 2.března
   • Literatura a zkouška
   • Zmenšení počtu běhů v souboru "předtříděním" ve vnitřní paměti; použití dvou heapů.
   • Idea polyfázového třídění výpočet optimálního rozdělení běhů
   • Přímý přístup k datovým souborům
   • Proč je sekvenční přístup rychlejší
   • Stromy, binární stromy - terminologie
   • Různá data se strmovou strukturou, různé datové reprezentace stromu
   • Kanonická reprezentace lesa pomocí binárního stromu
   • Průchody binárního stromu do hloubky - preorder, inoreder, postorder
     a jejich rekursivní implemenace
   Zpět začátek
3. přednáška 9.března
   • Průchody binárním stromem do hloubky a souvislost s aritmetickými notacemi
     (preorder - prefixová (polská), inorder - infixová, postorder - postfixová (inverzní polská).
   • Visualizace stromu pomocí indentace
   • Binární vyhledávací stromy a operace na nich: vyhledávání, vkládání a vypuštění prvku s daným klíčem
   • Vypouštění intervalu z binárního vyhledávacího stromu.
   • Postavení dokonale vybalancovaného binárního vyhledávacího stromu ze začátku (zadané délky) rostoucí posloupnosti
   • Vkládání do kořene binárního vyhledávacího stromu
   • Datová reprezentace binárního stromu s polem synů, aby šlo předat směr jako parametr podprogramu.
   Zpět začátek
4. přednáška 16.března
   • AVL stromy, definice, nejhorší případ - Fibonnaciho stromy, datová reprezenantace,
     jednoduchá a dvojitá rotace, algoritmus vkládání - stačí nejvýše jedna rotace, algoritmus vypouštění - je případně nutné rotovat podél celé cesty k vypouštěnému prvku.
   • Programování práce s AVL stromy
     • je výhodné definovat typy tak, abych nemusel zvlášť programovat
     • je více než rozumné přidat výstupní parametr (např. typu boolean), který říká, zda se zvýšila (při vkládání) resp. snížilia (při vypouštění) výška stromu
     • Zkuste si příslušné procedury naprogramovat !!
   • Hašování, myšlenka, hašovací funkce bez kolizí pro statické tabulky nevelké velikosti, kolize a různé metody jejich odstraňování, metoda řetízků a její modifikace, aby šlo i vypouštět.
   • Stručný vývoj metodologie programování; strojový kód, assembler, strukturované, modulární programování, abstraktní datové typy.
   • Objektové programování - úvodní povídání.
   • Motivační příklad implementace fronty neobjektové a objektové
   Zpět začátek
5. přednáška 23.března
   • Objektové programování
   • Terminologie třída (class) je typ, objekt (instance) je proměnná daného typu.
   • Zapouzdření (encapsulation).
   • Ochrana přístupu k atributům - private a public
   • Dědičnost (inheritance). Podtřída může přidat libovolné (datové nebo metody) atributy a předefinovat metody nadtřídy. Klíčové slovo inherited.
   • Ochrana přiřazovacího příkazu mezi objekty třídy a nadtřídy.
   • Motivační příklad implementace fronty neobjektové a objektové
   .
   • Polymorfismus, virtuální metody, jejich realizace pomocí tabulky virtuálních metod, role konstruktoru. Destruktor.
   • Rozšířená syntaxe procedur new a dispose s voláním konstrukroru resp. destruktoru.
   • Doporučení pro objektové programování v Pascalu
     1. Neužívejte staticky alokované objekty.
     2. Při alokaci a dealokaci dynamických objektů užívejte jen rozšířenou syntaxi new resp. dispose s voláním konstruktoru resp. destruktoru.
     3. Každá třída, jejíž objekty chcete vytvářet (není jen abstraktní), by měla mít konstruktor a destruktor (třeba zděděný nebo prázdný).
     4. Prvním příkazem konstruktoru podtřídy by mělo být zavolání konstruktoru její nadtřídy (slušnost a dobrý návyk).
   • Ilustrační příklady na virtuální metody.
   Zpět začátek
6. přednáška 30.března
   • Opakování objektového programování v Pascalu
     • Třída a objekt
     • Zapouzdření - encapsulation
     • Dědičnost - ihneritance
     • Hierarchie tříd dědičnosti lépe řeší problémy, na se dříve používaly větvený záznamy
     • Polymorfismus, virtuální metody, tabulka virtuálních metod, role konstruktoru
     • Funkce typeof a její použití, přetypování ukazatelů na objekty
     • abstraktní třídy
     • Destruktor a jeho role
   • Příklad objektové hierarchie modelující práci s dvousměrnými seznamy s hlavou - rozmyslete si
   • Příklad návrhu objektové hierarchie pro práci s geometrickými objekty - virtuální metoda draw
   Zpět začátek
7. přednáška 6.dubna
   Programové prostředí Delphi - první seznámení

   • Pascal a Delphi
   • Delphi jako "programovací editor"
   • Komponenty, vlastnosti, události
   • Návrhový mód, ladící mód, inspektor objektů, editor zdrojového textu, "textový tvar" (DFM) objektů
   • Formulář, komponenty Edit a Label
   • Komponenta Memo
   • Standardní dialogy open, save, colour
   • combo box, updown
   • časovač
   • komponenta shape, události myši
   • Name a Caption
   • Používání helpu
   • Zkuste si: pohrát si s Delphami
   Zpět začátek
8. přednáška 13.dubna
   • Hledání K-tého největšího z N prvků
     • Nalezení prvních M prvků z posloupnosti délky M*M
     • Metoda založená na vytváření hromady z N-K+2 prvků
     • Metoda založená na qiucksortu
     • Lineární algoritmus pro nalezení K-tého prvku z N prvků
   • Rozmyslete si: Nalezněte konstantu při dělení posloupnosti na pětice
   • B-stromy. Definice, algoritmy vkládání a vypouštění.
   • Opakování idei dynamického programování na příkladu hledání optimálního uzávorkování součinu matic
   • Problém batohu - vratíme se k němu
   Zpět začátek
9. přednáška 20.dubna
   • Problém batohu - polynomiální algoritmus pro problém s celočíselnými velikostmi,
     trasování algoritmu
   • Optimální vyhledávací strom, definice, hledání pomocí dynamického programování v čase O( n ³ ),
     modifikace se složitostí O( n ² )

      Delphi a jazyk Object Pascal

   • knihovny VCL a CLX
   • Objekty jsou podtřídy třídy Tobject, proměnná je odkaz na exemplář, konstruktor Create, metody Destroy a Free
   • ochrana atributů třídy: private, public, protected, published
   • Virtuální metody, předefinování v podtřídě - override
   • dynamické metody - jiná implementace "virtuálních metod"
   • abstraktní metody - lze vytvářet exempláře třídy s abstraktní metodou, ale ta se nesmí volat
   • Přetěžování metod, overloaded, reintroduced u virtuálních metod
   • Vlastnosti - properties, mapování přístupu na datovou položku resp na metodu, specifikace default
   • is - test na příslušnost objektu k třídě, přetypování - as
   • Vyjímky - co to je, handler, propagace vyjímky do nadbloku/ů
   • try blok s hanlery on ... , try blok s finally , vyvolání vyjímky raise
   k vyjímkám se ještě vrátíme
   Zpět začátek
10. přednáška 27.dubna
    Delphi

    • zpracování události propadáním k podřízeným
    • více oken:
      • vytvoření nového okna
      • zobrazení pomoci Show
      • automatické doplnění USES
      • přebirání údajů z jiného okna
      • Memo
      • typ TStrings, Add, Count, Clear, [], implicitníi vlastnost
      • modálni a nemodální zobrazeni
        • ShowModal
        • vlastnost ModalResult tlačitka a okna
        • BitBtn
        • vlastnosti Cancel, Caption, Default, Glyph, ModalResult...
          ...a vlastnost Kind, která je všechny nastaví
        • událost OnCloseQuery
    • grafika
      • Canvas
      • Pen - Width, Color, Style
      • přerušované čáry jen tloušťky 1
      • barvy, TColor, barva v sestnactkove soustave
      • Brush - Color, Style
      • barevne prechody
      • LineTo, Rectangle
      • TextOut
      • vlastnost Font
      • pozadi vlastnosti Brush
    Zpět začátek
11. přednáška 4.května
    Další algoritmy, ukázkový "zkouškový příklad"
    • O zkouškách
    • Reprezentace aritmetického výrazu pomocí stromu,
      pomocí notací prefix, postfix a infix,
      nejednoznačnost notace infix, nutnost závorek, zjednodušení pomocí priorit
    • Algoritmy vyčíslování hodnoty aritmetického výrazu zadaného stromem, postfixovou nebo prefixovou notací.
    • Algoritmy vyčíslování hodnoty aritmetického výrazu zadaného infixovou notací: zdola, zhora, rekursivní sestup (konstrukce soustavy rekursivních podprogramů pomocí graamatiky - viz první semestr), převod na postfixovou notaci.
    • Konstrukce notace ze stromu - rekursivní průchod stromem do hloubky.
    • Konstrukce stromu z notace je modifikací algoritmu vyhodnocování.
    • Převod infixu na postfix, modifikace, která počítá hodnotu.
    • Simulace diskrítní a spojitá.
    • Diskrétní simulace - kalendář událostí, plánovací procedury, simulární čas, procesní a událostní simulace.
    • Analýza řízení výtahů ve velké budově.
    • Rozmyslet: návrh konkrétního simulačního programu.
    • Příklad "zkouškového" příkladu.
    Zpět začátek
12. přednáška 18.května
    Delphi
    Zpět začátek
13. přednáška 25.května
    Zpět začátek