PRM001 Programování - středa 10:40 M1

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

16.října - odpadla (imatrikulace)

přednáška 23.října
přednáška 30.října
přednáška 6.listopadu
přednáška 13.listopadu
přednáška 20.listopadu
přednáška 27.listopadu
přednáška 4.prosince
přednáška 11.prosince
přednáška 18.prosince
přednáška 10.ledna

přednáška 23.ří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 a důkaz jeho správnosti. Pojem invariantu.
- Úlohy k rozmyšlení :
  - Synchronizace konečných automatů (generál a vojáci)
  - Nalezení stabilního párování
zpět na začátek
přednáška 30.října
- 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.
- 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.
- Úloha k rozmyšlení :
  Nalézt 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 6.listopadu
- 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 .
- Složený příkaz, úplný a neúplný podminěný příkaz, cykly repeat a while.
- Odstranění nejednoznačnosti konstrukce
  if P then if Q then S1 else S2
- Čí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.
- Typ real : operace, standardní funkce, funkce trunc a round.
zpět na začátek
přednáška 13.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.
zpět na začátek
přednáška 20.listopadu
- Pole, indexový typ, typ složky, přístup ke složce pole pomocí indexového výrazu.
- For cyklus jeho syntaxe a sématnika.
- 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).
- 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 27.listopadu
- 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.
- 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ů.
- 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.
zpět na začátek
přednáška 4.prosince
- 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ů.
zpět na začátek
přednáška 11.prosince
- Povídání o testech a systému přihlašování na ně.
- 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), zavírání souboru.
- Přehled prostředků pro vstup z textového souboru: read, readln, eof, eoln.
  Vstup čísel ze souboru, funkce seekeof, seekeoln.
  Vstup řetězců.
- Přehled prostředků pro výstup do textového souboru: write, writeln.
  Formátovaný výstup.
zpět na začátek
přednáška 18.prosince
- Příkaz case.
- 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).
- Programové jednotky - unity: část interface, část implementation, klausule uses. Překlady Compile, Make a Build.
zpět na začátek
přednáška 10.ledna
- ještě nebyla
- 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 PRM001