Hromadná konzultace ve středu 20.1. od 15:40 v posluchárně S3
- přednáška 30.září
pravděpodobný obsah přednášky
- Úvodní povídání o předmětu a studiu na MFF UK.
- Podmínky k zápočtu, praktický test, zkouška v letním semestru
- O předmětu nepovinném NPRM047 "Praktika z programování pro začátečníky", jeho cílech a způsobech výuky
Tento předmět půjde zapsat až cca za dva týdny a začne za tři týdny
- Pojem algoritmu, jeho "filosofické vymezení"
- Příklady konkrétních algoritmů:
- Eukleidův algoritmus
- aritmetické operace v desítkové soustavě
- konstrukce magického čtverce lichého řádu
- Fáze řešení problému a problémy na jejich rozhraních:
skutečnost - (matematický) model - algoritmizace a volba datových struktur - vytváření programu - testování
budeme se k tomuto schematu mnohokrat vracet
- 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í,
důkaz toho, že párování vzniklé pánskou volenkou je mezi všemi stabilními párováními optimální pro muže,
t.j. žádný muž nemůže mít v žádném stabilním párování lepší (pro něj) ženu, než je ta, kterou dostal při pánské volence
- 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ů
- Příště budeme mimo jiné probírat algoritmus prohledávání bludiště,
může se Vám hodit, pokud si přečtěte
Beletristické zpracování Ariadnina algoritmu a důkazu jeho správnosti
- přednáška 7.října
- opakování myšlenek důkazů o algoritmu pánské volenky
- Úloha o bludišti a jednoduchý "Ariadnin" algoritmus,
který ji řeší (trasování na konkrétním bludišti).
- Důkaz konečnosti Ariadnina algoritmu
- Pojem invariantu algoritmu
- Důkaz parciální správnosti Ariadnina algoritmu
- Beletristické zpracování Ariadnina algoritmu a důkazu jeho správnosti.
- 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"
programové konstrukce Pascalu jsou strukturované, lze tedy při návrhu programu postupovat "shora dolů"
- Tvar programu v Pascalu
- přednáška 21.října
- Opakování: Proměnná, přiřazovací příkaz,
Strukturované 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. Tvar programu v Pascalu.
- Čí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í)
- Celočíselné typy v Borland Pascalu:
integer, shortint, longint
- 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.
- Typ boolean.
- Program, který testuje, zda číslo na vstupu je prvočíslo.
Pokud jste tak již neučinili, pořiďte si účet v laboratoři Karlín a zaregistrujte se do systému Codex !!!
- přednáška 4.listopadu
přednáška byla suplována
- Podprogramy - procedury a funkce
- Lokální a globální deklarace. Lokální definice zastiňuje globální.
- Podprogramy lokální v podprogramu, raději bychom je neměli (nad)užívat, protože v jazycích odvozených od jazyka C neexistují.
- Předávání parametrů hodnotou a referencí (odkazem)
- Příklady
- Pole, indexový typ, typ složky, přístup ke složce pole pomocí indexového výrazu.
kontrola přetečení indexu, možnost vypnout a zapnout, přepinač R
- Zjednodušená sémantika příkazů read, readln, write, writeln
vstup číselných typů,
formátování výstupů číselných typů
Pokud chcete navštěvovat praktika NPRM047, přijďte nejpozději v týdnu od 9.11. na příslušné praktikum.
Informace o obsazenosti jednotlivých praktik najdete na stránce předmětu
- přednáška 11.listopadu
- Na praktikách NPRM047 jsou ještě volná místa viz stránka
- Faktoriál
- Výpočet kombinačních čísel - není vhodné volat funkci faktoriál, výpočet s prevencí přetečení
- proč není v novějších programovacích jazycích operátor umocňování
- Funkce počítající n- tou mocninu s optimálním počtem násobení (2*log2(n))
- 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ě
- 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
- Obdobně je v případech citlivých na přesnost zobrazení 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
- 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
- "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
- 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.
- Opakování for cyklu, jednoduché příklady
for cyklus je "opakování zadaný počet krát", změna mezí v těle cyklu nemá vliv na počet průchodu cyklem.
Hodnotu řídící proměnné cyklu se v těle cyklu se nesmíme pokoušet měnit - je to krajně nečistý způsob programování, který nebude tolerován. Na tom nic nemění skutečnost, že překladače Pascalu tuto věc nekontrolují a připouštějí.
- Znakové řetězce - stringy, funkce length
- 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říště si zopakujeme použití podprogramů a typy předávání parametrů podprogramům,
přečtěte si před příští přednáškou příslušné partie z knihy P. Satrapy (nebo jiné, kterou používáte jako učebnici jazyka)
- přednáška 18.listopadu
- Opakování
- Podprogramy a jejich význam pro programování. Návrh programu metodou "shora dolů".
- Procedury, funkce, formální a skutečné parametry.
- Předávání parametrů hodnotou a referencí. Jednoduchý příklad.
- Bloková struktura programu a viditelnost objektů
- 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
- Najděte chyby v podprogramu, který má transponovat matici
řešení
- Výčtové typy
- 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.
- Typická reprezentace vektoru jako záznamu o dvou složkách:
pole a jeho skutečně využitá délka.
- 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
- 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
- Úplné a neúplné vyhodnocování booleovských výrazů.
Přepinač B ovlivňujicí činnost překladače Pascalu
- přednáška 25.listopadu
- Programové jednotky - unity, klausule uses, části interface a implementation
- Strukturované a modulární programování
- 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í
- 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ě!
- 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 stringů
- Výstup hodnot typu boolean - normální člověk nepoužívá
- přesměrování vstupu a výstupu při spouštění přeloženého programu mimo ladící prostředí Borland Pascalu
- přednáška 2. prosince
- upozornění na soutěž studentů 1. ročníku v programování,
která proběhne na internetu v pátek 11.12. odpoledne (jsou dvě kategorie - informatici a matematici
- přátelské, ale důrazné upozornění na to, že je nejvyšší čas začít pracovat
- Opakování souborů a jejich významu
- Proměnné typu souboru (a typu, které obsahují soubor jako složkuy) není v Pascalu k dispozici přiřazovací příkaz
(znamenalo by to tiž kopírování souboru) a tedy nelze ani parametry tohoto typu předávat hodnotou
- 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
- Standardní podprogramy pro práci se stringy a komentář k jejich požívání
- 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
- 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"
- Algoritmus pracující v čase n*m 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
- 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
- Paradoxní aspekty pojmu asymptotické složitosti
- přednáška 9.prosince
- opětovné upozornění na soutěž studentů 1. ročníku v programování,
která proběhne na internetu v pátek 11.12. odpoledne
(jsou dvě kategorie - informatici a matematici
- Rekursivní algoritmy a podprogramy
- Rekursivní funkce - mocnina, faktoriál, je 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
- Výstup otočeného řetězce pomocí rekursivní procedury s lokální proměnnou,
implicitně využíváme zásobník volání podprogramů
- 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 nestačí pamatovat si pro každé políčko
zda je ohrožováno, ale stačí pamatovat si
kolikrát je ohrožováno
- 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í
- 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
- přednáška 16.prosince
- Opakování úlohy o osmi (nezávislých) dámách
inkrementální aktualizace "světa", krok dopředu, krok dozadu
- Přímá a nepřímá rekurse, direktiva forward.
- 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?
- 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 zadaného preorder notací
- 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"
- metoda 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
- převod na postfix klikátko
- algoritmus převodu na postfix jde rovnou spojit a algorimem vyčíslování postfixu
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ů
- Prohledávání grafu do hloubky a šířky .
- Společná implementace se seznamy OPEN a CLOSE,
ve které se tyto algoritmy liší jen implementací seznamu OPEN (zásobník/fronta)
- typické implementace zásobníku a fronty (fornta pomocí "zacykleného pole")
- Animace: do hloubky,
do šířky,
tyto animace obsahují (poměrně závažnou chybu) Najděte ji!
- Algoritmus vlny
- prohledávání do šířky bez fronty, přímo do vrchlů grafu se zapisují vzdálenosti od startu
"zpětný chod" pro nalezení nejkratší cesty
- přednáška 6.ledna
Na přednášce pravděpodobně bude
- praktické testy, požadavky, zapisování
- Komentář k programování úlohy o hledání nejkratší cesty dané figury po šachovnici se zakázanými políčky,
šachovnici se zakázanými poli je vhodné si "nakreslit" v editoru a
jednoduše přečíst,
srovnej se čtením seznamu zakázaných políček
- Různé reprezentace grafu,
Matice sousednosti, matice incidence, seznam hran, seznam následníků.
- Mocnina grafu sousednosti - použití pro hledání komponent souvislosti
- Dijkstrův algoritmus pro hledání nejkratší cesty v grafu s nezáporně ohodnocenými hranami
invarianty, složitost - klikátko
- Porovnání použití prohledávání do šířky a do hloubky pro hledání nejkratší cesty
- Dlouhá čísla - reprezentace a aritmetické operace s nimi
- 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
- Velká množina jako pole množin.
- přednáška 13.ledna
- Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti
(program).
- hledání minimální kostry grafu
- Úloha vnitřního třídění - jednoduché algoritmy složitosti O(n2)
efektivnější si necháme na letní semestr:
- přímé zatřiďování
- třídění výběrem
- třídění výměnami - bubblesort, shakesort
Programy
- třetí způsob předávání parametrů v Pascalu - const
- "typované" konstanty (pozor nejsou to konstanty !) jako příjemný způsob inicializace hodnot
proměnných (i strukturovaných) typů
- příkaz case
- konformní schémata polí - rozšíření Pascalu, které umožňuje napsat podprogramy,
který lze předat jako skutečný parametr pole libovolné délky
omezení toho způsobu - je asi lepší je nepoužívat
- 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
- 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.
- unita CRT
Hromadná konzultace ve středu 20.1. od 15:40 v posluchárně S3