• Studenti jsou povinni pravidelně číst předmětové aktuality níže.
  Dozvíte se tam například o mimořádnostech ve výuce, plánované termíny testů a podobně...
• Dále je pro (jakékoliv) případné dotazy, které nemohou být rozumně zodpovězeny během cvičení, zřízeno Diskusní fórum předmětu IB000.
  Cvičící budou dotazy na fóru promptně zodpovídat. Na samostatné emailové dotazy týkající se obecných otázek nebude vůbec odpovídáno, neboť to nic nepřináší ostatním studentům.

Pro hrubou představu o průběhu semestru máte zde zpřístupněny i aktuality minulého roku, ale nepleťte si je se současným semestrem.

Kterak studovat

IB000 = učebnové přednášky + povinná učebnová cvičení + domácí procvičení s online odpovědníky.

Jelikož předmět IB000 je poměrně obtížný, zvláště pro studenty, co se příliš "nekamarádí" s matematikou, věnujte mu už během semestru patřičnou pozornost i mimo samotné přednášky a povinná cvičení. Berte proto na vědomí několik dalších rad do studia:

• Zapojte se sami či s kamarády do domácího řešení procvičovacích odpovědníků po jednotlivých lekcích, bude se vám to hodit! Uvidíte, jak různorodě lze nabyté vědomosti uplatnit při řešení příkladů (a i když pak v praxi budete narážet na jiné problémy, umění aplikovat teoretické vědomosti na řešení libovolných konkrétních zadání vám zůstane...).
• Také si každý sám vyzkoušejte, jakou výraznou pomoc při studiu vám mohou přinést předmětová diskusní fóra. Takže čtěte diskuse (kde mnohé vaše nejasnosti již mohou být vysvětleny) a případně se sami ptejte na další problémy. Snažte se však udržovat diskusní vlákna přehledná, tj nejprve se dívejte, zda už k vaší tématice je založeno vlákno jinými, a přispívejte do něj. Pokud je téma nové, volte název zakládaného vlákna výstižně, aby ostatní hned poznali, o čem je řeč, a diskuse se rozvinula. Nakonec nemusíte vždy čekat až na rady cvičícího, mnohdy i spolužáci poskytnou hodnotné odpovědi a vysvětlivky...
• Samotná osnova IB000 přímo odkazuje na materiály z přednášky, odpovědníky k procvičení v jednotlivých lekcích, doplňkové materiály na internetu a také odkazy na hodnotná diskusní vlákna z minulých let vztahující se ke konkrétnímu učivu. (Jenodušší to už snad ani nemůžete mít.)

Účast na přednáškách sice není povinná, ale je důrazně doporučovaná, neboť některé přednášené myšlenky ani nelze pořádně zachytit na papíře a slovní podání je nejlepší. Pro případ výjimečné neúčasti ještě budete mít k dispozici online záznamy přednášek, ale nespoléhejte jen na ně.

Testy a zkoušky

Komplexní hodnocení ukončení předmětu se skládá z následujících:

• Povinné semestrální bodované činnosti (testy) - 3x domácí online testy po 8 bodů každý, školní semestrální test 1x za 12 bodů (jako domácí testy, ale hlídané), drobné testíky na cvičeních za celkem 12 bodů počítaných dohromady jako jedna akce (organizují si sami cvičící), domácí písemný úkol 1x za 16 bodů (poměrně obtížný). Do výsledku zkoušky či zápočtu se započítává součet čtyř lepších nezáporných z těchto šesti činností (bez možnosti opravy - proto jsou počítány jen lepší výsledky).
  • Pro dobrou šanci na složení zkoušky doporučujeme získat alespoň 26 semestrálních bodů.
  • Ony školní test, testíky na cvičeních a písemný úkol nazveme prioritními (neboť je u nich obtížnější podvádět).
• POZOR, pro připuštění ke zkoušce či k zápočtu je nutno získat aspoň 8 prioritních bodů, tj. součet nezáporných zisků ze školního testu plus testíků na cvičeních plus domácího úkolu musí být alespoň 8 bodů (počítají se do toho i případné mimořádné bonusy). Z tohoto pravidla nejsou možné výjimky ani nebudou žádné opravy!
  • Prostě kdo toto (nakonec velice snadné) pravidlo nesplní, v předmětu končí - to proto, aby všichni studenti byli nuceni studovat průběžně.
• Závěrečná povinná zkouška testem na počítači na 36 bodů, která se koná pod dozorem v učebně. Požadavkem pro úspěšné složení je zisk aspoň 51 bodů v součtu s celkovým semestrálním výsledkem. Samozřejmě je nejprve nutno splnit také pravidlo prioritních bodů.
  • Příklady na této zkoušce budou obdobné cvičícím odpovědníkům a domácím i školním testům, ale vše pod dozorem, obtížnější a s vyšším bodovým hodnocením 6x6. Rozhodně tam nečekejte nějaké snadné tipovací testy.
• V případě úspěchu u online zkoušky následuje (nepovinná) písemná zkouška za až 30 bodů, obdobná uvedeným starším písemkám. Písemná zkouška přitom nemá žádné záporné body, pohoršit si už nemůžete a složení zkoušky máte po počítačové části jisté. Celkový součet pak určí známku E-A.
• Některé studijní programy mají určeno předmět ukončit zápočtem (vybrat si však nemůžete). Zde platí stejné podmínky semestrálního hodnocení. Mimo povinného zisku 8 prioritních bodů pak k udělení zápočtu stačí dosáhnout semestrálního výsledku aspoň 29 bodů.

Bodování na cvičeních:

• Povinná účast na cvičeních je místo tupého odškrtávání jmen v seznamu ohodnocena body za pravidelné lehké testíky (do celkového součtu 12 bodů). Tyto testíky si organizují a opravují cvičící sami podle svého a stejně jako jiné semestrální testy z nich není možná oprava.
• Testíky na cvičeních budou zpravidla tři ve cvičeních 2,3,4 nebo 2,3,5, každý po 4 bodech. V některých cvičeních toto může být jinak, ale to vám cvičící první týden oznámí. V případě omluvené neúčasti (v IS) budete mít možnost psát náhradní testík v posledních cvičeních, po individuální dohodě.
• Pokud někdy nemůžete na své cvičení, máte možnost si účast nahradit na stejném pořadovém cvičení skupiny, co se s váma střídá ob týden ve stejném čase (tj. týden před nebo po). Pro náhradu na cvičení v jiném čase musíte získat souhlas příslušného náhradního cvičícího (aby na cvičení bylo místo). To však bude povolováno jen výjimečně - jste na denním studiu a během celého týdne musíte mít na školu čas!
• Cvičící mohou nejlepším z vás udělit na cvičení bonusové body za mimořádnou aktivitu a znalosti, avšak tyto body nelze udělovat na posledních dvou cvičeních! (Bonusové body se připočítávají k prioritním, viz dole.)

Možnosti oprav hodnocení:

• Jak je uvedeno, semestrální testy nelze skládat opakovaně (jen je možnost jejich složení v náhradním termínu pro omluvenky zadané v IS, jak je psáno níže). Pozor, to se týká i povinných prioritních bodů, kde také nelze jejich nenaplnění nijak opravit (ostatně možnost získávat je ze třech nezávislých zdrojů je dostatečnou alternativou oprav).
• Na druhou stranu v případě splnění prioritních semestrálních bodů lze celkový semestrální výsledek opravit následovně (platí jak pro zkouškové ukončení, tak i pro zápočtové): Po neúspěšném složení zkouškového testu bude jeho výsledek plus třetina původně získaných prioritních bodů vašim opraveným semestrálním hodnocením - samozřejmě jen pokud si tím pomůžete. Cenou za tuto opravu je vyčerpání jednoho zkouškového termínu a udělení F. Vše tak bude počítáno automaticky bez potřeby vaší iniciativy.
• Samotné zkoušky na počítači je (po udělení F) samozřejmě možné opravovat na dalších termínech podle běžných zvyklostí. Pro vylepšení výsledku >F z počítačové zkoušky však slouží následná písemná zkouška, která je finální a hned po ní dostáváte známku.

Termíny a náplň testů, písemek a zkoušek

Termíny a pokyny naleznete včas na tematickém fóru aktualit našeho předmětu  https://is.muni.cz/auth/df/aktuib000/. Online testy se vám také budou přímo objevovat v IS https://is.muni.cz/auth/el/1433/podzim2013/IB000/odp/ s příslušnými daty skládání.

Náplň všech semestrálních testů s výjimkou písemného domácího úkolu odpovídá příkladům z cvičných odpovědníků (jen pochopitelně dostanete jiné varianty a občas i nový typ příkladu). Stejné je to i s počítačovou částí zkoušky. Jedinou formální odlišností z nich je způsob skládání u školního semestrálního testu, kdy odpovědi místo ťukání do počítače zatrháváte na speciální odpovědní arch, který se pak oskenuje. Podstatně odlišná náplň pak je u písemného domácího úkolu a u navazující písemné zkoušky, v obou těchto případech budete (na papír) řešit zapeklité příklady a psát matematické důkazy svého řešení.

Náhradní termíny testů

Každý ze semestrálních testů lze nahradit, pokud jste se řádného termínu nemohli zúčastnit a máte na to omluvenku zadanou v IS. Mi žádné omluvenky neposílejte, stejně je hned smažu! Důležité je jen to, co bude jako omluvenka zapsané v IS v době, kdy si budete chtít náhradu složit.

Termín(y) náhradního testu bude vyhlášen nejspíše někdy ke konci semestru a pro písemné testy až na začátku zkouškového období. Počítejte s tím a čekejte. Stejné se týká i domácího úkolu, pro který dostanete nejen nový termín odevzdání, ale i nové zadání. Mimo to u domácích online testů obvykle lze test neoficiálně nahradit zhruba týden po termínu, ale to je bez záruky a je na vás si to pohlídat (a nepište mi o tom žádné emaily).

Pomůcky k testům a zkouškám

Ohledně dovolených pomůcek a nápověd ke všem testům a zkouškám pod dozorem je jednoduchá politika:

• Nesmíte používat žádné kalkulačky, mobily ani jinou výpočetní techniku. Veškeré pomocné výpočty musíte provádět sami ručně, nebude to obtížné. (Jen pokud má někdo zdravotní indikaci vylučující ruční provádění výpočtů, může požádat o výjimku.)
• Nemáte dovoleno používat během testu žádné výukové materiály, jedinou povolenou nápovědou je jeden list A4 s vlastnoručně psanými (ne tištěnými) poznámkami k učivu.
• Ke každému hlídanému testu či zkoušce si navíc musíte přinést ISIC kartu pro ověření identity.
• A ke každé počítačové zkoušce si dopředu musíte zjistit svůj login na fakultních strojích a umět se v příslušné učebně přihlásit!

Vyhodnocení testů a zkoušek

Všechny výsledky vašich testů i zkoušek se dříve či později objeví v IS MU, to jest jak jejich obodování v příslušném zápisníku, tak i samotné opravení odpovědí a chyb pod správou odpovědníků v IS. (Ano, i písemné testy se nakonec scanují do speciálních odpovědníků v IS, takže každý pak budete mít přístup ke všem svým úspěchům i chybám.) Proto se zbytečně nedožadujte svých opravených testů, prostě jakmile budou připraveny, objeví se vám v IS samy a budete si je moci prohlédnout.

• Online skládané testy se pochopitelně vyhodnotí samy ihned a budete vidět své body. Avšak své chyby si budete moci prohlédnout až později, kdy skončí skládání testu všemi ostatními studenty. To se protáhne především u semestrálních domácích testů až na několik dní čekání. Musíte být trpěliví, žádné výjimky k předčasnému prohlížení nebudou.
• U písemných testů budete muset čekat ještě déle, než budou písemně opraveny a pak nascanovány do IS. To nejde urychlit.
• Pokud nebudete spokojeni s udělenými body, budete si muset nejprve počkat na zpřístupnění opraveného testu a zjistit sami, kde jste udělali chybu. (Nepište žádné emailové dotazy dříve, nebudeme na ně reagovat.) Pokud ani po vlastní netriviální snaze nebudete vidět, kde jste vlastně chybu v příkladu udělali, zeptejte se poté cvičících na diskusním fóru v IS, tam váš problém určitě rychle vyřeší.
• Reklamovat ohodnocení testu lze jen v jediném(!) případě -- pokud vaše objektivně správná odpověď bude ohodnocena jako chybná. Zdůrazňuji slova "objektivně správná", neboli k případné reklamaci budete muset přiložit screenshot chybného ohodnocení i důkaz správnosti vašeho výsledku. (Pokud si s důkazem nebudete vědět rady, opět se obraťte na cvičící.) Reklamaci pak pošlete emailem přímo mi. V žádném případě ale nelze reklamovat udělený počet bodů u automaticky vyhodnocených testů, body jsou udělovány zcela objektivně všem stejně a nelze se separátně bavit o žádné "téměř správné odpovědi" ani o "chybící desetince bodu k limitu", je jen odpověď přesně správná nebo chybná. V této souvislosti zdůrazňuji, že u online testů se za každou špatnou odpověď udělují záporné body (aby se test nezvrhl na tipování), obvykle -30% hodnoty celého příkladu, a tyto záporné prémie se sčítají přes všechny otázky v příkladě, takže to může znamenat velmi citelné postižení. Prostě pokud nevíte, raději odpověď nevyplňujte.

Technické poznámky k online testům na IS

Třebaže skládání testových odpovědníků v IS vypadá docela intuitivně a nekomplikovaně, je zde několik skrytých zádrhelů, které vás (i coby informatiky) u ostrého testu mohou nepříjemně překvapit a zbytečně vám pokazit výsledek. (Je doufám zbytečné zdůrazňovat, že takové zádrhele nelze následně reklamovat či opravovat...) Proto si dobře přečtěte následující rady:

• Každý ostrý test lze spustit a uložit jen jednou! Proto nikdy neklikejte na spouštěcí tlačítko vícekrát, i když spuštění testu trvá dlouho. Také si dobře pohlídejte, že vám během spuštěného testu nespadne prohlížeč ani internetové spojení (wifi a komunitní sítě nejsou dobrou volbou, běžte raději do školy). Každý takový technický problém totiž znamená ztracení testu nadobro. Pokud přesto ostrý test kvůli technickým problémům ztratíte před uložením, budete mít obvykle možnost jej spustit ještě jednou (potřetí už ne!), na to si už ale najděte stabilní počítač a spojení.
• Aby se odpovědník správně spustil, musíte mít v prohlížeči podporu javascriptu (doporučujeme Firefox). Správné spuštění ostrého odpovědníku poznáte snadno podle toho, že nad web stránkou naskočí odpočítání času. Některé prohlížeče však také mohou bez varování nenahrát potřebné javascriptové knihovny, bez kterých se některé otázky nevyhodnotí vůbec. Dotčené otázky samy se na takový problém snaží upozornit alertem. Pokud odpovědník správně nenaskočí nebo se mu nenačtou některé obrázky či knihovny, nikdy(!!!) nesmíte mačkat tlačítko Reload, o test byste taktéž nadobro přišli. Místo toho skoro vždy ke správnému načtení a spuštění neúplného odpovědníku pomůže stisknout v testu tlačítko průběžného uložení výsledků. To si dobře zapamatujte.
• Do odpovědí vždy zapisujte jen holé konečné výsledky, které se v daném příkladě očekávají. Typicky jde o číselné výsledky, které zapisujte jen jako celá čísla, tj. jen číslicemi a případným znaménkem. Určitě nezkoušejte psát třeba "1+1" nebo "6/3" nebo "(2)" místo správné odpovědi "2", žádné takové mezivýsledky nebudou uznány, neboť IS kontroluje číselné odpovědi na textovou shodnost. (Jiné otázky s netriviální syntaxí zápisu výsledku, kde se očekávají třeba funkce nebo formule, mají svou vlastní nápovědu i okamžitou kontrolu syntaxe.)
• Zkuste si pro jistotu nejprve spustit několik cvičných odpovědníků na počítači a prohlížeči, kde se chystáte skládat ostrý test. Na jiném počítači vás třeba může překvapit špatná čitelnost fontů v prohlížeči; v minulosti už měli studenti někdy problémy s chybícími znaky lomených závorek, se záměnou písmenek "g" a "q", nebo se záměnou "-" a tečky jako "krát". Pokud si nejste jisti zapsaným, zvětšete si v prohlížeči font až do absurdních velikostí, je to lepší než pak smutnit nad zápornými body. A také si dejte pozor, abyste výsledky testu zapisovali normálním ascii či utf kódováním latinky, už se vyskytl i odpovědník vyplněný kanji fontem, který pochopitelně IS neuznal.
• Nakonec si dejte i pozor, aby během skládání odpovědníku plynul systémový čas počítače běžným tempem (rozhodně čas neměňte), neboť vás náhlé změny času taktéž mohou o test připravit.

Další možná specifická úskalí domácích testů

Jak si můžete všimnout výše, část semestrálních testů IB000 budete skládat v určenou dobu bez dozoru online doma nebo u školních počítačů. Tento fakt může vyvolávat některé otázky, na které se pokusíme dopředu odpovědět zde.

• Přestože nad vámi nebude nikdo bdít, stále jste povinni řešit domácí testy samostatně a v případě zjištění porušení této povinnosti vás neminou sankce jako u opisování ve škole.
• Avšak nejen možné sankce by vás měly vést k poctivosti. Uvažte, že hlavní "příděl" bodů potřebných k úspěchu v předmětu získáte na počítačové zkoušce (36 z potřebných 51), která se bude skládat ze stejných odpovědníků, ale již pod přísným dozorem. Během semestrálních testů, při započítání 4 lepších ze 6, máte možnost až 2 testy zkazit zcela bez následků, kdežto u počítačové zkoušky už tři nebo i jen dva zkažené odpovědníky znamenají definitivní konec! Proto ve vlastním zájmu využijte možnost skládat i ostré domácí testy v klidu sami a bez pomoci, ať se tím dobře připravíte na počítačovou zkoušku, včetně nevyhnutného stresu z faktu, že teď to už je "naostro".
  (Nemluvím tady "do větru", statistický pohled na výkony studentů na podzim 2008 ukázal zhruba stovku(!!!) studentů, kteří měli perfektní výsledky u všech domácích testů a zároveň mizerné výsledky u hlídaného školního testu - zrovna tito studenti pak v drtivé většině předmětem neprošli, neboť dalších potřebných zhruba 20 bodů z počítačové zkoušky ani opakovaně nedokázali získat. Proč asi?)
• A jak je to s účastí na domácím testu? Skládat jej pochopitelně můžete v určenou dobu kdekoliv, takže i když nejste zrovna ve škole, termín nezameškáte. Pokud vám přesto něco zabrání v určenou dobu test složit, bude test ještě jednou na chvíli otevřen s jistým časovým odstupem (pohlídejte si to sami) a budete mít možnost přístupu znovu, bez potřeby omluvenky. Pokud však ani dodatečný termín nevyužijete, nebo se vám byť jen z technických důvodů nepodaří k testu přihlásit ("spadne to"), tak pro další možnost složení testu už budete muset prokázat omluvenku v IS na celou dobu řádného termínu testu i dodatečnou dobu. Na to pozor...
• Poslední poznámka se opět týká problematiky "spadlých" domácích testů. Pokud k takovému pádu během vyplňování a před konečným odesláním odpovědí dojde, již se nebudete moci ke stejnému testu vracet. Aby vás toto chování IS zbytečně nepoškodilo, bude každý domácí test "zdvojen" a vy budete moci jej okamžitě spouštět s novými otázkami. Nepokoušejte se však tento mechanizmus zneužívat k "opravě" špatně napsaného testu, neboť ze všech kopií téhož testu se vám započítá ten nejmenší bodový zisk!  Po lopatě, druhým spuštětím téhož, už jednou vyhodnoceného, testu si nemůžete nijak pomoci, jen se poškodit. A pokud k tomu dojde, na vaše nářky, že chcete zpět ty první vyšší body, nikdo nebude odpovídat. 

Vedlejší informace

Doplňkové studijní materiály:

Tyto materiály jsou jen podpůrné, nejsou nadále udržovány a tudíž se mohou líšit od vykládaného učiva. (Učivo z přednášky má samozřejmě přednost.) Pokud je něco v těchto materiálech v rozporu se znalostmi vyučovanými a požadovanými ke zkoušce v aktuálním semestru, ignorujte příslušnou část těchto materiálů. Rozhodně těmito doplňkovými materiály nelze argumentovat u opravování zkoušek.

Velká část pěkných příkladů v prvním adresáři pochází od Mgr. Holečka, bývalého cvičícího.

Dobrovolné bonusové úkoly

Jako doplněk k běžným (povinným) testům a zkouškám mají mimořádně aktivní studenti v předmětu IB000 možnost získat bonusové body, které se jim přímo připočtou k semestrálnímu hodnocení. Jejich výše může být kdekoliv mezi 1 až 99 bodů, ale je třeba zdůraznit, že bonusové body mohou být uděleny skutečně jen za mimořádné aktivity a přínosy k výuce. Aktuální možnosti zisku bonusových bodů jsou vyhlašovány během semestru, zde jen obecně nastíníme hlavní myšlenky jejich přidělování.

• Nejdůležitějším pravidlem je, že bonusové body nejsou nárokové. To znamená, že o jejich přidělení a výši vždy rozhoduje vyučující až následně, po zhodnocení mimořádnosti přínosu a srovnání s výkony ostatních studentů. Ostatně toto odpovídá významu slova "mimořádné". (Jsou to vlastně "bonbónky" pro nejlepší studenty.)
• Standardní možností zisku bonusových bodů je řešení dobrovolných bonusových úkolů, které budou vyhlášeny během prvních týdnů semestru. Úkoly se týkají obtížných matematicko-informatických problémů, k jejichž úspěšnému řešení je třeba vynaložit úsilí a prokázat schopnosti výrazně přesahující běžnou úroveň předmětu. Odměna pro nejlepší pak stojí za to.
• Dále je možno (a stávalo se to v minulých letech) udělit bonusové body za objevení a podrobnou analýzu případných chyb či nedostatků v předmětových testech či studijních materiálech. Zahrnuje to jak odborné chyby, tak i technické aspekty a problémy, ale v každém případě je tam důležitý důraz na část "podrobná analýza", která má zkoumat příčiny i navrhovat řešení.
• Příjemnou vlastností bonusových bodů je, že se připočítávají k prioritním testům...

Přejeme hodně štestí, píle, dobrých nápadů a ve výsledku i mnoho bonusových bodů ke zkoušce! A nezapomeňte, pokud Vás některý obtížný úkol zaujme a přijdete na pěkné výsledky, nejen že budete mít body navíc, ale především si už na počátku studia "přičichnete" ke skutečné vědě a získáte tak s předstihem skvělu možnost se zapojit do řešení opravdu zajímavých vědeckých problémů.

Odevzdávejte řešení do 19.11., přitom do 5.11. získáte +50% bodů

Pozorně čtěte obecné poznámky k úkolům dole!

Obecné poznámky

Řešení odevzdávejte celé v jednom PDF souboru obsahující vše podstatné do příslušné odevzdávárny odkazované níže.

Bonusové úlohy jsou docela obtížné a neočekáváme, že by každý musel vyřešit úplně všechno v jedné úloze. I dostatečně dobrá částečná řešení budou odměněna, pokud obstojí v porovnání s výkonem ostatních studentů na bonusech.

S upřesňujícími dotazy se obracejte na cvičící v diskuzi na IS.
Nezapomínejte, že se jedná o vaši vlastní tvůrčí práci! Při opodstatněném podezření z opisování vám nebudou uděleny žádné body. (Respektive z každé třídy příliš podobně vypadajících řešení bude kladně ohodnoceno jen to, které bylo odevzdáno první. V extrémních případech můžeme sáhnout k záporným prémiím a nebo dokonce pak může být přijímání veškerých řešení předčasně zastaveno.) Také nebudou hodnocena řešení, které nevyhoví zde uvedeným formálním specifikacím.

Ve správně zpracovaném projektu očekáváme, že nejprve teoreticky analyzujete problém; poté popíšete slovně postup / algoritmus, který použijete na jeho řešení, a nakonec shrnete všechny dosažené výsledky. Při teoretickém řešení formálně sepište použitá tvrzení a všechna vaše nová tvrzení korektně dokažte. To ostatně znáte z prvních dvou lekcí. Při "počítačovém" řešení algoritmy popisujte podle formálních zásad zavedených v desáté lekci a také co nejlépe zdůvodněte jejich správnost. Jako příloha (v tomtéž PDF souboru) musí být zahrnut výpis vašeho programového kódu s komentáři, pro naši kontrolu (ten ale nenahrazuje výše zmíněný popis algoritmu!). Na programovacím jazyku nezáleží. Přiložte jen ten "výkonný" kód, nezajímají nás hlavičky knihoven ani vstupně/výstupní operace. A určitě nikde nepřikládejte samotný program - výpočty provádíte jen sami a nás musíte textem přesvědčit, že vám to funguje a dosáhli jste výsledky.

Důležitá poznámka se také týká využívání cizích zdrojů. Ne, nemáme nic proti tomu, když si pomůcky pro řešení projektu vyhledáte v literatuře či nejspíše přímo na internetu. V praxi přece také nebudete všechno řešit sami od začátku, ale s výhodou využijete již nalezené poznatky, takže učit se vyhledávat potřebné informace je také součástí výuky. Je však vždy nutné úplně citovat všechny zdroje, ze kterých jste čerpali poznatky (nejlépe formou funkčního www odkazu). Takže na toto myslete, neboť zatajení citací je víc než dostatečným důvodem k zamítnutí vašeho řešení. A rozhodně neoceníme, pokud si pod "využíváním cizích zdrojů" představíte prosté opsání programu řešícího projekt, třeba od spolužáka. Vaše řešení projektu by mělo být skutečnou "nadstavbou" nad obecně dobře známými poznatky.

Mnoho zdaru a zábavy!

Představme si následující úkol: Je dán hrací plán s 2n+2 hracími poli - čtverečky v jedné řadě. Prvních n čtverečků je obsazeno černými kameny, následujících n polí má bílé kameny a poslední dva čtverečky jsou prázdné. Dovoleným tahem hry je vždy zvednout dva sousední kameny a ve stejné pořadí je položit na aktuálně volná hrací pole. Cílem hry je dostat se do stavu, kdy první dva čtverečky jsou volné a na zbylých jsou kameny na střídačku bílý-černý-bílý-černý-... atd. Viz jednoduché schéma:

a) Pro začátek matematicky dokažte, že cíle nelze dosáhnout na méně než n tahů.

b) Pokuste se najít aspoň jedno řešení pro každé obecné n na co nejméně tahů (jak blízko se dostanete dolní hranici n tahů?). Své řešení precizně zapište matematicky nebo formou jednoduchého algoritmu. Nezapomeňte přidat důkaz jeho správnosti.

c) Alternativně můžete hrubou silou na počítači hledat všechna optimální (tj. na nejmenší počty tahů) řešení pro konkrétní malé hodnoty n. Jak vysoko se s hodnotou n dostanete a jaké počty všech optimálních řešení dostanete? Při řešení této části úkolu (není povinná pro ty, kteří raději matematiku než programování) musíte poctivě strukturovaně slovně popsat svůj algoritmus, dokázat jeho správnost a pokusit se nalézat různé způsoby zrychlení jeho výpočtu, abyste se dostali k vyšším hodnotám n než ostatní... V řešení nechceme dostávat váš výsledný program, nýbrž přehlednou tabulku dosažených hodnot - počtů optimálních řešení úkolu a délek výpočtu.

d) Chcete-li řešit ještě více, zkuste přirozeně zvětšit počet prázdných polí na 3 za sebou (celkem 2n+3 polí) a jedním tahem přenášet 3 sousední kameny se zachováním jejich pořadí. Co se pak změní v odpovědích na předchozí otázky? (Tuto část má cenu řešit teprve až vyřešíte dva z úkolů a,b,c...)

e) A pokud máte ještě chuť řešit něco dále, zkuste si prostě vymyslet vhodnou netriviální dvourozměrnou analogii tohoto úkolu (nejspíše s přenášením 2x2 kamenů) a něco hezkého o ní dokažte.

V kombinatorické geometrii je velmi dobře známý problém, kolik barev je třeba na obarvení všech bodů roviny tak, aby žádné dva body ve vzdálenosti 1 neměly stejnou barvu: http://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem

Vašim úkolem je zkoumat rozšíření tohoto problému, kdy zakážeme stejné barvy dvojicím bodů ve vzdálenostech 1 a 2. Kolik je pak třeba barev na všechny body roviny?

a) Pro začátek ukažte nějak jednoduše (třeba s využitím výsledku pro vzdálenost pouze 1), že stačí konečně mnoho barev. To je jen zahřívací kolo, které samo o sobě na bonus nestačí, ale je potřeba jej v řešení mít.

b) Najděte konfiguraci ("konečný obrázek") bodů, která vynucuje co nejvíce barev. Nezáleží, jak tu konfiguraci najdete, jen musíte dokázat, proč na tyto vybrané body je potřeba mnoha barev.

c) Pokuste se nalézt netriviální horní odhad, tj. obarvení roviny co nejméně barvami takové, že žádné dva body ve vzdálenosti 1 ani 2 nejsou stejné barvy.

d) A pokud vám ještě nestačí, zamyslete se, jak se úloha změní, pokud zakážeme stejné barvy ve vzdálenostech 1 a d, kde d>1 je nějaké reálné číslo. Opět vždy bude stačit konečně mnoho barev. Dokážete si však vhodnou volbou d "pomoci" k lepšímu dolnímu nebo hornímu odhadu?

Jelikož i původní problém se vzdáleností 1 je dosud nevyřešen, skutečně neočekáváme úplné řešení ani zde. Avšak pohrajte si a zkuste, kam se dostanete. Body se budou udělovat relativně podle toho, o kolik lepší budete než ostatní řešitelé.

OBSAH

Jak sami poznáte, studium informatiky neznamená jen "naučit se nějaký programovací jazyk", nýbrž zahrnuje celý soubor dalších relevantních předmětů, mezi nimiž najdeme i matematicko--teoretické (formální) základy moderní informatiky. Právě odborný nadhled nad celou informatikou včetně nezbytné formální teorie nejspíše odliší řadového programátora, kterých jsou dnes spousty i bez VŠ vzdělání, od skutečného a mnohem lépe placeného IT experta.

A na tomto místě nyní přichází náš předmět Matematické Základy Informatiky, který vás právě na studium těchto formálních základů moderní informatiky připraví.
Jak také během studia tohoto předmětu poznáte (a ti méně šťastní až s překvapením u zkoušek), vlastně vše, k čemu naším předmětem IB000 směřujeme, se dá neformálně shrnout slovy "naučit se přesně vyjadřovat a být si svými tvrzeními naprosto jisti" a analogicky "naučit se navrhovat správné algoritmy a být si i svými programy naprosto jisti". (Z pohledu programátora-praktika se sice toto může jevit jako nedostižná chiméra, ale určitě není zbytečná námaha se o to aspoň pokusit.)

Takže s chutí do studia první lekce - a nelekejte se velmi formálního začátku, je nezbytný a po něm hned přijdou už přístupnější a zajímavější pasáže...
Zde máte slidy lekce, přičemž rozsáhlejší popis poznatků najdete v první části studijního textu (a také se můžete podívat na video z přednášky).

Samostatné procvičení učiva - odpovědníky

Jelikož je náš předmět obtížný, zvláště pro studenty, kteří na střední škole matematice až tak neholdovali, očekáváme od začátku, že se zapojíte aktivně do využívání poskytnutých elektronických výukových materiálů. Mimo čtení a případný tisk výukového textu a jednotlivých slidů to především znamená aktivní vyplňování cvičebních odpovědníků na IS. Ty by měly spolu s cvičeními (podívejte se níže na náplň cvičení) prakticky prozkoušet, jak jste schopni aplikovat vyučovanou látku k řešení problémů. Tak jen do toho, hned uvidíte své výsledky!

Pro začátek se v příkladech podíváme na úvodní výrokovou logiku, které musíte dobře porozumět. U pravdivostních tabulek o tom nepochybujeme, úpravy logických formulí by také neměly činit velké potíže. Obzvláště však upozorňujeme na nutnost pochopení významu implikace, neboli matematického tvrzení formulovaného stylem "jestliže platí předpoklad, pak platí závěr" (sekce 1.2). I přes všechno vysvětlování okolo stále mnohým studentům činí velké problémy pochopit, že třeba i následující tvrzení ja matematicky pravdivé:  Je-li n přirozené a zároveň n<0, tak n=0.5. (Proč? Přece 0.5 není přirozené ani záporné...)

Očekáváme rovněž, že své dojmy a hlavně případné problémy s řešení odpovědníků budete diskutovat mezi sebou a s cvičícími prostřednictvím předmětového diskusního fóra. Nechť se živá a podnětná diskuse rozproudí dříve než v předvečer prvního testu.

Diskuse o látce

• Následující starší diskusní vlákna, nahrazující učebnová cvičení v minulých letech, by i vám mohla pomoci se vypořádat s látkou a příklady této lekce. (Obzvláště online vysvětlivky dřívějšího cvičícího Vaška Brožka jsou velmi hodnotné!)
• Případně si založte nové vlákno v současném semestru, ale nerozmělňujte vlákna příliš, pro vaše vlastní pohodlí při sledování vláken se nejprve podívejte, zda vlákno o stejném tématu již není letos založeno. Cvičící budou v nových vláknech promptně reagovat a pomáhat vám.

Konkrétně v učivu Lekce 1 je jeden důležitý a trvale problematický bod - platnost implikace z neplatného předpokladu, který mnohým dělá problémy (a ani si to včas neuvědomí, až třeba na zkoušce). Čtěte v této staré diskuzi (dříve se vztahovala až k lekci 7), srovnejte si to s příslušnými příklady v odpovědnících a případně založte nové diskuzní vlákno na toto téma v aktuálním semestru.

Následuje malé cvičení z logiky a jazyka pro pobavení...

Doplňkové a externí materiály

Mimo vlastních přednáškových textů a cvičících příkladů přinášíme ještě množství odkazů na doplňkové a externí zdroje (nespravované vyučujícím). V těchto externích zdrojích můžete nalézt množství informací, které vám poskytnou jiný pohled na látku nebo více hlubších vědomostí (ale také někdy mohou být v rozporu s některými našimi pojmy a definicemi - v takovém případě samozřejmě dávejte předost materiálu z přednášky). Ke zvládnutí předmětu nejsou doplňkové informace nutné, ale mohou se hodit.

Obecně o cvičeních IB000

Na látku jednotlivých lekcí předmětu navazují povinná cvičení, jejichž hlavním cílem je přemostit "propast" mezi suchou teorií z přednášek a použitím této teorie k řešení příkladů a problémů, které můžete potkat v dalším studiu a v praxi. Avšak pozor, nepředstavujte si, že jediným cílem cvičení je vás naučit mechanicky řešit příklady pro zkoušky, to určitě ne (i když si to mnozí studenti představují)! Ne, vy byste se měli naučit, jak získané matematické poznatky využívat i v příkladech, se kterými se dopředu nesetkáte...

Cvičení jsou organizována co dva týdny po 2 hodinách, neboli v poloviční délce oproti přednáškám, přesto jejich snahou je pokrýt rovnoměrně látku všech lekcí, možná trochu se zpožděním oproti těm lekcím.

Co v osnově k cvičením najdeme

Na rozdíl od přednášek, jejichž náplň je pevně daná výukovým textem a promítanými slidy, je náplň cvičení poměrně volná a závisí na cvičícím a konkrétním zájmu studentů, co se bude přesně probírat. Studenti by proto měli chodit do cvičení dobře připraveni s představou, co se mají a chtějí dozvědět. K tomu jsou zde naznačeny body a směry, které to které cvičení může probírat...

Skutečně nejhorší jsou studenti, co ani nebyli na přednášce, ani si přednášku před cvičením neprostudovali! Těm pak ani dobré cvičení nemá jak pomoci a není tam čas na jejich neznalost brát ohled.

Jelikož může nastat, že první cvičení některé skupiny budou mít před první přednáškou, nebude zde náplň pevně navázaná na přednášku, nýbrž cvičící může volně tvořit obsah v rámci níže uvedených mantinelů.

Obecná náplň cvičení - s komentáři

(Pořadí se nemusí dodržovat.)

• K čemu je tento předmět a k čemu je matematika obecně. Viz komentář jednoho z cvičících 2012:

V prvním týdnu mě překvapilo, kolik studentů si myslí, že matematika je k ničemu a že ji v životě nepoužijí, tak jsem na druhý týden vymyslel nějaké motivační ukázky použití matematiky. Konkrétně jsem jim ukázal nějakou primitivní kryptografii (jak matematikou zabezpečit komunikaci) a že existuje něco jako měnová arbitráž a že na to lze použít nějaké matematické metody (jak matematikou vydělat peníze). Doporučuji na začátek nějakou motivaci (ať už tuto, nebo jinou) zařadit.

• Rozebrat některé z příkladů z přednášky na důkazy, případně jiné krátké důkazy. Vysvětlit praktický rozdíl mezi důkazem tvrzení a jeho vyvrácením protipříkladem, což se studentům často plete. Dát si záležet na pochopení rozdílů mezi "rozhodněte, zda", "dokažte" a "vyvraťte (podejte protipříklad)" a co to všechno znamená. Příklady na "vyvraťte tvrzení" - hledat a najít jeden co nejkonkrétnější protipříklad.
• Probrat výrokové formule, práci s nim a pravdivostní tabulky. Dopsání formule k předvyplněné tabulce. Vyjádření formule pouze pomocí implikace a negace. Tautologie. Mechanická negace formule s příklady na skutečné použití.
  • Co třeba takový příklad: Z elementárních výroků "předevčírem pršelo", "včera sněžilo", "dnes je konec světa" sestavte tautologii v přirozeném jazyce. Pohrejte si s ní, ať vypadá hezky a košatě, zkuste ji pak také znegovat.
• Vysvětlit skutečně do hraničních detailů význam implikace, tj. ne pouze pravdivostní tabulka, ale skutečný logický význam v matematických tvrzeních. Jaký má význam implikace z napravdivých (sporných) předpokladů.
• Kvantifikátory, jak se s nimi pracuje (v jednoduchých situacích). Jednoduché příklady - že obecně nelze prohazovat pořadí kvantifikátorů, že nelze zaměnit existenční za univerzální, ale ani naopak.
  • Rozdíl si dobře uvědomíme třeba na následujícím příkladu:
  1. Pro každého studenta A v posluchárně existuje osoba B taková, že B je partnerem/partnerkou A.
  2. Existuje osoba B taková, že B je partnerem/partnerkou každého (tj. všech najednou) studenta A v posluchárně.

Poznámka k matematickému zápisu

• Studenti se někdy asi cítí "zastrašeni" důrazem na přesné matematické vyjadřování od první lekce. Pravý význam (že skutečně nejde o psaní matematických symbolů, ale naučení se přesně vyjadřovat v běžném jazyce) je sice zdůrazňován už na přednášce, ale je třeba se na odstranění tohoto strachu zaměřit i na cvičení. Viz komentář jednoho z cvičících 2012:

Mnoho studentů se bojí “matematického zápisu” a vůbec netuší, jak nějaké tvrzení napsat. Bojí se přitom použít slova a celé věty a myslí si, že všude musí být matematické znaky (kvantifikátory atp.), tj. neopodstatněný strach ze spojení “přesné matematické tvrzení”. Možná je dobré je v tom trochu povzbuzovat a třeba na úvod na prvním cvičení zařadit nějaké ukázky jednoduchých tvrzení a hledání nepřesností v nich.

• Co třeba tvrzení "pro každé číslo platí, že je liché nebo sudé"? Zde je hlavní nepřesnost v chybějícím určení číselného oboru - celá nebo reálná? Podobné příklady přesných i nepřesných tvrzení pomohou pochopit to "správné".
• Zkuste si formálně zapsat důkaz tvrzení "součin dvou lichých (celých) čísel je lichý" - nechť se každý student pokouší sám, je to jasné tvrzení, ale pocvičí se při něm, co je v zápise důkazu podstatné.

OBSAH

Tato lekce pokračuje v základních formalismech matematických vět a důkazů a rozebírá jednotlivé základní typy matematických důkazů. Největší důraz je kladen na techniku matematické indukce. Blíže viz slidy...

Samostatné procvičení učiva - odpovědníky

Sice pro látku matematických důkazů je obtížné připravovat automatizované testy, ale přesto zde máte připraveno několik příkladů, jejichž úkolem je zjistit, nakolik porozumíte formálním matematickým (logickým) výrokům a umíte s nimi a důkazy pracovat v různých situacích. Procvičíte si v nich jednoduchou "doplňovačku" důkazu indukcí a ověříte si, nakolik chápete logiku matematických tvrzení zapsaných slovně ve tvaru "pokud máme předpoklady, pak platí tento závěr". Zastoupeny jsou i rekurentní vzorce posloupností. Abyste si vyzkoušeli něco nového, na co musíte sami přijít zobecněním poznatků z přednášky, budete také hledat obecný součet zadané řady přirozených čísel.

Diskuse o látce

Následující diskusní vlákna, nahrazující učebnová cvičení v minulých letech, by i vám mohla pomoci se vypořádat s látkou a příklady této lekce. (Obzvláště online vysvětlivky dřívějšího cvičícího Vaška Brožka jsou velmi hodnotné!)

Případně si založte nové vlákno v současném semestru, ale nerozmělňujte vlákna příliš, pro vaše vlastní pohodlí při sledování vláken se nejprve podívejte, zda vlákno o stejném tématu již není letos založeno. Cvičící budou v nových vláknech promptně reagovat a pomáhat vám.

Doplňkové a externí materiály

Pro další doplňkové studium matematických důkazů a jejich příkladů doporučujeme následující výukový text DIM - kapitolu 3, a sady zadání tištěných příkladů. Jelikož se jedná o staré a neupravované texty, mohou se v nich vyskytovat odlišnosti od výuky, přednost má však zásadně to, co se učí v aktuálním semestru IB000. Teprve po vlastních pokusech o vyřešení příkladů si ve složce /el/1433/podzim2013/IB000/um/jine/ v IS prohlédněte příslušné soubory s řešením (ty zde schválně nejsou přímo odkazované).

Z důvodu lepší provázanosti oddílů cvičení v osnově s lekcemi jsou následující cvičení rozděleny do podosnov jako "2a" a "2b", třebaže obě dohromady se fyzicky probírají v jedné dvouhodinovce.

Obecná náplň cvičení

• Důkazové techniky. Důkaz obrácením implikace a důkaz sporem. Zopakování správného logického významu implikace a negace výroků v tomto kontextu. Proč je důkaz sporem tak "mocný" a užitečný - "přibírá" si ke své práci více předpokladů získaných negací původního závěru.
• Pokračovat (ano, zase znovu, neboť je to důležité) s vysvětlením významu implikace v zapeklitém případě, asi založeném na dostupných příkladech s minimální množinou předpokladů z cvičných odpovědníků.
• Důkazy matematickou indukcí, podrobné rozebrání některých ukázek z přednášky či podobných, třeba důkazy sumačních vzorců a jiných kombinatorických identit. Vysvětlení techniky "zesílení" dokazovaného tvrzení, a proč tento přístup tak dobře pomáhá matematické indukci (získáváme silnější indukční předpoklad pro další odvozování).
• Zvlášť vysvětlení významu báze indukce (první kostička musí "spadnout"!), opětovné rozebrání falešného příkladu s koňmi stejné barvy z přednášky - kde je podstata falešnosti tohoto "důkazu".

Jelikož je látka tohoto cvičení poměrně obtížná, bude spíše "přednášena" cvičícím než interaktivně procvičována.

Možné příklady k demonstraci důkazů

(Libovolný výběr z nabídky, která doplňuje obsah přednášky.)

• Jestliže x^2 je celé(!) sudé, pak také x je sudé.
• 2^(6k)-1 je dělitelné sedmi.
• 2^n >= 2n (pro n>=1, pro n=0 to platí taky, ale špatně se dokazuje ind. krok, musí se udělat dva zákl. kroky) a podobné.

• 1+3+5+...+(2*n+1) = (n+1)^2,    1^2+2^2+...+n^2 = n*(n+1)*(2*n+1)/2,
  f_0+f_1+...+f_(n-1) = f_(n+1)-1 (součet členů Fibonacciho posl.).
• Obecně řešení a důkaz jednoduchých rekurentních posloupností jako třeba f(n+1)=2f(n)+3 apod., včetně počátečního "uhodnutí" výsledku.

• Šachovnici 2^n*2^n lze pokrýt tříčtverečkovými “L-segmenty” tak, aby právě jedno předem zvolené pole zůstalo nepokryto.
• Na kolik nejvýše částí rozdělí rovinu n kružnic (obdoba přímek z přednášky).

OBSAH

Od třetí lekce se dostáváme už k formálně jednoduššímu a praktičtějšímu učivu, které navazuje na vaše základní znalosti ze středních škol... V informatické mluvě se dá říci, že se budeme zabývat základními "datovými strukturami" moderní matematiky a teoretické informatiky - množinami a relacemi.

Připravená sada cvičících příkladů je v této lekci poměrně snadná a týká se základních množinových operací, jejichž vyřešení je s pomocí nakreslených Vennových diagramů záležitost spíše oddechová, a také jednoduchých výpočtů číselných posloupností a nakonec zopakování logického matematického uvažování.

Diskuse o látce

Následující starší diskusní vlákna by vám opět mohla pomoci se vypořádat s látkou a příklady této lekce.

Doplňkové a externí materiály

Opět přidáváme dvě starší sady papírových příkladů na množiny k doplňkovému procvičení. Vyberte si z nich, co vás zajímá, některé příklady jsou značně obtížné (ale opět se můžete potom podívat na vzorová řešení v /el/1433/podzim2013/IB000/um/jine/). Také v kapitolách 1,2 textu DIM najdete zajímavé poznatky a řešené příklady a na závěr si užijte volných internetových zdrojů.

Obecná náplň cvičení

Množiny a množiny...

• Množinový kalkul, Vennovy diagramy, jednoduché ukázky a identity. Například: distributivita průniku vůči sjednocení i naopak; konkrétní protipříklad, proč rozdíl není asociativní; důkaz asociativity symetrického rozdílu.
• Pochopení chování symetrického rozdílu si vůbec zaslouží zvláštní pozornost i na více množinách; jak lze třeba zjednodušit výraz (A∪B)Δ(B∪C)Δ(C∪D) bez použití symetrického rozdílu? Jak zjednodušit výraz (AΔB)∩(BΔC)∩(CΔD)∩(DΔA)?
• Je dobré si znovu probrat definici uspořádané dvojice z přednášky - jak se chová a jak snadno dokázat, že rovnost dvojic znamená rovnost po složkách? (nezapomeňte v tom případ (x,x)!).
• Rekurentní posloupnosti, konkrétní ukázky, odhad řešení a využití indukce k důkazu správnosti řešení - pro náměty viz cvičení 2a nahoře.

Tato druhá část cvičení je poměrně jednoduchá a množinový kalkul obvykle nečiní potíže, až na symetrický rozdíl. Je dobré si všimnout a spojit příklady rekurentních posloupností s důkazy matematickou indukcí (které se výhodně používají k ověření vlastností či předpisů pro takto zadané posloupnosti) - viz cvičení 2a.

Upozornění k diagramům

• Pokud se Vennovy diagramy mají používat k důkazům množinových identit, je to v zásadě možné (s patřičným komentářem). Avšak není formálně možné je jednoduše využít vyvrácení množinového vztahu - u vyvrácení vztahu je třeba vždy podat konkrétní protipříklad volby množin, pro které vztah neplatí. Pouhý vybarvený diagram nestačí - proč?

OBSAH

Čtvrtá lekce se blíže zabývá relacemi, jejich základními vlastnostmi a obecně tím, jak na relace nahlížet a uchopit je. Klíčovým nástrojem při práci s relacemi je jejich skládání. Specificky se zaměřujeme na binární relace. Zmíněno je použití relací v aplikační informatice.

Procvičení začínáme zopakováním kartézského součinu množin. Dále jsou přidány středně obtížné příklady na princip inkluze a exkluze a posloupnosti. Definice vlastností relací si pak nejlépe procvičte na hlavních příkladech v odpovědníku. Jedná se o nelehké a dosti abstraktní učivo, které se pak často vyskytuje u zkoušek, takže tenokráte věnujte procvičení dostatek času. V příkladech (zde i v příští lekci) vás čekají jak jednoduché dotazy na vlastnosti relací přímo zadaných tabulkami, tak obdobné značně obtížnější otázky o relacích implicitně zapsaných běžným jazykem.

Diskuse o látce

Doplňkové a externí materiály 

Opět přidáváme tři starší sady příkladů na relace k doplňkovému procvičení.

S pojmem relace se můžeme setkat v mnoha oblastech života a s různými faktickými významy. Nás zajímá matematický pojem relace, k němuž existuje také několik alternativních vysvětlení na českém webu.

Následující náplň cvičení je na celou dvouhodinovku (případně lze nejprve doběhnout nedokončené učivo množin).

Obecná náplň cvičení

Podrobné (hloubkové) pochopení toho, co jsou relace a jak je chápat v praktických ukázkách...

• Zopakování definice uspořádaných dvojic, kartézského součinu, konkrétní příklady, proč součin není komutativní. Ukázka distributivity součinu proti sjednocení a průniku.

• Volitelně se lze věnovat otázce asociativity kartézského součinu (což je věcí přesné definice a může i nemusí být asociativní). Taktéž volitelně se lze dotázat, kdy je výsledkem kartézského součinu neprázdná množina - na konečných množinách to je (přirozeně) právě pro oba neprázdné činitele, kdežto na nekonečných množinách se jedná o poněkud zapeklitý "axiom výběru".

• Zavedení relace jako podmnožiny kartézského součinu. Reprezentovat relaci výčtem dvojic, tabulkou (maticí), grafem - co v těchto reprezentacích znamenají vlastnosti reflexivní, symetrická, antisymetrická, tranzitivní? Zde je třeba se soustředit na podrobné pochopení významu zmíněných vlastností a probírat konkrétní příklady. Které relace s informatickým podtextem by už studenti mohli znát?

• Probrání definice a "praktických" aspektů skládání relací, názorné zobrazení a tabulky. Inverze binární relace (což bude podrobněji probíráno u inverzí funkcí). Skládání relací je asociativní operací, není to však komutativní operace ani když probíhá nad stejnou nosnou množinou.

Relace ekvivalence - úvod (když bude čas, lze ponechat na další cvičení po Lekci 5)

• Ekvivalence je reflexivní, symetrická a tranzitivní relace. Příklady relací ekvivalence a jejich přirozený vztah ke "shlukování" - rozkladům nosné množiny.

• Důraz je na správné intuitivní pochopení, co to znamená relace ekvivalence (tj. že prvky v třídách jsou vždy něčím "stejné" a zároveň "různé" od ostatních tříd). 

Možné příklady k demonstraci vlastností relací

• Lze zvolit libovolné příklady z příslušného odpovědníku v IS, avšak lepší by bylo se podívat také na další ukázky relací, jaké si cvičící vymyslí a hned demonstruje na studentech (například nechť se studenti "shlukují" podle barvy vlasů nebo přibližné výšky). Kdy demonstrované relace budou ekvivalencemi?
• Vyvrátit několik studenty oblíbených bludů jako:
  • relace je symetrická <=> relace není antisymetrická ?
  • dvě relace mají nějakou vlastnost => jejich sjednocení/průnik ji má taky ?
  • relace R je popsána podmínkou typu "A nebo B" a relace popsaná jako "A" je reflexivní/symetrická => celá R jereflexivní/symetrická ?
• Je třeba zdůraznit, že na řešení slovních úloh z odpovědníků (zde v Lekci 4,5) neexistují žádné "spolehlivé zkratky" - vlastnosti relací nebo jejich složenin se MUSÍ poctivě odvozovat z definic, ostatně to ukazují i předchozí vyvrácené bludy o relacích.

• Trochu obtížné, ale pěkné: V posluchárně jsou studenti A a B v relaci (A,B), právě když A sedí v první řadě nebo B sedí v poslední řadě. Dokažte, že je tato relace tranzitivní.
• A další obtížnější námět: Pro které základní množinové operace * platí, že složení relací "S po (P*R)" je totéž, co "S po P" * "S po R"? Podívejte se na platnost/neplatnost takových tvrzení v obrázkové znázornění skládání (šipečkama).

OBSAH

V matematice jsou dva typy nejčastěji zmiňovaných relací  - ekvivalence a uspořádání, které alespoň na intuitivní úrovni (bez matematických formalit) už potkal snad každý. Jejich správné pochopení i ve formální rovině bude potřebné i v mnoha pozdějších teoretických předmětech. V páté lekci se tedy zaměřujeme na relace ekvivalence (a s ní související rozklady) a na relace částečného uspořádání a předuspořádání a Hasseovy digramy.

Přiložené příklady rozvíjejí minulou látku vlastností relací a jejich složenin na obtížném poli slovních popisů relací v běžném jazyce. Některé příklady jsou teď až velmi obtížné, a proto se neváhejte o nich poradit se spolužáky, diskusními vlákny a se cvičícími. Právě u těchto slovně zadaných příkladů není žádný jednoduchý spolehlivý postup na jejich vyřešení, nýbrž musíte sami hledat cesty, jak každé variantě příkladu zvlášť porozumět, a hlavně si zkoušejte problém zakreslit co nejlépe na papír.

Dále se klade důraz na porozumění rozkladům u ekvivalencí a Hasseovým diagramům a uspořádaným množinám obecně; otázky jsou kladeny na různé pojmy spojené s uspořádáními z přednášky. Učte se kreslit si relace vhodně na papír a "vidět" v tom svém nakreslení, o co v příkladě jde. Z technických důvodů dva z příkladů předbíhají dobu, neboť se odkazují na pojem tranzitivního uzávěru relace z příští lekce, avšak jinak náplní patří k současné látce (případně se k nim můžete vrátit později).

Diskuse o látce

Jelikož se v průběhu doby výrazně přesunula jednotlivá témata a příklady mezi lekcemi 4,5,6, mohou některé diskuse působit vzhledem k současnému stavu zmateně, ale své si tam najdete...

Zaměřte se na diskuse o správném pochopení zadání příkladů o skládání relací studentů sedících v posluchárně - když se v zadání vůbec nespecifikují rozměry posluchárny ani obsazenost jejích míst, pro jaké instance tedy mají vlastnosti platit? Skutečně můžete předpokládat, že každé místo (sedadlo) v posluchárně je při skládání relace obsazené? Co když v posluchárně nikdo jiný kromě vámi sledované dvojice či trojice nesedí, změní se tím vlastnosti zkoumané složené relace? Pokud odpovědi nevíte sami, ve fórech ji najdete několikrát rozebranou z různých stran a je to všeobecně poučné počtení v každém případě, nejen vzhledem k dotčeným příkladům...

Doplňkové a externí materiály 

Opět přidáváme dvě starší sady příkladů na relace k doplňkovému procvičení. Částečně se vztahují i k příští lekci, takže je řešte postupně...

Následují externí odkazy, které by snad mohly být také užitečné, ale k látce je obtížné najít pěkné materiály...

Následující náplň cvičení je na celou dvouhodinovku, neboť se jedná o příliš obsáhlé učivo.

Obecná náplň cvičení

Opět skládání relací.

• Jak se relace skládají, ilustruje se chování definice skládání "na obrázku", tj. v grafickém zobrazení relace se šipkami. V případě zadání relací maticí je vhodné si obrázek dokreslit. Srovnání se skládáním "tabulkami" jako v relačních databázích (databáze však nejsou naším zájmem, je to jen jeden z ilustračních případů).
• Zdůraznit pořadí relací u skládání!
• Příklad skládání slovně popsaných relací, kde je třeba ad hoc kombinovat slovní popisy k získání "uchopitelné" definice té složené relace.

Relace ekvivalence - mohli jste mít trochu už v Cvičení 3

• Ekvivalence je reflexivní, symetrická a tranzitivní relace. Příklady relací ekvivalence a jejich přirozený vztah ke "shlukování" - rozkladům nosné množiny.
• Potrénovat i formální stránku rozkladů množin, podle definice.

Pochopení relace uspořádání a především konečných uspořádaných množin.

• Zopakování relace uspořádání - reflexivní, symetrická a tranzitivní, vysvětlení role reflexivity jako neostré versus "ostré uspořádání". Ne všechny dvojice na uspořádané množině jsou porovnatelné - proto se někdy říká "částečné uspořádání".
• Popisy relací uspořádání - výčtem dvojic, slovním popisem, Hasseovým diagramem. Kromě slovního popisu na obecné konečné množině (jako "mezi studenty sedící v posluchárně...") se příklady soustřeďují na malé uspořádané množiny a důraz se opět klade na pochopení, jak uspořádání vypadají a jak je použít. Konstrukce uspořádání po složkách a lexikografického. Jiným vhodným příkladem uspořádání je dělitelnost na přirozených číslech.
• Pojmy uspořádaných množin: nejmenší/největší prvek, minimální a maximální (čím se tyto liší od nejmenších/největších!), infimum a supremum podmnožiny, atd. Tyto pojmy je nejlepší trénovat na malých Hasseovských diagramech.
• Lehce se ukáží nekonečné uspořádané množiny a jejich "divné" chování, jako třeba možná neexistence minimálního prvku atd.
• Předuspořádání - pochopit význam asociované ekvivalence a z ní získaného jádra předuspořádání. V mnoha praktických situacích si říkáme, že nějaké věci "uspořádáme" a přitom to je pouze předuspořádání! Vezměme si třeba "uspořádání zboží podle ceny" - co děláme s těmi, co stojí stejně?

Možná jednoduchá tvrzení o uspořádáních k procvičení důkazů

(Pokud bude čas...)

• Na konečné uspořádané množině je vždy alespoň jeden minimální prvek (proč na nekonečné ne?).
• Pokud je prvek nejmenší, musí to být právě jediný minimální prvek, ale naopak to platí jen na konečných množinách.
• Lexikografické uspořádání podle lineárně uspořádaných složek poskytuje opět lineární uspořádání.

OBSAH

Šestá lekce završí látku o relacích a funkcích, tentokráte se podíváme na základní vlastnosti funkcí a na skládání. Dobře se při studiu látky podívejte do definic a porozuměte i kvantifikacím v nich, tj. pochopte, kdy a proč se píše, že něco má platit pro "každý prvek množiny" nebo že "existuje prvek pro který platí".

Lekce končí další formálně nelehkou látkou, totiž induktivními definicemi množin a funkcí, avšak i to je látka pro informatiky užitečná, jak ukazují i příklady z přednášky. Mimo jiné z ní odvodíme dříve zmíněné uzávěry relací.

Procvičte si zde skládání funkcí dle definice, porozumnění zápisu permutace pomocí cyklů a práci s ním. Vedle toho příklady pracují s uzávěry relací, kde je potřeba (kromě znalostí formálních definic) dobře pochopit, "co to vlastně dělá". Zvláště si nacvičte zakreslování relací jejich grafem na papír a dokreslování tranzitivního uzávěru. Se správným přístupem na těchto příkladech nakonec není nic obtížného. A opět dojde i na oblíbené (mnou) slovní zápisy relací - u tohoto typu příkladu ještě více platí, že univerzální návod na jejich řešení neexistuje a musíte do každé varianty sami zvlášť "vidět" a cvičit se v tom.

Diskuse o látce

Doplňkové a externí materiály

Opět přidáváme dvě starší sady příkladů k doplňkovému procvičení. Ne vše v nich se vztahuje přímo k lekci, ale za vyzkoušení to stojí - hlavně část o induktivních definicích, jež zatím není pokrytá v odpovědnících.

Cvičení 5 je z časových důvodů rozděleno na dokončení látky relací a funkcí a následné (5b) uvedení grafů z Lekce 7.

Obecná náplň cvičení

Funkce a permutace, inverze a skládání

• Vlastnosti funkcí (prostá, na, bijektivní), jejich vztah k inverzím funkcím. Skládání funkcí coby speciálních relací.
• Permutace, jejich vyjádření a zobrazení ("šipečkami") na malé konečné množině. Reprezentace permutací cykly, skládání permutací.

Induktivní definice a speciálně induktivně definované uzávěry relací.

• Induktivní definice množiny, induktivní definice funkce z množiny. Jejich reálné ukázky, nejspíše příklady definic "syntaxe a sémantiky" v informatických oblastech.
• Reflexivní, symetrický, tranzitivní uzávěr relace jako speciální případy induktivních definic. Procvičení především tranzitivního uzávěru na obrázcích. Zdůrazňujeme, že tranzitivní uzávěr je nejlepší hledat a pochopit na grafu relace ("šipečkách")!

OBSAH

V sedmé lekci se začneme zabývat další důležitou oblastí diskrétní matematiky, teorií grafů mající skutečně široký dopad na rozsáhlé oblasti informatiky. Úvodem si zavedeme pojem grafu a další základní pojmy jako podgrafy a isomorfismus. Poté se hlouběji seznámíme s jedním druhem grafů - stromy. Rozsah pokrytí látky grafů v předmětu IB000 je sice omezený, ale dostatečný z hlediska deklarovaného profilu absolventa bakalářského studia.

Podívejte se pozorně na přiložené odpovědníky a sami si zkuste, nakolik látce rozumíte do detailu i do hloubky. Máte na výběr od velice snadných příkladů po (trochu) obtížnější testování isomorfismu. (Později se ještě doplní více typů příkladů.)

Hlavní poselství k těmto příkladům však zní: Naučte se grafy správně "hezky" nakreslit, abyste jim lépe porozuměli a mnohem snadněji tak uměli příklady vyřešit.  Skutečně, dobrý obrázek je základ, který i z obtížného příkladu dokáže udělat trivialitu (a pokud ne, hledejte ještě lepší obrázek...).

Diskuse o látce

Jedná se o novou látku v IB000, takže dosud zajímavé diskuse nebyly....

Doplňkové a externí materiály

Pro širší studium grafů v prvé řadě doporučujeme materiály kurzu MA010 na FI MU. Doplňkově uvádíme další odkazy a především doporučujeme skvělou učebnici Kapitoly z diskrétní matematiky.

Společně s Cvičením 5a.

Obecná náplň cvičení

Na látku využívající grafické zobrazení binárních relací a funkcí přímo navazuje abstraktní pojem grafu, který vlastně není ničím jiným než binární ireflexivní symetrickou relací, ale na druhou stranu nabízí mnohem širší možnosti použití.

• Formální definice grafu, její vztah k názornému nakreslení obrázkem a k běžným způsobům reprezentace grafu v počítači (maticí sousednosti nebo seznamy sousedů).
• Pojmy hran, stupňů vrcholů, kružnic a cest, podgrafů a podobně. Vše k procvičení především na názorných obrázcích. Triviální důkaz toho, že součet stupňů je sudý.
• Isomorfismus grafů, jeho poznání a taky zdůvodnění neisomorfismu v různých příkladech. Při zdůvodňování různosti grafů je potřeba pochopit, že na to není "univerzální recept", ale řešení se hledají ad hoc podle aktuální situace - třeba nesouhlasící stupně, nesouhlasící jednoduché podgrafy, atd.

Druhá část cvičení se pak soustředí jen na jeden speciální druh grafů - stromy.

• Definice jako souvislý graf bez kružnic. Běžné vlastnosti, převážně odvozené ze základního faktu, že strom obsahuje vrchol stupně 1, pokud má >1 vrchol. Počet hran stromu je n-1.
• Strom coby minimální souvislý (pod)graf na daných vrcholech. Kostry grafu, volitelně lze ukázat něco o počtech koster některých grafů, ale to je nad náplň předmětu.

OBSAH

Osmá lekce přímo navazuje na předchozí a představuje první základní oblast použití grafů v modelování užitečných úloh. Začneme s obecným schématem procházení grafu, které si pak specializujeme na několik známých algoritmů jako procházení do šířky, do hloubky, Dijkstrův a Jarníkův algoritmus. Těžištěm lekce však zůstává matematika stojící za těmito aplikacemi a důraz na pochopení správnosti postupů předvedených algoritmů.

Cvičební příklady budou doplněny v budoucnu - zatím vyvíjíme novou technologii do odpovědníků, která by vám umožňovala si s obrázky grafů naživo "hýbat" a lépe tak být schopni si i složité grafy s ohodnocením "přečíst".

Diskuse o látce

Doplňkové a externí materiály 

Toto cvičení je volitelné pro případ, že Cvičení 5a se zbytky relací bylo probráno již ve Cvičení 4 a teď není po 5b co pořádně dělat... (jinak přeskočit a jít rovnou na 6a!)

Rozebrání způsobů procházení grafu, ruční ukázky běhů algoritmů.

• Tuto část není až tak nutno probírat na cvičeních, neboť průběh algoritmů vázajících se k procházení grafu byl důkladně vysvětlen na přednášce a stejně bude znovu probírán na jiných předmětech o návrhu algoritmů.
• Pokud je přesto volný čas, lze například dokazovat, že obecné schéma procházení grafu probere všechny vrcholy a hrany souvislé komponenty. Také je možno probrat důkazy korektnost Dijkstrova a Jarníkova algoritmu.

OBSAH

Devátá lekce se zabývá jinou rozsáhlou oblastí užitečných aplikací grafů, které jsou svázány s pojmem sítě (s kapacitami) a problémem hledání maximálního toku v ní. Jedná se opět o tradiční problém s dávno známými efektivními postupy řešení a také s množstvím příznivých důsledků jak v samotné teorii grafů, tak v aplikacích ze života. Mimo samotného problému toku v síti si musíme podrobněji zavést orientované grafy a jejich souvislost, a také si probereme některé z teoretických důsledků řešení toku v síti, jako bipartitní párování a systémy různých reprezentantů.

Diskuse o látce

Doplňkové a externí materiály

Cvičení 6 se dělí na dva výrazně odlišné tematické celky. Zde v 6a se dokončí látka grafů s důrazem na orientované grafy, sítě.

Obecná náplň cvičení

Vysvětlení orientovaných grafů a jejich využití pro "síťové" problémy.

• Orientované grafy - čím se liší od obyčejných,kdy třeba potřebujeme orientaci hran, souvislost s relacemi, které nemusí být symetrické. Krátké shrnutí pojmů, které se na orientované grafy přímo přenášejí, jako podgrafy, isomorfismus, atd.

• Úlohy využívající sítí a toků v nich, ukázky všelijakých "transportních úloh". Ukázky definovaných sítí a použití základního algoritmu vylepšování nenasycených cest pro nalezení toku, se zdůrazněním rovnosti velikosti toku s nalezeným minimálním řezem na konci.

• Volitelně lze probrat, jak algoritmus nenasycených cest implementovat pro rychlejší práci (tj. především hledat nejkratší nenasycené cesty do šířky - Edmonds-Karp, Dinitz). Tot však není nutné, neboť k tomu budou kurzy návrhu algoritmů.

• Lehce se uvedou v příkladech některé odvozené úlohy od toků - jako bipartitní párování nebo systémy různých reprezentantů. Studenti by měli vědět, že takové úlohy existují, a spojit si je s toky v síti.

OBSAH

Desátá lekce se týká dokazování vlastností algoritmů. Nejprve si ukážeme, jak vůbec správně formalizovat zápis algoritmu (otázku, co to přesně je algoritmus, ponecháme stranou a zůstaneme na intuitivní úrovni pochopení). Algoritmus tak pro nás bude konečná posloupnost elementárních kroků, zjednodušená v zápise tzv. řídícími konstrukcemi. K zápisu elementárních kroků budeme používat symbolický zápis (určený pro tento předmět, přitom poměrně kompatibilní s běžnými zvyklostmi jinde) nebo i běžný jazyk; nejdůležitější bude správné strukturování zápisu.

V návaznosti na předchozí si pak ukážeme vlastnosti algoritmů na mnoha malých příkladech a uvedeme si problematiku matematického dokazování vlastností algoritmů. Zmíněny budou i rekurzivní algoritmy.

Odpovědník této lekce se zaměřuje na pochopení procedurálního zápisu jednoduchých algoritmů a na poznání, co daný algoritmus počítá. Na to pak navazují příklady týkající se rekurentních zápisů posloupností, což jsou vlastně jednoduchá matematická vyjádření rekurzivních programů.

Při řešení části z úloh byste si měli opět vzpomenout na matematickou indukci - právě ta vám pomůže si ověřit vaši odpověď, abyste se vyhnuli penalizaci za chyby (třebaže odpovědník stěží může přímo ověřit, zda si svou odpověď dokazujete nebo jen hádáte, záporné body za chyby to statisticky poměrně dobře odhalí).

Diskuse o látce

(Mějte na paměti, že dříve - v době uvedených diskusí - byla látka této lekce jinde, trochu už na začátku a převážně pak v Lekci 8. Některé z diskusí jsou relevantní také pro následující Lekci 11.)

Doplňkové a externí materiály

V části 6b cvičení se přejde na látku dokazování algoritmů.

Obecná náplň cvičení

Proč je třeba algoritmy dokazovat, jak si vůbec algoritmy zapisovat nějak nezávisle na programovacím jazyce a přitom dostatečně blízce programům a podobně...

• Je třeba procvičit symbolický formální zápis algoritmů z přednášky. Studenti musí umět běžné algoritmy rozepsat do elementárních kroků a přehledně procedurálně zapsat nezávisle na programovacím jazyce.
• Zkusí se pár krátkých příkladů, na kterých je vidět, proč je nutné i krátké a jednoduše vypadající algoritmy ověřovat a dokazovat.
• Mohou se podrobněji rozebrat ukázkové příklady důkazů algoritmů z přednášky, zmíní se také otázka, zda se vůbec algoritmus zastaví (problém s "while" cykly).

Možné ukázky chybných a správných algoritmů k procvičení:

• Vrcholové pokrytí je podmnožina X vrcholů grafu taková, že každá hrana má aspoň jeden vrchol v X. Zkusme hledat nejmenší vrcholové pokrytí v grafu následujícím hladovým algoritmem
  • Bereme vždy vrchol (či jeden z několika), který má největší stupeň v podgrafu dosud nepokrytých hran.

Kde je chyba? Najděte graf, na kterém tento postup selže (stačí už 7 vrcholů a 6 hran...). A jak lze vrcholové pokrytí vlastně řešit? Bohužel je to NP-úplný problém, avšak existují krásné algoritmy řešící otázku, zda graf má vrcholové pokrytí o <=k vrcholech pro konstatní (malé) k.

• ...

OBSAH

Jedenáctá lekce pokračuje v látce dokazování vlastností algoritmů, tentokrát v systematickém podání. Nejprve se zaměříme na dokazování konečnosti algoritmu, poté na přehled technik matematické indukce vhodných pro dokazování algoritmů a nakonec si uvedeme několik hezkých vzorových algoritmů s důkazy.

V tomto odpovědníku se seznámíme s obtížnějšími úkoly určení chování netriviálních algoritmů...

Diskuse o látce

(Opět mnohé diskuse pocházejí z dřívější doby, kdy látka byla v Lekci 8.)

Doplňkové a externí materiály

OBSAH

Poslední lekce se již věnuje některým teoreticky pokročilým partiím, vycházejícícm z teorie množin a zajímavým pro příští studium informatiky. Konkrétně si vysvětlíme něco z historie nekonečných množin, meze použitelnosti naší naivní definice množiny a nakonec si ukážeme, že stejný typ argumentace (známý jako Cantorova diagonála) je velmi užitečný pro teoretickou informatiku při důkazech neřešitelnosti jistých problémů.

Vzhledem k výběrovému charakteru tato látka bude podána pokročilým způsobem nebude vyžadována u zkoušky. Přesto, či spíše právě proto, doporučuji návštěvu poslední přednášky všem studentům, kteří to myslí se studiem informatiky vážně a chtějí se něco pořádného dozvědět.

Doplňkové a externí materiály

Jelikož se nedá obecně čekat, že by během semestru došlo až na sedmé cvičení, nejsou zde žádná doporučení ohledně obsahu. V podstatě se lze zaměřit na kteroukoliv látku, již si chtějí studenti zopakovat nebo prohloubit.