- přednáška 2.října
- Úvodní povídání o předmětu a studiu na MFF UK.
- Několik dobrých cílů:
- Je třeba umět poznat zda něčemu rozumíme nebo ne
- pokud víme, že věci rozumíme - a je to pravda - jsme "za vodou"
- pokud víme, že věci nerozumíme, pak jsme v situaci, která nás bude provázet celým životem, je však známa naprosto spolehlivá metoda, jak ji "řešit" -
několikrát zopakujeme kolečko (rozmyslet si, přečíst si, poradit se)
- pokud nevíme, že nevíme, je to vážný psychologický (či osobnostní) problém, se kterým mohou pomoci rodiče, přítel/kyně, psychoanaliti-k/-čka, trenér (kick)boxu a pod. - ne však učitel,
ten jen může pomoci stanovit diagnozu
Pokud se Vám nepodaří tohoto cíle dosáhnout asi Vám na matfyzu nebude moc dobře
- Je třeba umět vysvětlit, to čemu rozumíme (jinak řečeno - neumíme-li to vysvětlit, může to být i tím, že tomu nerozumíme).
Správným cílem při tom není vysvětlit to "panu profesorovi" (o kterém předpokládáme, že to umí lépe než my),
ale stejně chytrému kolegovi jako jsme my, který ale o dané věci neví nic. To je těžké a ne všem se to v prním ročníku podaří, ale nejpozději do psaní bakalářské práce se to naučit musíte.
- Podmínky k zápočtu, praktický test, zkouška v letním semestru
- O nepovinném předmětu NMIN161 "Praktika z programování pro začátečníky", jeho cílech a způsobech výuky
Tento předmět začne na ostro v týdnu od 22.října, bylo by však dobré přijít do skupiny, kam chcete chodit již v týdnu od 15.října.
Zapsat půjde až před koncem měsíce.
- Příklady konkrétních algoritmů:
- Eukleidův algoritmus
- aritmetické operace v desítkové soustavě
- konstrukce magického čtverce lichého řádu
- výpočet n-té mocniny pomocí co nejmenšího počtu násobení - (2*log2(n)) dokažte si tento odhad, ještě se k tomu vrátíme
- Úloha o nalezení stabilního párování - zkuste najít algoritmus
- Úloha o bludišti a jednoduchý "Ariadnin" algoritmus,
který ji řeší (trasování na konkrétním bludišti).
- Algoritmus je správný, když je
- konečný (na každý přípustných datech skončí)
a
- parciálně správný (pokud skončí, tak dá správný výsledek)
tuto ideu využijeme pro dokazování správnosti algoritmů
- Důkaz konečnosti Ariadnina algoritmu
- Pojem invariantu algoritmu
- Beletristické zpracování Ariadnina algoritmu a důkazu jeho správnosti.
- Ariadnin algoritmus je vlastně speciálním případem obecnějšího algoritmu prohledávání grafu do hloubky (backtracking),
se kterým se ještě mnohokrát setkáme.
- přednáška 9.října
- O předmětu, literatuře, překladačích, praktiku, ....
- Opakování: pojem algoritmu,
algoritmus backtrackingu, idea důkazu konečnosti algoritmů, pojem invariantu, důkaz konečnosti Ariadnina algoritmu
- Důkaz parciální správnosti Ariadnina algoritmu
- Pojem algoritmu, jeho "filosofické vymezení"
- Griesova úloha o tahání koulí z urny
- Algoritmus hledání stabilního párování a důkaz jeho správnosti
důkaz, že náš algoritmus nalezne optimální stabilní párování, které je "optimální pro muže"
- Existují algoritmy, jejichž správnost jde (poměrně snadno) dokázat, ale jejichž výpočty na reálných datech trvají tak dlouho,
že jsou prakticky nepoužitelné. Proto je třeba zabývat se složitostí algotritmů. O tom, jak se měří, budeme - mimo jiné - povídat příště.
- 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.
- Strukturované příkazy. Úplný a neúplný podmíněný příkaz, složený příkaz, cykly while a repeat.
- Vývojové diagramy řečené bloková schémata - "blokáče"
- přednáška 16.října
Pokud jste tak již neučinili, pořiďte si účet v laboratoři Karlín a zaregistrujte se do systému Codex !!!
Pokud chcete navštěvovat praktika NMIN161, přijďte nejpozději v tomto týdnu na příslušné praktikum nebo se ozvěte jeho vedoucímu.
Informace o obsazenosti jednotlivých praktik najdete na stránce předmětu
- Opakování: Proměnná, přiřazovací příkaz,
Úplný a neúplný podmíněný příkaz, složený příkaz, cykly while a repeat.
Tvar programu v Pascalu.
- Tvar programu v Pascalu
- Čísla ve světě, rychlost růstu exponenciely
- Čísla ve světě, v matematice, "počítačová" čísla.
- Typ integer, aritmetické operace a jejich priority, konstanta maxint, přetečení hodnoty.
(ukázka, že díky němu není sčítání integerů asociativní)
- Konstanty jako nástroj pro snadnou modifikaci programů.
Ukázkové programy.
- Typ real, standardní funkce.
- Ukázkový program, demonstrující,
že není rozumné používat pro kontrolu běhu výpočtu programu výsledek testu reálný čísel na rovnost.
- Typová ochrana přiřazovacího příkazu. Funkce trunc a round.
- přednáška 23.října
V tomto týdnu by mělo být jasné kdo a na jaké praktikum chce chodit
- Programové konstrukce Pascalu jsou strukturované, lze tedy při návrhu programu postupovat "shora dolů"
- Syntaktická nejednoznačnost konstrukce podmíněného příkazu.
- Celočíselné typy v Borland Pascalu a Free Pascalu:
integer, shortint, longint
V učebnicích i na přednášce se setkáte s typem integer, v konkrétních případech je ho z důvodů malé hodnoty maxint často vhodné nahradit
(zejména v Borland Pascalu) typem longint
- V případech citlivých na přesnost zobrazení je vhodné nahradit typ real typem double
zmenší se tím reativní chyba (zvětší počet platných cifer), nejde o zvětšení rozsahu čísel
- 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
Hornerovo schéma je vlastně lineární algoritmus pro zjištění hodnoty polynomu v zadaném bodě
- 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 programu je chyba v kontrole přípustnosti znaku v zápisu, zkuste ji odhalit!
- "Zoologie" typů v Pascalu (jednoduché - strukturované,
standardní - definované programátorem, ordinální).
- Výčtové typy
- Ordinální typy - funkce ord, succ, pred, inc, sub
- přednáška 30.října
- opakování ordinální typy
- Typ interval. Hostitelský typ, běhové kontroly a možnost je vypínat
(a proč to není žádoucí).
- for cyklus jako opakování zadaný počet krát,
je zakázáno měnit uvntř těla cyklu hodnotu řídící proměnné cyklu, případná změna horní meze uvnitř těla cyklu nemá vliv na počet průchodů tělem cyklu
jednoduché příklady dvou cyklů v sobě.
- Pole, indexový typ, typ složky, přístup ke složce pole pomocí indexového výrazu.
- Vícerozměrná pole
- Jednoduchý příklad - hledání maxima čísel ležících pod hlavní diagonálou čtvercové matice
- Funkce v Pascalu, příklady jednoduchých funkcí.
- Faktoriál
- Výpočet kombinačních čísel - není vhodné volat funkci faktoriál, výpočet s prevencí přetečení
- Zkuste naprogramovat funkci, která umocňuje v logaritmickém čase
- přednáška 6.listopadu
- Podprogramy a jejich význam pro programování.
- Procedury, funkce, formální a skutečné parametry.
- Bloková struktura programu a viditelnost objektů.
Lokální a globální deklarace. Lokální definice zastiňuje globální.
- Předávání parametrů hodnotou a referencí. Jednoduchý příklad.
- Alokace lokálních objektů (parametrů a lokálních proměnných) na zásobníku.
- Kdy použít předávání parametrů hodnotou resp. referencí
- Je výrazně lepší používat komunikaci s podprogramy přes parametry než používat globálních proměnných (vyjímky budou později)
- Je vhodné se vyhýbat používání podprogramů lokálních v jiných podprogramech,
protože to ve většině dnes používaných jazyků (c-like) nejde
- Typ záznam (record) a příkaz with,
jednoduché příklady.
Používání příkazu with je analogie vět se zamlčeným podmětem, podstatně zjednodušuje zápis,
jeho nadužívání však může vést ke zcela nesrozumitelným programům.
- Najděte chyby v podprogramu, který má transponovat matici
řešení
- 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í.
- přednáška 13.listopadu
- Opakování:
- Procedury, funkce, formální a skutečné parametry.
- Bloková struktura programu a viditelnost objektů.
Lokální a globální deklarace. Lokální definice zastiňuje globální.
- Předávání parametrů hodnotou a referencí. Jednoduchý příklad.
- Alokace lokálních objektů (parametrů a lokálních proměnných) na zásobníku.
- Kdy použít předávání parametrů hodnotou resp. referencí
- Je vhodné se vyhýbat používání podprogramů lokálních v jiných podprogramech,
protože to ve většině dnes používaných jazyků (c-like) nejde
- Je výrazně lepší používat komunikaci s podprogramy přes parametry než používat globálních proměnných
(vyjímky budou později)
- Dobrá zásada:
Vždy hned po návrhu hlavičky podprogramu napište komentář,
který v "řeči parametrů" popíše, co podprogram má udělat (nikoli jak, ale co),
teprve pak pište její kód
- 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 -
klikátko.
- Unity utab a seektab
realizující probírané algoritmy vyhledávání v tabulce
Přečtěte i si kód procedur, které jsme na přednášce detailně neprobírali, připravte si případné dotazy
- Úplné a neúplné vyhodnocování booleovských výrazů.
Přepinač B ovlivňujicí činnost překladače Pascalu
- Programové jednotky - unity, klausule uses, části interface a implementation
- Znakové řetězce - stringy, funkce length
- Standardní podprogramy pro práci se stringy:
+ , lenght, pos, copy, delete, insert,
konverze mezi číselnou hodnotou a jejím zápisem ve stringu
a komentář k jejich používání
- Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti
(program),
rozmyslete
- přednáška 20.listopadu
Pravděpodobný obsah přednášky
- Motivace k pojmu asymptotické složitosti
- Ekvivalence dvou definic pojmu "funce f je velké O z funkce g"
- Měření časové složitosti algoritmu, asymptotická složitost - formální definice pomocí O(f).
- Nejlepší, nejhorší a průměrný případ
- Použitelnost odhadu asymptotické složitosti pro konkrétní výpočet
- Mrkev a petržel
- 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.
animace (nemusí vám ve Windows 7 chodit)
- Trivální algoritmus složitosti n3*m3 ,
ani chytrá implementace naivního algoritmu příliš nepomůže
- Algoritmus se složitostí n*m2
využívající předvýpočet "počtu jedniček pod danou jedničkou",
rozmyslete
- Zkuste najít algoritmus pracující v čase n*m
návod: postup je založený na myšlence,
že v matici obroubené nulami každý maximální jedničkový
obdélník přiléhá zprava k nějaké nule, a předvýpočtech počtů jedniček nad a pod danou jedničkou
- Význam použití souborů pro ladění programů
- Datové a textové soubory - rozdíl v použití, (file of char není textový ale datový soubor!),
v zimním semestru budeme používat jen textové soubory !
- Textové soubory v Pascalu - abstraktní model a konkrétní reprezentace.
- Procedura assign
- Otevření textového souboru ke čtení, k zápisu a přípisu. Zavírání textového souboru.
- Všechny procedury mají nepovinný první parametr udávající, ze/do kterého souboru se má číst/psát
pokud není uveden jde o vstup/výstup z/do souboru input/output,
- Vstup z textového souboru.
- Testy eof, eoln,
- Procedura read, readln,
- Čtení znaků
- Čtení čísel
- Anomální chování programu s testem
while not eof(F) do
begin read(F,I); ..... end;
- Testy seekeof, seekeoln.
- Čtení znakových řetězců,
pozor chová se neočekávaně!
- přednáška 27. listopadu
Pokud se v látce ztrácíte, je nyní nejvyšší čas nějak na to reagovat (studium, dotazy na přednáškách a cvičeních, konzultace, počítání více příkladů, diskuse s kolegy).
Později Vás to může stát neúměrně více úsilí a nemusí se to ani povést.
Stav, kdy víte, že nevíte, je normální a zvládne se studijním úsílím a konzultacemi.
Stav kdy nevíte, že nevíte, je nebezpečný, deprimující a demotivující, neměli byste se do něj dostat.
V něm už nestačí jen se učit, je ale je třeba se hlouběji zamyslet nad motivacemi ke studiu, které máte, sebrat síly a
najít odvahu se s tím poprat - možná pak budete potřebovat i psychologickou podporu Vašich blízkých.
- Opakování pojmu asymptotické složitosti
- Mrkev a petržel
- Zkuste najít algoritmus pro hledání maximálního jedničkového obdélníka pracující v čase m*n
- Mrkev a petržel
- Opakování textové soubory:
procedura assign, otvírání a zavírání souboru,
je lepší pracovat s abstarktním modelem textového souboru než s jeho fyzickou reprezentací
(s konci řádků budeme pracocvat výhradně pomocí procedur eln, readln, writeln)
vstup v Pascalu
- Výstup do textového souboru
- Formátování
- Procedura write, writeln,
- výstup znaků
- výstup integerů (bez formátu se výsledky mohou "slepit")
Pascalův trojúhelník jako příklad programů,
kde formát je "složitější" výraz
- výstup čísel typu real, zokrouhlování, výstup v semilogaritmickém a "desetinném" tvaru
- Ukázkový program demonstrující
formátovaný výstup číselných hodnot
a jeho výstup
- výstup řetězců
- Výstup hodnot typu boolean - normální člověk nepoužívá
- Chyba Borland Pascalu - při ukončení programu nezavře výstupní soubory
(a tedy nevyprázdní buffery do souboru)
proto se doporučuje na konci programu vždy zavřít všechny výstupní soubory procedurou close
- Rekursivní algoritmy a podprogramy
- Rekursivní funkce - faktoriál, je (mírně) lepší naprogramovat iterativně
- Fibonnaciova posloupnost - chybné řešení s exponenciální složitostí - animace
naprogramujte si iterativní řešení i rekursivní řešení bez této chyby(přidáte parametr/y)
- Rekursivní řešení problému Hanojských věží a jeho animace
- 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í aktualizaci - Program
Rozmyslete si dobře a důkladně tento algoritmus i jeho technické provedení. Příště se k němu vrátíme.
Velmi mnoho rekursivních algoritmů můžete "napasovat" na toto schéma.
- přednáška 4.prosince
- přednáška 11.prosince
- opakování - průchod do šířky a do hloubky
- typické implementace zásobníku a fronty (fronta pomocí "zacykleného pole")
- Porovnání použití prohledávání do šířky a do hloubky pro hledání nejkratší cesty
- Přímá a nepřímá rekurse, direktiva forward,
někdy se používá i jen k tomu, abychom hlavičky podstatných podprogramů umístili hned na začátek programu
- Různé reprezentace grafu,
Matice sousednosti, matice incidence, seznam hran, seznamy následníků (lze "dát do jednoho pole")
- Mocnina grafu sousednosti - použití pro hledání komponent souvislosti
- Typ množina, jeho realizace v Borland Pascalu.
- 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;
faktorová množnina - animace
rozmyslete si!
- "typované" konstanty (pozor nejsou to konstanty !) jako příjemný způsob inicializace hodnot
proměnných (i strukturovaných) typů
- podmíněný příkaz case a typický způsob jeho implemenace jako "skoku podle indexu"
- přednáška 18.prosince
- Opakování: algoritmus faktorové množiny
- Velká množina jako pole množin.
- Strukturované a modulární programování
- měli byste se zamýšlet nad strukturou svých programů a tvořit spíše podprogramy,
které budou data dostávat a odevzdávat prostřednictvím parametrů, než hlavní programy, které řeší vše.
- Kriteria pro užitečné rozdělení systému na části:
- Vazby jednotlivých částí (jejich inteface) musí být jednoduché
- Funkce celého systému musí jít jednoduše popsat jako spolupráce jeho částí
aniž bychom museli znát (detailní) vnitřní strukturu jeho částí
- Použití globálních proměnných může vést k sideefectům a pokud pro to nejsou vážné důvody,
měl by podprogram komunikovat jen "přes svoji hlavičku" - pomocí parametrů
Jednou z vyjímek je použití globálních proměnných při tvorbě rekurzivních podprogramů
(alternativa - předávat stále stejný parametr odkazem - je očividně horší)
- příkaz goto - je lepší nepoužívat
"kultivované" formy skoků: break, continue, exit, halt
- třetí způsob předávání parametrů v Borland Pascalu - const
- rozšíření Pascalu - konformní schémata polí - neužívejte!
- reprezentace "dlouhých čísel" a programování operací s nimi
- Dijkstrův algoritmus pro hledání nejkratší cesty v grafu s nezáporně ohodnocenými hranami
invarianty, složitost - klikátko
pamatování se předchůdce - zpětný chod
- Floyd-Warshalův algoritmus pro nalezení všech vzdáleností v grafu, doplnění, aby hledal nejkratší cesty
- topologické uspořádání grafu, algoritmus a vhodné datové struktury (pro každý vrchol si pamatujeme počet předchůdců a seznam následníků)
- zadání aritmetického výrazu stromem a třemi notacemi: inorder, postorder, preorder
klikátka:
- vyčíslování hodnoty aritmetického výrazu zadaného postorder notací
- klikátko
- vyčíslování hodnoty aritmetického výrazu z inorder notace
- metoda shora dolů - nalezení "nejvnějšnějšího" operátoru a rekursivní volání
- klikátko
- metoda zdola nahoru - postupné vyčíslování toho, co jde "hned vyčíslit"
- převod na postfix klikátko
-
přednáška 8.ledna
Na přednášce pravděpodobně bude - vše asi nestihneme
- Opakování vyčíslování hodnot aritmetických výrazů
- algoritmus převodu na postfix jde rovnou spojit a algorimem vyčíslování postfixu
- Vyčíslování hodnoty aritmetického výrazu (čtyři operace +, -, *, / s prioritami, závorky, bez znamének)
metodou rekursivního sestupu:
Formální definice aritmetického výrazu a z něj odvozené rekursivní procedury
pro vyčíslení hodnoty aritmetického výrazu - klikátko
- Rozmyslet: Modifikace programu pro vyčíslování hodnoty aritmetického výrazu
metodou rekursivního sestupu tak, aby nepoužíval podprogramů lokálních v jiném podprogramu.
Jak se musí změnit hlavičky podprogramů a jejich vzájemná komunikace?
- podrobněji se o vyčíslování aritmetických výrazů můžete dočíst
ve 12. kapitole knihy Algoritmy a programovací techniky
k programování těchto úloh se vrátíme v letním semestru
až budeme mít k dispozici lepší způsob reprezentace stromů
- technické poznámky k programování vyhodnocování výrazů
- Vnitřní třídění - specifikace úlohy, adresní a asociativní (založené na porovnávání klíčů) algoritmy
- adresní třídění pro malý rozsah čísel - bucketsort
- Jednoduché asociativní algoritmy složitosti O(n2):
- přímé zatřiďování
- binární zatřiďování - polohu najdeme v logaritmické čase, ale posun pole je lineární
- třídění výběrem
- třídění výměnami - bubblesort, shakesort
implementace bez pamatování si místa poslední výměny je programátorská nešikovnost
- Algoritmus Quicksort, jeho
rekursivní verze (bude na internet doplněna)
a nerekursivní verze - přečtěte si
- Využití prvku tříděného pole jako pivota - mohu použít jako zarážku
- Složitost quicksortu v nejhoším a v nejleším případě
- Paměťová složitost - třída algoritmů pracujících "na místě" - "in situ"
- Paměťová složitost quicksortu - netřídí na místě
- datová struktura heap (hromada) a dvě základní operace s ní: delete-min a přidej prvek
- hromada jako část pole, reprezentace hromady v poli,
algoritmus heap sortu
- vlastnosti třídích algoritmů: přirozenost, stabilita, třídění na místě (in situ)
- zdrojové texty procedur realizujících jednotlivé třídící algoritmy
- Nerekursivní a rekursivní
verze programu hledajícího všechny rozklady zadaného čísla na sčítance
rekursivní verzi jsme probrali detailně, rozmyslete si nerekursivní
- Přepinače kompilátoru
- standardní unity Pascalu
- unita CRT
- odpovědi na dotazy -- budou-li
hromadná konzultace k přednášce se koná 14.ledna od 10:00 v posluchárně S4
- suplováni v paralelce X 19.prosince
- komentář k praktickým testům a přihlašování na ně, průzkum zájmu o termíny
- Pseudonáhodná čísla, pojem a jejich použití, hnízdo generátoru náhodných čísel
- Pseudonáhodná čísla v Borland Pascalu
( RandSeed, Randomize, Random, Random(n) )
- Metoda Monte Carlo
- proč je důležité mít možnost pseudonáhodnou posloupnost přesně reproduvat
- politická aktualita
http://www.ceskapozice.cz/domov/politika/jak-se-v-kocourkove-dela-nahodny-prezidentsky-vyber
nekontroloval jsem osobně, ale jde z toho děs - aspoń vidíte, že lidé vašeho typu to budou muset vzít za své, jinak dopadneme strašně
- Strukturované a modulární programování
- měli byste se zamýšlet nad strukturou svých programů a tvořit spíše podprogramy,
které budou data dostávat a odevzdávat prostřednictvím parametrů, než hlavní programy, které řeší vše.
- Kriteria pro užitečné rozdělení systému na části:
- Vazby jednotlivých částí (jejich inteface) musí být jednoduché
- Funkce celého systému musí jít jednoduše popsat jako spolupráce jeho částí
aniž bychom museli znát (detailní) vnitřní strukturu jeho částí
- Použití globálních proměnných může vést k sideefectům a pokud pro to nejsou vážné důvody,
měl by podprogram komunikovat jen "přes svoji hlavičku" - pomocí parametrů
Jednou z vyjímek je použití globálních proměnných při tvorbě rekurzivních podprogramů
(alternativa - předávat stále stejný parametr odkazem - je očividně horší)
- příkaz goto - je lepší nepoužívat
"kultivované" formy skoků: break, continue, exit, halt
- Programové jednotky - unity, klausule uses, části interface a implementation
- podrobný rozbor unit utab a seektab
realizující probírané algoritmy vyhledávání v tabulce
- unita se zdrojovými texty procedur realizujících jednotlivé třídící algoritmy
- 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í aktualizaci - Program
Rozmyslete si dobře a důkladně tento algoritmus i jeho technické provedení.
Velmi mnoho rekursivních algoritmů můžete "napasovat" na toto schéma.
- V úloze o dominanci šachovnice dámami
(hledáme nejmenší počet dam, které by ohrožovaly všechna políčka šachovnice)
pro inkrementální aktualizaci stavu si nestačí pamatovat pro každé políčko
zda je ohrožováno, ale stačí pamatovat si
kolikrát je ohrožováno