Kolegové a kolegyně, zde najdete informace o přednášce Programování 2.

Podmínky získání zápočtu stanoví jednotliví cvičící. Minimální podmínky, které by měly být vyžadovány všemi cvičícími, jsou:

• Odevzdání zápočtového programu (včetně dokumentace),
• aktivní účast (měřená počtem bodů v CodExu).

Na přednáškách bylo probráno toto:

• 23. února:
  Organizační informace, třídění (zopakování algoritmů ze zimy, quicksort, heapsort). Slidy.
• 1. března:
  Složitost problému třídění porovnáním (dolní a horní odhad složitosti), rozhodovací strom a jeho využití k důkazu dolního odhadu. Bucketsort, Mergesort, stručná poznámka o třídění na vnějších pamětech. Paměť počítače a její organizace, pojem pointeru (alias ukazatele), operátor stříšky a zavináče. Slidy.
• 8. března:
  Práce s pamětí, reprezentace datových typů v paměti (pojem endianity), alokace, dealokace, pointer-aliasing (a jeho důsledky pro alokaci/dealokaci), motivace spojových seznamů, implementace zásobníku potenciálně neomezené velikosti (jednoduchým spojovým seznamem; spojové seznamy s typologií budou příště). Slidy. Priklad usporadaneho spojoveho seznamu.
• 15. brezna:
  Typologie spojovych seznamu, definice stromovych datovych struktur. Slidy (po slide 10, po slide 15 jsme se dostali na pristi prednasce).
• 22. brezna:
  Operace s binarnim vyhledavacim stromem, AVL-stromy, poznamka o cerveno-cernych stromech, A-B-stromy, B-stromy, A-sort. Slidy (po slide 28).
• 29. brezna:
  Ridke matice a polynomy, udrzba pameti svepomoci, hashovani (viz slidy minule prednasky). Aritmeticke vyrazy a notace. Slidy.
• 5. dubna:
  Dynamicke programovani poprve (postup od rekurze pres rekurzi s cachi k vyplneni tabulky bez rekurze). Fibonacciho cisla (Prednasejici jde do poslucharny), Catalanova cisla (pocet platnych zavorkovani), rozklad na soucty, Pascaluv trojuhelnik, nejdelsi rostouci podposloupnost. Slidy.
• 12. dubna:
  Dynamicke programovani podruhe. Zavorkovani matic, problem batohu pro celociselne vstupy a takovou kapacitu batohu, aby s ni slo indexovat pole. Zacali jsme mluvit o grafovych algoritmech (reprezentace grafu, prohledani do hloubky a sirky, faktorova mnozina, topologicke usporadani). Slidy.
• 19. dubna:
  Dokonceni grafovych algoritmu. Dijkstruv algoritmus (s dukazem korektnosti), Bellman-Forduv algoritmus, Floyd-Warshalluv algoritmus (vse na hledani nejkratsich cest), Kruskaluv algoritmus (s dukazem korektnosti), zminka o Jarnikovu algoritmu.
• 26. dubna:
  Posledni poznamky ke grafovym algoritmum, median linearne, odstraneni rekurze, Quicksort s logaritmickou prostorovou slozitosti (mimo velikost vstupnich dat), binarni soubory, predani funkce v parametru. Pozor, ve slidech je udaj o Stredniku (alespon zatim) spatne, tento semestr dost mozna Strednik nebude! Slidy.
• 3. kvetna:
  Hry (1. cast). Definice kombinatoricke hry, priklady her, veta o existenci neprohravajici strategie, graf hry, strom hry, AND-OR-strom, hry s ohodnocenim, hry s nulovym souctem, Minimax, Negamax. Slidy. (skoncili jsme kolem slidu 31).
• 10. kvetna:
  Dokonceni her (staticka ohodnocovaci funkce, horizont, heuristiky dvou druhu - alfa-beta-prorezavani, maticove hry a poznamky o minimaxovych vetach), zaznam s variantami (variantni record).
• 17. kvetna:
  Objektove programovani 1. cast (pojednani o tridach a objektech, atributy, metody, klicova slova public a private, dedicnost). Slidy. Pozor na matouci poznamku o Stredniku, ten letos v lete nebyl a zrejme jiz nebude).
• 24. kvetna:
  Dokonceni objektoveho programovani (virtualni funkce, ciste virtualni funkce, abstraktni tridy, typeof, klicove slovo self). Slidy. Zaver prednasky Programovani.

HGW XX/7 15:15

Podrobne pozadavky ke zkousce (jsou uz radu let stejne).