ZS 2013/14 Co bylo NMIN101 Programování I paralelka Y

přednáška 2.října

Omlouvám se za neuspořádanost druhé části přednášky, díky závadě jsem nemohl promítat a musel změnit plánovaný obsah přednášky

Ú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 první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 - podrobněji na stránkách předmětu
Všichni studenti, kteří budou navštěvovat tento předmět by měli co nejdříve:
1. nechat si vytvořit účet pro laboratoře v Karlíně (požádáte o to, ve studentské laboratoři Karlín, v přízemí budovy vpravo od vchodu)
2. zaregistrovat se do systému Codex na stránce, učitelé si vás pak stáhnou do svých skupin
O nepovinném předmětu NMIN161 "Praktika z programování pro začátečníky 1 ", jeho cílech a způsobech výuky. Tento předmět začne na ostro v týdnu od 16.října, bylo by však dobré přijít do skupiny, kam chcete chodit, již v týdnu od 9.října na úmluvu nebo se alespoň do té doby ozvat jejímu vedoucímu. Individuální elektronický zápis není dovolen, provede ho hromadně studijní oddělení.
Příklady konkrétních algoritmů:
- Erathosteno síto - algoritmus pro nalezení prvočísel menších než zadané číslo,
  podmínka ukončení, nemusíme násobit, ale jen přičítat dvejnásobek čísla, jehož násobky "vyškrtáváme"
- aritmetické operace v desítkové soustavě
  ukázka toho, "za starého Rakouska" se na školách učil chytřejší algoritmus písemného násobení, který nevedl k potřebě sčítat mnoho čísel
  uvědomte si jak těžké by bylo provádět aritmetické operace v méně šikovných zápisech čísel,
  např. v "římských číslicích"
Úloha o nalezení stabilního párování - zkuste najít algoritmus
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).
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"

Zpět začátek

přednáška 9.října

zařiďte si co nejdříve účet v Karlínských laboratořích a zaregistrujte se v Codexu
O praktiku - pokud chcete chodit, přijďte tento týden na úmluvu nebo dejte vědět vedoucímu - bližší na stránce předmětu
Opakování: pojem algoritmu
Eukleidův algoritmus
- animace1 s rozdílem
- animace2 se zbytkem po dělení
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"
Ú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
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.
Opakování:
- proměnná jako označení místa v paměti, přiřazovací příkaz, typ proměnné, deklarace
- Identifikátor, zápis číselné konstanty, klíčové slovo.
- programové konstrukce: složený příkaz, podmíněný příkaz - úplný a neúplný (nejedoznačnost zápisu)
Jednoduchý program v Pascalu
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ě.
Čísla ve světě, rychlost růstu exponenciely

Zpět začátek

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 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

O předmětu, literatuře, překladačích, praktiku, ....
Čí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.
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.

Zpět začátek

přednáška 30.října

vzhledem k potřebám cvičení se věnujeme více jazyku, k problémům dokazování správnosti programů a jejich efektivnosti se vrátíme později

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í
najděte co nejrychlejší výpočet n-té mocniny pomocí co nejmenšího počtu násobení - jde v čase (2*log₂(n)) dokažte si tento odhad, ještě se k tomu vrátíme
Typ char, funkce ord a chr.
"Zoologie" typů v Pascalu (jednoduché - strukturované, standardní - definované programátorem, ordinální).
Výčtové typy
Ordinální typy - funkce ord, succ, pred, inc, sub
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 nad hlavní diagonálou čtvercové matice
zjednodušený výklad vstupu a výstupu z konzole
read, readln, write, writeln, výstup s formátem

Zpět začátek

přednáška 6.listopadu

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.
Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti (program),
rozmyslete
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.
Kdy použít předávání parametrů hodnotou resp. referencí
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í.

Zpět začátek

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)
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
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
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í
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 řetězců
- Výstup hodnot typu boolean - normální člověk nepoužívá
Standardní podprogramy pro práci se stringy:
+ , lenght, pos, copy, delete, insert
dvě nejdůležitější nám zbyly napříště
a komentář k jejich používání

Zpět začátek

přednáška 20.listopadu

Upozornění na soutěž studentů v prvního ročníku v programování - pátek 6.12.2013

Standardní podprogramy pro práci se stringy:
konverze mezi číselnou hodnotou a jejím zápisem ve stringu
a komentář k jejich používání
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
Shrnutí "nebezpečných" případů při vstupu a výstupu
1. test while not eof(F) při četení čísel z textového souboru
2. čtení stringů
3. slepení hodnot typu integer při výstupu bez formátu
4. nevyprázdění bufferů výstupního souboru na konci programu
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
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

Zpět začátek

přednáška 27.listopadu

Upozornění na soutěž studentů v prvního ročníku v programování - pátek 6.12.2013

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.

"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"
Opakovánií - pojem rekurse
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ý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 rozkladů zadaného čísla na součet sčítanců
- rekursivní řešení
- nerekursivní řešení
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
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)
Animace: do hloubky, do šířky, tyto animace obsahují (poměrně závažnou chybu) Najděte ji!

Zpět začátek

přednáška 4.prosince

Upozornění na soutěž studentů v prvního ročníku v programování - pátek 6.12.2013

Opakování:
Společná implementace se seznamy OPEN a CLOSE,
ve které se tyto algoritmy liší jen implementací seznamu OPEN (zásobník/fronta)
Animace: do hloubky, do šířky, tyto animace obsahují (poměrně závažnou chybu)

Končí dříve než vypráznili seznam OPEN - to znamená, že algoritmus, kterým by byly řízeny by na modifikovaných datech dal špatné výsledky
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
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
opakování : úloha o nezávislosti dam
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
Komentář k úlohám se šachovnicí:
Nezávislost, dominance, nezávislá dominance; nejkratší cesta;prostý průchod šachovnicí;
tvar šachovnice: čtverec, obdélník; rovinnná, válec, pneumatika, Möbiuv list;
prázdná, se kázanými políčky;
figury: dáma, věž, střelec, jezdec, "obecná figura", různé exofigury (maharádža, slon);
......
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, seznamy následníků (lze "dát do jednoho pole")
Mocnina grafu sousednosti - použití pro hledání komponent souvislosti
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
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 či 8 chodit)
- Triviální algoritmus složitosti n³*m³ ,
  ani chytrá implementace naivního algoritmu příliš nepomůže
- Algoritmus se složitostí n*m²
  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

Zpět začátek

přednáška 11.prosince

Opaková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 (nemusí vám ve Windows 7 či 8 chodit)
- Triviální algoritmus složitosti n³*m³ ,
  ani chytrá implementace naivního algoritmu příliš nepomůže
- Algoritmus se složitostí n*m²
  využívající předvýpočet "počtu jedniček pod danou jedničkou",
- 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
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!
Velká množina jako pole množin.
Dijkstrův algoritmus pro hledání nejkratší cesty v grafu s nezáporně ohodnocenými hranami
invarianty, složitost - klikátko
pamatování si předchůdce - zpětný chod
Floyd-Warshalův algoritmus pro nalezení všech vzdáleností v grafu, doplnění, aby hledal nejkratší cesty
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
  algoritmus převodu na postfix lze spojit s algoritmem vyčíslování postfixu - vygenerovaný postfixový zápis přímo posíláme k vyhodnocení
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ů

Zpět začátek

přednáška 18.prosince

komentář k praktickým testům a přihlašování na ně
Opakování reprezentace aritmetických výrazů pomocí stromu, aritmetických notací a algoritmů vyčíslování jejich hodnoty
datová reprezantace binárního stromu pomocí pole
postavení stromu z prefixové notace
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):
1. přímé zatřiďování
2. binární zatřiďování - polohu najdeme v logaritmické čase, ale posun pole je lineární
3. třídění výměnami - bubblesort, shakesort implementace bez pamatování si místa poslední výměny je programátorská nešikovnost
zdrojové texty procedur realizujících jednotlivé třídící algoritmy
heapsort
- 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
Časová a paměťová složitost heapsortu

Zpět začátek

přednáška 8.ledna

Pravděpodobný obsah přednášky

komentář k praktickým testům a přihlašování na ně, průzkum zájmu o termíny
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!
Přepinače kompilátoru
standardní unity Borland Pascalu
unita CRT
reprezentace "dlouhých čísel" a programování operací s nimi
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ě reprodukovat
- politická aktualita
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ě
quicksort
Časová a paměťová složitost quicksortu, různé optimalizace
porovnání algoritmů heapsort a quicksort
algoritmus vnitřního třídění sléváním - mergesort
netřídí na místě
zdrojové texty procedur realizujících jednotlivé třídící algoritmy
Důkaz tvrzení, že neexistuje žádný algoritmus vnitřního třídění, kterému by v nejhorším případě stačilo méně než n*log(n) porovnání
Obdobné tvrzení platí i pro průměrný případ (myšlenka důkazu), ale pro nejlepší případ neplatí.

NMIN101 Programování I paralelka Y ZS 2013/14

Co bylo na přednáškách

paralelka Y - středa 10:40 M1

Soutěž v programování pro studenty prvního ročníku