Co bylo PRG030 Programování I

přednáška 7.října

Úvodní povídání o předmětu a studiu na MFF UK.
Pojem algoritmu, "filosofické vymezení", příklady konkrétních algoritmů:
sčítání v desítkové soustavě, Eukleidův algoritmus, Erathostenovo síto (úpravy jeho efektivity), konstrukce magického čtverce lichého řádu.
Problém stabilního párování a jeho řešení algoritmem pánské volenky. Důkaz toho, že pánská volenka vytvoří stabilní párování, které je mezi všemi stabilními párováními "optimální pro muže".
Konečnost a parciální správnost algoritmu.
Úloha o bludišti a důkaz správnosti algoritmu, který ji řeší
Pojem invariantu algoritmu
Měření časové složitosti algoritmu, asymptotická složitost - formální definice pomocí O(f).
Příklad na hledání maximálního jedničkového obdélníku v 0/1 obdélníku rozměrů m x n.
- Trivální algoritmus složitosti n³*m³
- Algoritmus se složitostí n*m² využívající předvýpočet "počtu jedniček pod danou jedničkou"
- Na rozmyšlenou: Najít algoritmus pracující v čase n*m

Zpět začátek

přednáška 21.října

Opakování tématu asymptotické složitosti. Složitost konkrétního výpočtu jako počet provedení zvolené operace (resp. váženého mixu operací). Složitostí je funkce z N do N, Nejhorší případ, průměrný případ, nejlepší případ. Pojem O(f) a definice asymptotické složitosti, její přednosti a "antiintuitivnost" a zní vyplývající úskalí jejího bezmyšlenkovitého použití na konkrétní problém.
Motivační příklad pro zavedení konstrukcí obvyklých v programovacích jazycích.
Proměnná - jméno místa pro uložení hodnoty, nikoli hodnoty samé. Přiřazovací příkaz. Příkazy pro čtení (read) a výstup (write).
Datový typ, deklarace proměnných.
Identifikátor, zápis číselné konstanty, klíčové slovo.
Složené příkazy. Úplný a neúplný podmíněný příkaz, složený příkaz, cykly while a repeat. Syntaktická nejednoznačnost konstrukce podmíněného příkazu.
Čísla v reálném světě, v matematice a v počítači. Rychlost růstu exponenciely.
Typ integer. Maxint, přetečení hodnoty.
Celočíselné typy v Borland Pascalu (integer, longint, shortint, byte, word).
Typ real, standardní funkce, zaokrouhlovací chyby.
Typová ochrana přiřazovacího příkazu. Funkce trunc a round.
Výpočet hodnot výrazů - hlavní zásady.
Konstanty jako nástroj pro snadnou modifikaci programů.

Zpět začátek

přednáška 4.listopadu

Algoritmus hledající maximální jedničkový obdélník v 0/1 obdélníku o rozměrech m x n pracující v čase O(m*n)
Typ boolean.
Program, který testuje, zda číslo na vstupu je prvočíslo.
Typ char, funkce ord a chr.
Zápis čísla v poziční soustavě, výpočet jeho hodnoty Hornerovým schématem
Příklad programu, který čte ze vstupu řádky obsahující vždy číslo k udávající základ soustavy a zápis nějakého čísla X v této soustavě a spočítá a vytiskne hodnotu čísla X
Výčtové typy
"Zoologie" typů v Pascalu (jednoduché - strukturované, standardní - definované programátorem, ordinální).
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, jednodyché příklady.
Vícerozměrná pole.
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í "hardwarový" výpočet N-té mocniny pomocí umocňování na druhou násobení
Problém na rozmyšlení: nalézt přesný horní odhad počtu násobení pro tento algoritmus
Problém na rozmyšlení: příklad na vyčíslení složitější mocninné řady

Zpět začátek

přednáška 11.listopadu

Příklad na vyčíslení složitější mocninné řady (nepočítat každý člen vždy znovu, inkrementální výpočet dalšího členu z minulého, předpočítání nezávislých faktorů).
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.
- Unity utab a seektab realizující probírané algoritmy vyhledávání v tabulce
Samostatně překládané programové jednotky - unity. Interfaceová a implementační část, klausule uses. Význam používání unit. Módy překladu Complile, Make, Build
Úplné a neúplné vyhodnocování booleovských výrazů.
Přepinače ovlivňujicí činnost překladače Pascalu (speciálně B a R).
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.
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í.
Kdy použít předávání parametrů hodnotou resp. referencí
Pojem souboru, datové a textové soubory.

Zpět začátek

přednáška 18.listopadu

Znakové řetězce (stringy) a standarní podprogramy pro práci s nimi.
(Podmíněný) příkaz case
Textové soubory v Pascalu,
Procedura assign
Otevření textového souboru ke čtení, k zápisu a přípisu. Zavírání textového souboru.
Vstup z textového souboru.
- Testy eof, eoln, seekeof, seekeoln.
- Procedura readln,
- Čtení znaků, čísel a čtení stringů (a jeho specifika).
Výstup do textového souboru
- Formátování
- Procedura writeln,
- výstup znaků,
- výstup integerů (bez fromátu se výsledky mohou "slepit")
- výstup čísel typu real, zokrouhlování, výstup v semilogarotmickém a "desetinném" tvaru
Anomální chování programu typu while not eof do begin read(I); ...... end
a způsoby, jak se mu vyhnout
Rekursivní podprogramy
Faktoriál rekursivní a iterativní řešení
Fibonnaciova posloupnost - chybné řešení s exponenciální řešení

Rozmyslet: Iterativní výpočet a rekursivní procedura s lineární složitostí

Výstup otočeného řetězce pomocí rekursivní procedury s lokální proměnnou.
Hledání všech pozic N nezávislých dam na šachovnici N x N - volba datových struktur umožňujících inkrementální. Program
Rozmyslet:
- Program, který hledá jen ty pozice N nezávislých dam, které nelze získat pomocí symetrie z již dříve nalezených pozic.
- Program pro hledaní všech maximálních nezávislých konfigurací obecné (exo)figury zadané na vstupu.
Formální definice aritmetického výrazu a z něj odvozené rekursivní procedury pro vyčíslení hodnoty aritmetického výrazu

Zpět začátek

přednáška 25.listopadu

Výstup řetězců a booleoských hodnot
Program pro nalezení délky nejdelší rostoucí vybrané posloupnosti s časovou složitostí n*log(n)
Rekursivni a nerekursivni verze programu pro rozklad čísla na sčítance
Přímá a nepřímá rekurse. Direktiva forward.
Rozmyslet: Modifikace procedur pro vyhodnocování aritmetického výrazu tak, abychom nevyužívali vnořených podprogramů.
Pseudonáhodná čísla - princip použití, hnízdo generátoru. Metoda Monte Carlo. Pseudonáhodná čísla v Borland Pascalu ( RandSeed, Randomize, Random, Random(n))
Systémové unity SYSTEM a CRT. Stručná charakteristika jejich role.
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.
Program a jeho realističtější verze.

Zpět začátek

přednáška 2.prosince

Informace o přihlašování k praktickým testům, předtermíny.
Předávání parametrů const
Průchod grafem do šířky a do hloubky, implementace pomocí seznamů OPEN a CLOSE.
Je-li OPEN zásobník jde o průchod do hloubky, je-li to fronta jde o průchod do šířky.
Výhody a nevýhody průchodů do hloubky a do šířky. Ořezávání při průchodu do hloubky.
Typické implementace zásobníku a fronty pomocí polí. Cyklické pole jako implentace fronty.
Úloha hledání nejkratší cesty na šachovnici se zakázanými políčky. Vstup dat ze souboru, algoritmus vlny - implementace procházení do šířky bez explicitní fronty.
Některé reprezentace grafu:
- Seznam hran (a vrcholů)
- Matice sousednosti
- Matice incidence
- Seznamy následníků jednotlivých vrcholů
Umocňování matice sousednodnosti jako prostředek pro hledání vrcholů vzdálených m hran, resp. k hledání komponent
Dijkstrův algoritmus pro hledání vzdáleností všech vrcholů od startovního vrcholu, modifikace pro nalezení nejkratší cesty. Invariant algoritmu a důkaz jeho správnosti a složitosti.
Třída asociativních algoritmů vnitřního třídění pracujících in situ
Jednoduché třídící algoritmy s kvadratickou složitostí
- zatřiďování přímé a binární
- výběr
- výměna - bubblesort a jeho implementace, při níž si pamatuji místo poslední změny, shakesort
Vlastnosti třídících algoritmů: stabilita (je nutná, chceme-li algoritmus použít pro třídění podle více kritérií), a přirozenost (je vhodný pro skoro setříděná pole)
Quicksort - myšlenka; rekursivní implementace s pivotem jako zarážkou; složitost v nejlepším a nejhorším případě.
Datová struktura heap(halda), operace extract-min a insert (v čase log(n))
Reprezentace haldy v poli
procedura Sift(L,R:index), která přidává k haldě A[L+1]..A[R] prvek A[L]
Heapsort - třídící algoritmus heapsort se složitostí n*log(n)
V čem může být quicksort lepší než heapsort
Programová jednotka, testovací program a zkušební data realizující vybrané algoritmy vnitřního třídění

Zpět začátek

přednáška 9.prosince

Implementace seznamu jako pole - výhody a nevýhody
Ukazatele a dynamicky alokované proměnné, new, dispose, konstanta nil.
Jednosměrný spojový lineární seznam ukončený nilem a jednoduché opereace s ním
- Vytvoření seznamu (od posledního nebo od prvního prvku)
- Vložení prvku do seznamu za jeho zadaný prvek
- Vložení prvku do seznamu před jeho zadaný prvek
- Vypuštění následujícího prvku
- Průchod seznamem
- Hledání prvku s danou vlastností
Možnost "přetržení seznamu" - ztráta přístupu k dynamicky alokovaným proměnným (t.zv. "smetí" v paměti).
Jiné "modely" seznamů, např. cyklický seznam, seznam s přístupem na začátek i na konec, seznam s hlavou a/nebo s ocasem, dvojsměrný seznam atp.
Na rozmyšlenou:
- Vytvořte procedury provádějící jednoduché akce s jednotlivými typy seznamů.
- Obracení lineárního seznamu.
Možnosti vylepšení quicksortu
volba pivota, odstranění rekurze, dotřídění krátkých úseků jiným algoritmem, detekce nejhoršího případu
Odstraňování rekurze pomocí zásobníku
Nerekurzibvní quicksort, příklad implementace
Na rozmyšlenou:
Ukládám-li na zásobník oba úseky, který z nich je lepsší dát do zásobníku dřív ? Nebo je to jedno?
Procedurální a funkcionální typy, direktiva far resp. přepinač F vynucující vzdálené adresování.
Procedurální a funkcionální parametry, příklad procedury počítající kořen funkce, kterou dostane jako parametr.

Zpět začátek

přednáška 16.prosince

Komentář k praktickým testům.
Procedurální a funkcionální parametry - rekapitulace,
obecný průměr
Obracení lineárního seznamu
Program vyhledávání v uspořádaném seznamu s přístupem na fiktivní začátek (hlavu) a fiktivní konec (ocas).
Samoorganizující se seznamy ( např. nalezený prvek se stěhuje na první místo, nový prvek je vkládán na začátek).
Řídké polynomy - reprezentace pomocí cyklického seznamu s hlavou, její výhody,
ukázka alokace a uvolňování paměti "svépomocí", procedura pro nedestruktivní sčítání dvou řídkých polynomů.
Řídké matice - je třeba kriticky hodnotit přínosy té které implementace
Technické úlohy na rozmyšlenou:
- Napsat proceduru, která na základě dat ze vstupu vytvoří probíranou reprezentavci řídké matice
- Procedury pro "skladiště konzerv"
Typované konstanty (příklad popření přívlastkem) a jejich použití
Paměťová složitost quicksortu
Mergesort, příklad rekurzivní implementace
Metoda návrhu rozděl a panuj: analýza, rekurze, syntéza
klasifikace algoritmů vnitřního třídění z tohoto zorného úhlu
n*log(n) je dolní odhad složitosti úlohy vnitřního třídění v nejhorším a průměrném případě
Na rozmyšlenou: Zkusit dokázat, že tvrzení platí i pro průměrný případ

Zpět začátek

přednáška 6.ledna

O testech
Úloha kódování a dekódování morseovky
n*log(n) je dolní odhad složitosti úlohy vnitřního třídění i v průměrném případě
Antagonistická hra dvou hráčů s úplnou informací a nulovým součtem, Shannonova věta, algoritmus minimaxu, jeho negamaxová implementace
Statická ohodnocovací funkce, algoritmus minimaxu jako heuristika, horizont prohledávání, tiché pozice.
Typická architektura šachového programu
Alfa-beta prořezávání jako implementace manimaxu a jako heuristika, kaskádní varianta, metoda okénka, analýza plausibility
Hledání optimálního uzávorkování násobení posloupnosti matic pomocí dynamického programování.
Na rozmyšlenou:Nalezení minimální triangulace konvexního n-úhelníka

Zpět začátek

přednáška 13.ledna

Příkazy ovlivňující běh programu: goto, break, continue, exit,
Typická realizace haldy,
Prostředky pro alokaci a uvolňování paměti
- Garbage collector - v Pascalu není
- new a dispose
- svépomocí - proč může být vhodné
- mark a release - nepoužívat !!!
- prostředky nízké úrovně
  MemAvail, MaxAvail, Getmem, Freemem
Realizace dynamických polí (meze jsou proměnné) pomocí getmem a přetypování ukazatele
Open array parameters - možnost definovat podprogram, jehož skutečným parametrem může být libovolně velké pole
Reprezentace čísel v počítači, pevná a pohyblivá řádová čáska, doplňkový kód.
Nalezení minimální triangulace konvexního n-úhelníka pomocí dynamického programování.
Topologicky setříděný graf, algoritmus nalezení topologického setřídění.
Modifikace Dijsktrova algoritmu pro topologicky setříděné grafy.
Floydův algoritmus pro hledání nejkratší cesty v grafu.
Nejlacinější kostra grafu - odkaz na přednášku z Diskrétní matematiky, Faktorová množina.
O testech.
Otázky a odpovědi.

Zpět začátek

PRG030 Programování I

Co bylo na přednáškách

čtvrtek 14:50 M1