PRM001 Programování - úterý 15:40 K1

Co bylo na přednášce - paralelka Y

přednáška 15.října
přednáška 22.října
přednáška 29.října
přednáška 5.listopadu
přednáška 12.listopadu
přednáška 19.listopadu
přednáška 26.listopadu
přednáška 3.prosince od 14.00 v K1
přednáška 3.prosince od 15.40 v K1
přednáška 10.prosince
přednáška 7.ledna

přednáška 15.října
- Náplň a cíle předmětu, podmínky k zápočtu a zkoušce, praktický test v zimním semestru.
- Pojem algoritmu a příklady konkétních algoritmů (aritmetické operace se zápisy čísel v poziční soustavě, Eukleidův algoritmus, Erathosthenovo síto, ....).
- Správnost algoritmu, konečnost, parciální správnost.
- Algoritmus průchodu bludištem s pamatováním si přímé cesty zpět (příště bude dokázána jeho správnost)
zpět na začátek
přednáška 22.října
- Důkaz správnosti algoritmu průchodu bludištěm. Pojem invariantu.
- Důkaz, že algoritmus "pánské volenky" vytváří stabilní párování (dokonce v silném smyslu optimální pro muže).
- Časová složitost algoritmu. Asymptotická složitost. Nejhorší, nejlepší a průměrný případ. Proč má "teoretická" asymptotická složitost praktický význam.
- Úlohy k rozmyšlení :
  - Co nejlepší algoritmus pro nalezení maximálního obdélníka ze samých jedniček v daném obdélníku obsahujícím jen jedničky a nuly.
zpět na začátek
přednáška 29.října
- Algoritmus, který nalezne v čase m*m*n maximální obdélník ze samých jedniček v daném obdélníku rozměrů m krát n obsahujícím jen jedničky a nuly.
  Úkol: Zkusit najít algoritmus se složitostí m*n .
- Motivační příklad pro potřebu zavedení složených příkazů.
- Proměnná, identifikátor, mnemotechnické identifikátoty, deklarace proměnných, přiřazovací příkaz, klíčová slova.
- Složený příkaz, úplný a neúplný podminěný příkaz, cykly repeat a while.
- Čísla ve světě, v matematice a v programování. Exponenciální růst.
- Čísla typu integer. Maxint, synaxe zápisu konstant, operace a standardní fukce. Příklad neasociativity sčítání integerů.
  Celočíselné typy v Borland Pascalu : integer, shortint, longint, byte, word.
zpět na začátek
přednáška 5.listopadu
- Syntaktické diagramy jako prostředek pro popis syntaxe jazyka.
- Odstranění nejednoznačnosti konstrukce
  if P then if Q then S1 else S2
- Typ real : operace, standardní funkce, funkce trunc a round.
- Zaokrouhlovací chyby.
- Zásady pro vyčíslování výrazů.
- Typ boolean.
- Program, který testuje, zda číslo na vstupu je prvočíslo.
- Typ char, funkce ord a chr.
zpět na začátek
přednáška 12.listopadu
- Poziční soustavy. Vyčíslení hodnoty zápisu čísel v poziční soustavě o základu K (2<=K<=16) Hornerovým schématem (program).
  Příklad použití readln, writeln, eof bez přesné specifikace obecného významu.
- Konstanty a jejich význam pro snazší modifikaci programu.
- Typy v Pascalu (jednoduché - strukturované, standardní - definované programátorem, ordinální).
- Výčtové typy.
- Typ interval. Hostitelský typ, běhové kontroly a možnost je vypínat (a proč to není žádoucí).
- Funkce ord pro ordinální typy, succ, prev, inc, dec.
- Jednoprůchodovost překladače Pascalu a z toho vyplývající požadavek, aby každý identifikátor byl v (textu) programu definován před tím než je použit.
- Pole, indexový typ, typ složky, přístup ke složce pole pomocí indexového výrazu.
- For cyklus jeho syntaxe a sématnika.
zpět na začátek
přednáška 19.listopadu
- Vícerozměrná pole.
- Řetězce (stringy).
- Kvadratický algoritmus pro nalezení délky nejdelší rostoucí vybrané posloupnosti (dokáže nalézt i tuto posloupnost). (program) .
  Problém na rozmyšlení: nalézt (asymptoticky) rychlejší program pro nalezení délky nejdelší rostoucí vybrané posloupnosti (třeba za cenu toho, že samu posloupnost nenajde).
- Typ záznam (record) a příkaz with.
  Typická reprezentace vektoru jako záznamu o dvou složkách:
  Pole a jeho skutečně využitá délka.
- Příklady funkcí (nsd, faktoriál,...).
- Výpočet kombinačních čísel s prevencí přetečení.
- Efektivní výpočet N-té mocniny pomocí 2*log2(N) násobení
zpět na začátek
přednáška 26.listopadu
- Podprogramy a jejich význam pro programování. Návrh programu metodou "shora dolů".
- Procedury.
- Předávání parametrů hodnotou a referencí. Jednoduchý příklad.
- Lokální versus globální deklarace a jim odpovídající objekty.
- Alokace lokálních objektů (parametrů a lokálních proměnných) na zásobníku.
- Standardní podprogramy pro práci se stringy (mimo val a str).
- Vstup a výstup, abstrakce souboru, textové a datové soubory.
- Procedura assign
- Otevíraní textových souborů pro čtení (reset), zápis (rewrite) a přípis(append).
- Přehled prostředků pro vstup z textového souboru: read, readln, eof, eoln.
- Přehled prostředků pro výstup do textového souboru: write, writeln.
přednáška 3.prosince od 14.00 v K1
spojena s následující
přednáška 3.prosince od 15.40 v K1
- Vstup čísel ze souboru, funkce seekeof, seekeoln.
- Vstup řetězců.
- Formátovaný výstup.
- Typická reprezentace vektoru jako záznamu o dvou složkách:
  Pole a jeho skutečně využitá délka.
- Hledání prvku v tabulce: první výskyt, použití zarážky pro urychlení testu, prostřední výskyt.
- Hledání prvku v uspořádané tabulce, metoda půlení intervalu.
- Úplné a neúplné vyhodnocování booleovských výrazů.
- Programové jednotky - unity: část interface, část implementation, klausule uses. Překlady Compile, Make a Build.
- Lokální versus globální deklarace a jim odpovídající objekty.
- Alokace lokálních objektů (parametrů a lokálních proměnných) na zásobníku.
- Příklad "neintuitivního" chování podprogramu, který byl zavolán se stejným skutečným parametrem pro dva různé formální parametry předávané referencí.
- Rekursivní podprogramy. Faktoriál rekursivně a iterativně.
- Doslovný přepis definice Fibonacciovy posloupnosti vede k algoritmu exponenciální složitosti.
- Úloha o osmi dámách.
  Rekursivní implementace algoritmu backtrackingu. Návrh datové struktury, která jde inkrementálně aktualizovat.
- Vyčíslování hodnoty aritmetického výrazu.
  Metoda rekursivního sestupu - konstrukce rekursivních podprogramů na základě gramatiky definující syntaxi výrazu.
- Rekursivní procedura, která využívá implicitního zásobníku volání podprogramů k otáčení vstupního řetězce.
- Přímá a nepřímá rekurse. Direktiva forward.
- Úlohy k rozmyšlení :
  - Program pro nalezení maximálního počtu vzájemně se neohrožujících figur na šachovnici daného rozměru pro různé konkrétní (exo)figury, totéž pro figuru, jejíž tahy se přečtou z dat.
  - Modifikace procedur pro vyhodnocování aritmetického výrazu tak, abychom nevyužívali vnořených podprogramů.
- Pseudonáhodná čísla.
  Co to je. Pseudonáhodná čísla v Borland Pascalu : funkce random (vracející real resp. vracející integer), randseed - hnízdo, randomize - inicializace hnízda.
  Metoda Monte Carlo. Příklad výpočtu objemů složitého tělesa. Výpočet generátoru dávajících konečně mnoho hodnot se zadanými pravděpodobnostmi.
zpět na začátek
přednáška 10.prosince
- Povídání o testech a systému přihlašování na ně.
- Typ množina, jeho realizace v Borland Pascalu.
- Velká množina jako pole množin.
- Sekvenční algoritmus pro nalezení reflexního, symetrického a transitivního uzávěru binární relace ze vstupujícího seznamu jejich dvojic.
- Procházení grafu do hloubky a do šířky. Společný algoritmus užívající seznamy OPEN a CLOSE (je-li OPEN zásobník, dostaneme průchod do hloubky, je-li to fronta, dostaneme průchod šířky).
- Typická implentace zásobníku (pole a jeho konec) a fronty (zacyklené pole a jeho začátek a konec).
- Implementace algoritmu vlny bez explicitního vytváření fronty (na příkladu hledání nejkratší cesty na šachovnici - na jednotlivých polích ukládáme délku nejkratší cesty, samotnou cestu pak najdeme "zpětným chodem").
- Dijkstrův algoritmus pro nalezení délek nejkratších cest ze zadaného startovního vrcholu do všech ostatních (zatím bez důkazu).
zpět na začátek
přednáška 7.ledna
- Hledání nejkratší cesty, Dijstrův algoritmus
- Typované konstanty jako prostředek pro inicializaci datových struktur (nejde při tom o konstanty v pravém slova smyslu).
- Příkaz case.
- Program : počet rozkladů čísla na sčítance.
- Povídání o testech.
- Analýza vybraných příkladů.
zpět na začátek

Zpět