Průvodce IB000 Matematické základy informatiky
prof. RNDr. Petr Hliněný, Ph.D.
Průvodce IB000 Matematické základy informatiky
Info
Období
podzim 2021

Aneb bez matematiky to skutečně nepůjde...

Kurz přináší elementárně pojatý úvod do matematiky vysokoškolského typu s ohledem na potřeby studia informatiky. Studenti se seznámí se základními matematickými nástroji potřebnými pro popis a formalizaci vztahu mezi intuitivními informatickými konstrukcemi a jejich přesným matematickým významem. Také se naučí přesně vyjadřovat a být si svými vyjádřeními naprosto jisti. Cílem studia je vytvořit pojmový a metodologický základ pro studium řady dalších nezbytných informatických předmětů.

Základní informace

  • Studenti jsou povinni pravidelně číst předmětové aktuality https://is. muni.cz/auth/df/aktuib000/.
    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í, k dispozici Diskusní fórum předmětu IB000.
    Učitelé a studentští poradci budou dotazy na fóru promptně zodpovídat. Na samostatné emailové dotazy týkající se obecných otázek naopak nebude odpovídáno, neboť to nic nepřináší ostatním studentům.
  • COVID
    (Aneb "zavírači, táhněte už do pr****yč"! A vy se očkujte, ať zavíračům nedáváte zbytečně zbraně do rukou.)
    Bohužel ani letos to nevypadá se světem úplně normálně, takže budeme muset oželet velké prezenční přednášky. Nahrazeny budou loňskými videopřednáškami doplněnými letošními přednáškovými konzultacemi (provedením online přes Zoom, ale snad by mohlo dojít i na osobní setkání v omezeném počtu). Cvičení a zkoušení se vrací k prezenčním formám jako před Covidem (asi ale bude muset být zkoušení děleno na menší skupiny studentů).
  • Čtěte proto následující aktuality co nejčastěji, neboť další možná omezení a pokyny budou přicházet kdykoliv a s okamžitou účinností!
Učební text IB000
beze změn od 2020...
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/vi-offline/
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/118005466/
Přednáškové slidy po lekcích
Zde jsou jednotlivé slidy lekcí tak, jak jsou promítané na přednáškách (ale bez pauz uvnitř stránek). Obecně platí, že každý týden se probere jedna lekce po řadě. Můžete si slidy tisknout a na přednáškách do nich dělat poznámky, ale pro prosté vytištění k učení si vezměte celý učební text.
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/
Učitel doporučuje studovat od 29. 10. 2021 do 5. 11. 2021.
Učitel doporučuje studovat od 5. 11. 2021 do 27. 11. 2021.

Učitel doporučuje studovat od 11. 9. 2021 do 22. 9. 2021.
Učitel doporučuje studovat od 11. 9. 2021 do 29. 9. 2021.
Učitel doporučuje studovat od 18. 9. 2021 do 6. 10. 2021.
Učitel doporučuje studovat od 25. 9. 2021 do 13. 10. 2021.
Učitel doporučuje studovat od 2. 10. 2021 do 20. 10. 2021.
Učitel doporučuje studovat od 9. 10. 2021 do 27. 10. 2021.
Učitel doporučuje studovat od 16. 10. 2021 do 3. 11. 2021.
Učitel doporučuje studovat od 23. 10. 2021 do 10. 11. 2021.
Učitel doporučuje studovat od 30. 10. 2021 do 15. 11. 2021.
Učitel doporučuje studovat od 6. 11. 2021 do 24. 11. 2021.
Učitel doporučuje studovat od 13. 11. 2021 do 1. 12. 2021.
Nyní studovat
Učitel doporučuje studovat nyní – od 27. 11. 2021 do 14. 12. 2021.

Organizace studia, testů a zkoušek

Kterak studovat

IB000 = přednášky (mimořádně jen offline video plus konzultace) + povinná prezenční cvičení v učebnách + domácí procvičení s online odpovědníky.

Přednášky

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/vi-offline/
Zároveň za každou přednášku bude poskytnuta možnost interaktivních konzultací přednesené látky lekce (ty berte jako konzultace samotné teorie z videopřednášky, pro konzultace použití teorie na problémech a příkladech jsou běžná cvičení).
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/118005466/
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/vi/

Hned po přednášce se také na vykládanou látku můžete podívat z jiného úhlu v následujících automatizovaných příkladech. Ty jdou od úplných rutinních základů až po někdy značně obtížné problémy (ke kterým se třeba později vracejte).

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/auth/el/fi/podzim2021/IB000/um/cvicnv/

Cvičení

Na látku jednotlivých lekcí (přednášek) 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í, ale k mechanickému procvičování příkladů přece mnohem lépe poslouží výše odkázané odpovědníky). Hlavním cílem rozvrhovaných cvičení IB000 je studentům ukázat, jak získané matematické poznatky správně uchopit, zpracovat a využívat i v situacích a příkladech, na které nejsou dopředu nacvičeni...

Pamatujte: 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 dobře vedené cvičení nemá jak pomoci, není tam čas na jejich neznalosti brát ohled a je to celkově jen ztráta času pro ně i cvičícího.

COVID: MU se vrací k prezenční výuce (s výjimkou masových přednášek)!  Přesněji řečeno, v souladu s Rozhodnutím děkana Fakulty informatiky Masarykovy univerzity č. 4/2021, jako garant IB000 stanovuji závazně formu konání cvičení IB000 s fyzickou přítomností.

Tudíž pro všechny studenty IB000 opět platí povinnost prezenční účasti na cvičeních. Pokud by přece jenom došlo vyšší mocí k novému omezení prezenční výuky, cvičení se přesunou v rozvrhových časech do online formy (v reálném čase), ale povinnost účasti zůstane zachována.

Dobré rady pro začátek

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 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. A pamatujte, že učebnová cvičení IB000 neslouží k tomu, abyste se v nich "nadrilovali" na zkoušky, nýbrž abyste si lépe a do hloubky osvojili teorii přednášenou na přednášce. K samotnému procvičování příkladů k testům a ke zkouškám slouží právě odpovědníky každé lekce, které byste si měli procvičovat ihned po přednášce (a v případě těžkostí se případně pak ptát na cvičeních). A pokud odpovědníky na domácí zábavu nestačí, jsou ve zdejších materiálech přidány ještě další slovní příklady, které částečně obsahují i vzorová řešení.
  • Při samostatném řešení a procvičování příkladů uvidíte, jak různorodě lze nabyté vědomosti uplatnit u konkrétních problémů, včetně (především) takových, na které jste nebyli dopředu "trénováni". I když pak v praxi budete narážet na problémy a úkoly jiného typu, umění aplikovat teoretické vědomosti na řešení libovolných budoucích úkolů vám zůstane...
  • Samotná osnova IB000 přímo odkazuje na materiály z přednášky, odpovědníky k samostatnému procvičení, rámcový obsah cvičení, zmíněné přídavné slovní příklady se vzorovým řešením, doplňkové materiály na internetu a také přidává odkazy na hodnotná diskusní vlákna z minulých let vztahující se ke konkrétnímu učivu.
  • Pro obecné dotazy k výuce a odbornou diskusi o přednášené látce slouží v IS předmětové diskusní fórum, kde vám budou určení cvičící promptně odpovídat a hlavně je vyučujícím garantována odborná správnost odpovědí. Snažte se udržovat diskusní vlákna fóra 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 se diskuse mohla rozvinout.

Testy a zkoušky

COVID: Případná nechtěná omezení prezenční výuky se mohou do těchto detailů hodnocení neblaze promítnout, ale vždy bude prioritou co nejvíce zachovat popsaný systém hodnocení s případným přechodem jeho částí do online formy...

Komplexní hodnocení ukončení předmětu se skládá z následujících (povinných) částí...

Semestrální průběžné

  • 3x domácí online testy po 8 bodů každý, řešené samostatně studenty v určeném rozmezí doma (bez možnosti opravy).
  • 3x prioritní nadílka bodů (opět bez možnosti opravy) za
    • domácí písemný úkol za 16 bodů (poměrně obtížný na důkazy),
    • školní semestrální test za 16 bodů (trochu jako domácí testy, ale hlídané a také s důkazy),
    • drobné testíky na cvičeních v součtu za celkem nejvýše 12 bodů (viz upřesnění níže).
  • Ze semestru (plus bonusu níže) je požadován zisk aspoň 7 bodů ze 12 bodů na cvičeních a celkem aspoň 14 prioritních bodů, tj. součet nezáporných zisků ze školního testu plus domácího úkolu plus testíků na cvičeních musí být alespoň 14 bodů. Z tohoto pravidla nejsou možné výjimky ani nebudou žádné opravy!
    • Prostě kdo toto (nakonec celkem snadné) pravidlo nesplní, v předmětu končí už po semestru, neboť studovat se musí průběžně.
  • Ke zkoušce či zápočtu se pak jako semestrální výsledek započítá součet tří lepších nezáporných z uvedených šesti nadílek.
    • Pro dobrou šanci na složení zkoušky doporučujeme získat alespoň 26 semestrálních bodů. Jak si můžete přečíst dole, je jistá možnost si semestrální výsledek později vylepšit během zkoušek.
  • Dodatečnou (a nepovinnou) součástí semestrálního hodnocení jsou mimořádné bonusy pro nejlepší studenty, o jejichž možnostech získání budete informováni během semestru a na cvičeních. Tyto se připočítají jak ke splnění požadavku bodů na cvičeních a požadavku prioritních bodů, tak také k celkovému semestrálnímu hodnocení studenta. (Jsou tedy velmi cenné, ale i vzácné.)

Závěrečné (zkouškové)

  • Závěrečná povinná zkouška testem na počítači na 36 bodů, která se koná pod dozorem v učebně (a ke které je nejprve nutno splnit předchozí pravidlo prioritních bodů). Požadavkem pro úspěšné složení je zisk aspoň 51 bodů v součtu s celkovým semestrálním výsledkem a zároveň splnění výše uvedeného semestrálního požadavku, tj. zisku 7 bodů ze cvičení a celkem 14 bodů z prioritních.
    • 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 počítačové zkoušky následuje (jako jediná nepovinná součást) písemná zkouška za až 30 bodů, obdobná starším písemkám zveřejněným v materiálech. Celkový součet pak určí známku E-A.
    • Písemná zkouška nemá žádné záporné body, pohoršit si už nemůžete a složení zkoušky máte po počítačové části jisté.
  • 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í. S povinným ziskem prioritních bodů pak k udělení zápočtu stačí dosáhnout semestrálního výsledku aspoň 26 bodů.
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/auth/el/fi/podzim2021/IB000/um/pis/

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 ISs příslušnými daty skládání.

Náplň 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. Formální odlišností u školního semestrálního testu je způsob skládání, kdy odpovědi místo ťukání do počítače obvykle zatrháváte na speciální odpovědní arch, který se pak oskenuje. Nově školní semestrální test obsahuje i zapsání krátkého matematického důkazu (také na papír). 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í.

Odpovědníky
Ostré testy IB000 - zde (v příslušný čas) najdete odkazy odpovědníků, které budete v předmětu skládat jako testy. Bližší informace jsou v popisu každého odpovědníku (a obecné informace v osnově předmětu).

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 (bod za každé cvičení) do celkového součtu nejvýše 12 bodů. Stejně jako u jiných semestrálních testů z nich není možná oprava. Testíky na cvičeních budou online v IS a zkoušet budou především vaši připravenost na cvičení, tj. že budete vědět, co se probralo na přednášce (která je relevantní k danému cvičení).  Podrobné informace k testíkům.

  • Na pokročilých cvičeních (letos jediné značené AA) jsou tyto základní testíky nahrazeny pořádnými znalostními semestrálními testy, které jsou zvlášť organizovány cvičícím. Pro ně v součtu platí stejné maximum bodů (12) i stejný dolní limit jako pro základní testíky.

  • 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 třech cvičeních a případně může být vyhlášen i dřívější termín ukončení udělování bonusových bodů na cvičeních. (Bonusové body se připočítávají ke cvičením i k prioritním.)

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.














Jak to s testy a zkouškou probíhá

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. Stejně nemáte čekáním o co přijít.
  • K prohlížení odpovědníkových testů nám IS nedávno nadělil skvělou novinku - skrývá body udělené za jednotlivé podotázky. Naštěstí si to pořád můžete zobrazit, pokud myší ukážete na body za celou otázku.
  • U písemných testů budete muset čekat ještě déle, než budou písemně opraveny a pak naskenová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 (a nejméně) -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. 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 možnost jej spustit ještě jednou (či dvakrát), 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. Možná vám v některých otázkách třeba ty dodatečné závorky přijdou jako správné, ale IS si s tím prostě neporadí a dá vám záporné body. Proto si máte jednotlivé typy otázek dopředu procvičit sami doma. 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 kódováním, 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í 3 lepších výsledků ze všech (šesti nebo sedmi), máte možnost klidně polovinu testů 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".
  • 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 i každý domácí test možno opkovaně 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ění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. 

Náhrady a opravy v semestru

Možnosti oprav hodnocení:

  • Jak je uvedeno, semestrální testy nelze skládat opakovaně ani opravovat (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ů, existuje následující automatický mechanismus pro vylepšení celkového semestrálního součtu (platí to jak pro zkouškové ukončení, tak i pro zápočtové): Půjdete normálně na termín počítačové zkoušky. Po neúspěšném složení toho zkouškového testu se vezme jeho bodový výsledek plus třetina ze semestru získaných prioritních bodů a to bude vaším 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 bude počítáno automaticky bez potřeby vaší iniciativy a uvidíte to ve výsledcích dotyčného zkouškového termínu.
  • 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í úspěšného 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.

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

Poznámka pro studenty ukončené zápočtem

Jak už bylo napsáno, i na zápočtáře se vztahují stejná základní pravidla povinného zisku prioritních bodů a možnosti vylepšení semestrálního součtu automatickým mechanismem po absolvování testu počítačové zkoušky, jak je popsáno výše. Pokud v semestru nedosáhnete na potřebný bodový limit k udělení zápočtu, použijte výše popsaný mechanismus opravy semestrálních bodů - tj. naučte se a běžte na počítačový termín zkoušky. Výsledek se vám pak spočte automaticky a uvidíte případně vylepšené semestrální body (které vám snad budou k zápočtu stačit).

Doplňkové informace a materiály

Doplňkové studijní materiály:

Tyto materiály jsou jen podpůrné, nejsou nadále udržovány a tudíž se mohou liš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.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/

Testíky na cvičeních

Co testíky zkouší

Zda ovládáte základní pojmy z přednášky - ostatně bez jejich znalosti nedává účast na cvičení valného smyslu. 

Pro vaši informaci zde je obsah jednotlivých cvičení po týdnech (zkoušení budete z pojmů souvisejících s daným cvičením), Tyto pojmy vždy budou v době cvičení už odpřednášené.

  1. výroková logika [testík: Lekce 1]
  2. predikátová logika [testík: Lekce 2]
  3. množiny [testík: Lekce 3]
  4. důkazové techniky kromě indukce [testík: Lekce 4]
  5. indukce I [testík: Lekce 4]
  6. indukce II [testík: Lekce 5]
  7. relace [testík: Lekce 6 a část 3.5 z Lekce 3]
  8. ekvivalence, uspořádání [testík: Lekce 7]
  9. skládání relací, funkce, permutace  [testík: Lekce 8]
  10. grafy I (základní pojmy, podgrafy, isomorfismus) [testík: Lekce 9]
  11. grafy II (orientované grafy, stromy, kostry) [testík: Lekce 9 + 10]
  12. dokazování algoritmů I [testík: Lekce 4]
  13. dokazování algoritmů II, opakování  [testík: opakování, tedy cokoliv z předešlých týdnů]

Jak testíky probíhají

Testíky jsou realizovány formou odpovědníků v IS. Tyto odpovědníky mají název ve formě Týden xx a zpřístupní se automaticky na začátku vašeho cvičení. Na začátku se myslí opravdu "na začátku". Tedy pokud vaše cvičení začíná v 10 hodin, odpovědníky se zpřístupní v 10:00:00. Na vyplnění máte čas 5 minut (IS vám průběžně zobrazuje zbývající čas). Pozdní příchod tedy zkracuje čas na vyplnění odpovědníku!

Odpovědník se vyplňuje primárně elektronicky (na vlastním smartphone/laptopu/tabletu...). Proto mějte na začátku cvičení vaše zařízení už nachystané (ideálně s otevřeným IS). Pokud takovéto vhodné zařízení nemáte, nebo máte technické problémy, je k dispozici papírová verze. Nevýhodou je, že nemáte okamžitou zpětnou vazbu a výsledky se dozvíte až za týden.

V případě jakýchkoli technických problémů okamžitě kontaktujte cvičícího. Je vhodné si výsledky průběžně ukládat. Nezapomeňte na finální uložení.

Hodnocení testíku

Každý týden lze získat maximálně 1 bod. Za špatnou odpověď dostáváte záporné hodnocení, takže nedoporučujeme odpovědi tipovat. Nevyplněná odpověď je za 0 bodů. Pokud v daném týdnu získáte záporný počet bodů, do celkového hodnocení se započítává 0 (takže ani úplně špatně vyplněný testík není horší než absence na cvičení).

Do semestrálního hodnocení se vám započítá max. 12 bodů, přičemž musíte získat alespoň 7 bodů.

Pravidla

  • Odpovědník je nutno vyplňovat samostatně.
  • Při vyplňování musíte být fyzicky přítomni na svém cvičení.
  • Při vyplňování je zakázáno používat jakékoli studijní materiály.
  • Je zakázáno sdílet znění otázek v odpovědnících.

Jde prostě o zkoušení se vším všudy. Co to mj. znamená?

  • Nevyplňujte odpovědníky z domu/chodby na FI/jiné učebny...
  • Mít otevřené jakékoliv  materiály (skripta na/pod lavicí, PDF se slajdy v počítači, sbírka příkladů v počítači,  stránka na wikipedii...) je zakázané. (Pozor, i interaktivní osnova je studijním materiálem!)
  • Během vyplňování nic z netu nestahujte, nemějte otevřený chat (FB, discord,...) , nenahlížejte ke kamarádovi atp. Prohlížeč s jediným otevřeným oknem (ve kterém je odpovědník) je sázkou na jistotu.

Jakékoliv porušení pravidel bude odměněno -2 body do semestrálního hodnocení a osobní zkušeností s řízením před disciplinární komisí.

Náhrady testíků

Pokud máte pro daný týden řádnou omluvenku v IS, domluvte se s vaším cvičícím (mailem či osobně) na náhradě. Náhrada obvykle probíhá na některém z následujících cvičení, a to vyplněním odpovědníku v papírové formě.

Bonusové body obecně

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 0 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é".
  • Obvyklou možností zisku bonusových bodů je mimořádná aktivita na cvičení, tam však může jít celkově nejvýše o pár bodů za celý semestr.
  • Další možností je řešení dobrovolných velkých bonusových úkolů, které budou vyhlášeny někdy v půli 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í ke všem prioritním a jiným bodům potřebným ke splnění semestrálního limitu...

Domácí úkol - obecné pokyny

Získání zadání domácího úkolu

Pro získání zadání domácího úkolu si od určeného dne v ISu otevřete odpovědník "Domácí úkol ...". V něm dostanete zadání s otázkami. Otázky zodpovíte a odevzdáte v ISu a pak se podíváte na vyhodnocení. Pokud všechny vaše odpovědi budou správně, máte své zadání - vaším domácím úkolem pak bude napsat matematický důkaz správnosti vašich odpovědí podle pokynů z odpovědníku. Tento důkaz musíte napsat a odevzdat elektronicky do ISu nejpozději 12 hodin od otevření bezchybně vyhodnoceného odpovědníku, viz  technické pokyny v aktualitách předmětu.

Nebojte se, nemusíte vše zvládnout napoprvé, nýbrž máte možnost až 7 spuštění tohoto odpovědníku. Pokud vám odpovědník "spadne" nebo jej zodpovíte nesprávně nebo třeba pak nestihnete včas odevzdat samotný úkol (ten písemný důkaz vašich odpovědí), nic vážného se neděje a můžete odpovědník spouštět znovu, dokud nevyčerpáte určených 7 pokusů. Za neúplná nebo chybná vyplnění odpovědníku u tohoto úkolu nejsou žádné sankce. Ovšem uvědomte si, že v povolených 7 pokusech už jsou započítána řešení všech možných technických i jiných problémů, které vás mohou potkat, a více šancí nedostanete, takže šetřete.

Jak psát řešení - důkaz

Důkazy vždy pište stylem, jaký byl na přednáškách a v učebním textu. Tedy jasně stručně, srozumitelně a logicky správně. Ten důkaz se prostě musí dát číst jako po másle a určitě nedostanou moc bodů řešení, kde se opravující bude muset vracet v textu a luštit, co vlastně chcete říct. A řešení ve formě změti matematických symbolů bez vysvětlení nedostanou vůbec nic, i kdyby v nich někde byl "zakódovaný" správný důkaz. Řešení si po sobě několikrát nahlas přečtěte a když kdekoliv v argumentech sami zaváháte, tak jste to ještě nenapsali dobře a předělejte to.

Hodnotit se v úloze bude pouze to, jak pěkně umíte sepsat poctivý matematický důkaz. To, že jste dokázali najít správnou odpověď úlohy neznamená nic (to je jen nutný předpoklad, abychom se vůbec na řešení dívali).

Tak mnoho zdaru... a odevzdejte sem:

Domácí úkol - odevzdání písemného řešení
Pro informace k DÚ čtěte v aktualitách: https://is.muni.cz/auth/discussion/aktuib000/domaci_pisemny_ukol_29_10 Odevzdáváte jen 1 stranu A4 čitelného řešení s bílým pozadím ve formátu PNG nebo JPEG, případně na vlastní zodpovědnost PDF. Platný je pouze ten poslední vložený nebo změněný soubor, předchozí soubory se ignorují. Odevzdat musíte do 12 hodin od otevření odpovědníku.

Bonusové úkoly (dobrovolné)

Přejeme hodně štěstí, 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ělou možnost se zapojit do řešení opravdu zajímavých vědeckých problémů.

Odevzdávejte případná řešení do 27.11. 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 vyučují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í.) Také nebudou hodnocena řešení, které nevyhoví zde uvedeným formálním specifikacím.

Ve správně zpracovaném řešení 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. Všechna tvrzení ve vašem řešení musí být podepřena matematickým důkazem, nebo případně výsledky počítačového výpočtu, u kterého však musíte popsat a dokázat správnost použitého algoritmu. Vše podle formálních zásad uvedených v předmětu. A znovu opakujeme, že odevzdáváte jen jeden textový PDF soubor, ve kterém všechno napíšete a shrnete (speciálně v případě použití počítačových výsledků neodevzdáváte svůj program, nýbrž nás musíte o jeho správnosti přesvědčit v psaném textu).

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í nějakého cizího řešení, třeba od spolužáka. Vaše řešení projektu by mělo být skutečnou "nadstavbou" nad známými poznatky.

Mnoho zdaru a zábavy!

Bonusový úkol
Odevzdávejte řešení bonusového úkolu v jediném čitelném PDF souboru. Odevzdaný může být nejvýše jeden soubor na studenta a nesmí být nijak zabalený. Zadání bonusů viz předmětová osnova.

BONUS: Protínající se kruhy

Jedna pěkně kulatá geometrická úloha...

Definice. Množinu kruhů v rovině nazveme klikou, pokud se každé dva kruhy z této množiny protínají (mají neprázdný průnik).

Jak vidíte, není pravda, že každá klika kruhů v rovině musí obsahovat jeden bod náležející všem těmto kruhům zároveň. Kolik takových bodů dohromady potřebujeme, abychom "trefili" každý kruh, v tom nejhorším případě?

Úkoly. Není nutné řešit úplně vše, stačí se někde pohnout kupředu s přínosnou myšlenkou, ale nestačí jen řešit zahřívací první bod.
  • Pro zahřátí dokažte, že v každé klice 4 kruhů v rovině existují dva body takové, že každý kruh obsahuje aspoň jeden z nich. Poté totéž dokažte pro každou kliku 5 kruhů v rovině.
  • Rozhodněte, zda pro každou kliku tvořenou 6 kruhy v rovině existují dva body takové, že každý kruh obsahuje aspoň jeden z nich. Buď existenci takových dvou bodů dokažte pro všechny šestice kruhů tvořících kliku, nebo najděte konkrétní kliku šesti kruhů nemající takovou dvojici.
  • Pokud dvojice bodů je pro vaše úvahy málo, dokažte aspoň, že pro každou kliku tvořenou 6 kruhy v rovině existují tři body takové, že každý kruh obsahuje aspoň jeden z nich. A pokračujte stejně klikami 7, 8, .. kruhů v rovině. Je možné, že pro dostatečně vysoký počet kruhů v klice už ani 3 body nebudou stačit?

BONUS: Jak policajti honí zloděje

Přečtěte si Lekci 9 pro potřebné pojmy...

Na jednoduchém neorientovaném grafu honí policajti jednoho zloděje. Zloděj je na jednu stranu nekonečně rychlý, nekonečně chytrý a ví dopředu, co chtějí policajti dělat (čte myšlenky). Na druhou stranu se ale zloděj může pohybovat jen z vrcholu do vrcholu po hranách grafu, za předpokladu, že žádný z průchozích vrcholů není obsazený policajtem. Policajti se dole v grafu bojí pohybovat, a proto se pouze přemísťují vrtulníkem a občas do vybraného vrcholu jednoho policajta spustí. Zloděj je policajty chycen v okamžiku, kdy na jeho vrchol je spuštěn policajt a všechny sousední vrcholy jsou také obsazené policajty. Cílem zloděje samozřejmě je chycení unikat.

Ve "hře A" jsou následující upřesňující pravidla: policajti zloděje z vrtulníku vidí a jednou spuštěný policajt už musí ve svém vrcholu zůstat do konce hry. Ve "hře B" je upřesnění pravidel trochu jiné: policajti zloděje NEvidí (dokud ho nechytí), ale zase mohou dříve spuštěného policajta kdykoliv vytáhnout zpět do vrtulníku.

a) Udejte příklad grafu, pro který ve hře B stačí 2 policajti k chycení zloděje, ale ve hře A zloděje (na tomtéž grafu) nechytí ani 10 policajtů. Dokažte.
Každé odevzdané řešení musí tento bod obsahovat, avšak jen tato lehká otázka na bonus nestačí - pokračujte dále.

b) Pro každé k>1 udejte příklad grafu, ve kterém je nejmenší počet policajtů potřebný k chycení zloděje ve hře A i ve hře B stejný, roven k.

c) Nakonec dokažte, že pokud na daném grafu k policajtů vždy chytí zloděje ve hře A, tak stejných k policajtů na stejném grafu stačí k chycení zloděje ve hře B.

...d) Pokud ještě máte sílu dále řešit, podívejte se, co všechno se změní, pokud graf bude orientovaný (a zloděj bude muset respektovat směr šipek).

Lekce 1: Základní formalismy matematiky

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 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í procvičovací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 a pochopení významu výrokových formulí by také nemělo činit velké potíže.

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.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni1nv.qref

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.

Řecká abeceda

         

To pokud vídáte na přednáškách divná písmenka, která neznáte, nejspíše to budou řecká...

Lekce 2: Matematická logika a důkazy

OBSAH

V druhé lekci pokračujeme v učivu první lekce o logice a matematických důkazech. Zatímco v předchozí lekci jsme si k oběma uvedeným tématům řekli ty nejjednodušší základy (které jste si zároveň snad dobře procvičili na cvičeních i zde), nyní uvedeme hlubší poznatky matematické logiky a také se znovu podíváme na další aspekty matematických důkazů.
Hlavním výstupem lekce je pochopení tzv. kvantifikace a použití kvantifikátorů v predikátové logice.

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

Online procvičení učiva se v této lekci zaměřuje na pokročilé poznatky výrokové logiky, mimo jiné na úpravy logických formulí a na jejich normální tvar. Naučte se dobře všechnu tuto rutinu. (Na druhou stranu efektivní procvičení predikátové logiky není jednoduchou formou odpovědníku možné, a proto je ponecháno jen na učebnová cvičení.)

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni2nv.qref

Diskuse o látce

Opět následující starší diskusní vlákna (z dob před existencí učebnových cvičení IB000), která by vám mohla doplňkově pomoci s pochopením výkladu. Následuje malé cvičení z logiky a jazyka pro pobavení...

Doplňkové a externí materiály

Lekce 3: Množiny a množinové operace

OBSAH

V této lekci se vracíme k formálně jednoduššímu a názorně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ů s množinami. Těžší příklady s množinami pak najdete v příštím procvičení...

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni3nv.qref

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

K učivu přidáváme i 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á, ale některé příklady jsou značně obtížné. Teprve po vlastních pokusech o vyřešení příkladů si ve složce /el/fi/podzim2021/IB000/um/jine/ v IS prohlédněte příslušné soubory s řešením (ty zde schválně nejsou přímo odkazované).

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/zadani2005-2.pdf
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/zadani2005-4.pdf

Lekce 4: Techniky matematických důkazů

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ů. Důležité je i zavedení matematické indukce, které se budeme věnovat i v další lekci. 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ž cílem 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.

Na rozdíl od dřívějších odpovědníků zde již najdete i docela obtížné příklady, které nemusíte být schopni vyřešit napoprvé. K takovým příkladům se vracejte opakovaně po načerpání dalších vědomostí v předmětu, třeba na cvičeních. Opět upozorňujeme na nutnost dobrého 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í problémy pochopit, že třeba i následující tvrzení je 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é...)
Dále jsou zastoupeny dosti obtížné příklady připravující vás na příští látku týkající se posloupností a konkrétního použití matematické indukce. Naučte se v nich pracovat s neomezenými součtovými řadami i multiplikativními rozvoji technikou indukce.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni4nv.qref

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é.)

Doplňkové a externí materiály

Opět je přidána i starší sada papírových příkladů, jejichž vzorová řešení lze posléze najít ve výukových materiálech.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/zadani2005-1.pdf

Lekce 5: Rekurze, Strukturální indukce

OBSAH

Nyní je na čase se více ponořit do hlubin matematické indukce (tato lekce je jako samostatná od roku 2017) a spojit si tuto látku s induktivními definicemi množin a funkcí.

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

Příklady v procvičení zahrnují posloupnosti a jejich rekurentní vzorce. Budete hledat obecný součet zadané řady přirozených čísel a odhadovat správné řešení rekurentní posloupnosti. Procvičíte si také jednoduchou "doplňovačku" důkazu indukcí. Mimo samotných příkladů si uvědomte a sami zkuste, že správnost vašich odpovědí by se měla vždy dokazovat indukcí (při znalosti či uhodnutí výsledku je už takový důkaz docela přímočarý).

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni5nv.qref

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. (Dříve tato lekce o indukci nebyla samostatná a její obsah byl rozdělený v několika jiných.)

Doplňkové a externí materiály

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/prikl1.pdf
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/zadani2005-9.pdf

Lekce 6: Relace a jejich vlastnosti

OBSAH

Lekce se blíže zabývá relacemi, jejich základními vlastnostmi a obecně tím, jak na relace nahlížet a uchopit je. Specificky se zaměřujeme na binární relace a jejich vlastnosti a uzávěry.

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

V příkladech (zde i v příští lekci) vás čekají jak jednoduché dotazy na vlastnosti relací přímo zadaných tabulkami či výčtem, tak obdobné značně obtížnější otázky o relacích implicitně zapsaných běžným jazykem. Jedná se o nelehké a dosti abstraktní učivo, které se pak často vyskytuje u zkoušek, takže věnujte procvičení dostatek času.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni6nv.qref

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

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/prikl2.pdf
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/zadani2005-5.pdf
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/zadani2005-8.pdf

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.

Lekce 7: Ekvivalence, Uspořádané množiny

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.

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

Přiložené příklady rozvíjejí 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.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni7nv.qref

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,7 mohou některé diskuse působit vzhledem k současnému stavu zmateně, ale své si tam najdete...

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

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/zadani2005-6.pdf
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/zadani2005-7.pdf

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

Lekce 8: Skládání relací a funkcí

OBSAH

Tato lekce završí látku o relacích a funkcích. Tentokráte se podíváme na inverze a skládání relací a poté na základní vlastnosti funkcí (a také jejich 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í".

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

Procvičte si zde složené relace a skládání funkcí dle definice, také porozumění zápisu permutace pomocí cyklů a práci s ním. 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.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni8nv.qref

Diskuse o látce

(Z dob, kdy tato látka bývala v Lekci 6...)

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.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/zadani2005-3.pdf

Lekce 9: Pojem grafu

OBSAH

V osmé lekci se začneme zabývat další důležitou oblastí diskrétní matematiky - teorií grafů, kterou najdeme v mnoha oblastech informatiky. Úvodem si zavedeme pojem grafu a další základní pojmy jako podgrafy a isomorfismus, souvislost a vzdálenost. 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 (a více se naučíte také v kurzech algoritmizace).

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

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. Hlavní poselství k těmto příkladům 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. V příkladech si přímo můžete přesouvat vrcholy myší, abyste daný obrázek vylepšili. 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...).

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni9nv.qref

Diskuse o látce

Jedná se o novější látku v IB000 a dosud zajímavé diskuse sebrány 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.

Lekce 10: Stromy a kostry grafů

OBSAH

V této lekci se hlouběji seznámíme s jedním jednoduchým druhem grafů - stromy. V návaznosti na ně si probereme klasický problém hledání minimální kostry a postupy jeho řešení. V dodatku se můžeme podívat na jiný hezký kombinatorický problém hledání různých reprezentantů.

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

Pokračujeme s příklady k procvičení grafů. Přidáváme vzdálenosti a některé zapeklitější úlohy...

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni10nv.qref

Diskuse o látce

Doplňkové a externí materiály

Lekce 11: Formalizace a důkazy pro algoritmy

OBSAH

Jedenáctá 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 rekurzivní algoritmy, pro které je dokazování indukcí "jako dělané".

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

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á nebo jak probíhá. Na to pak navážou i příklady s naznačenými induktivními důkazy rekurzivních programů. Jelikož tyto odpovědníky nejsou lehké a následující lekce předmětu už nemá své procvičení, klidně si část procvičení nechte na poslední týden výuky.

Při řešení mnohých z uvedených ú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í).

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/cvicnv/Procviceni11nv.qref

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

Doplňkové a externí materiály

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2021/IB000/um/jine/prikl3.pdf

Lekce 12: Nekonečné množiny a zastavení algoritmu

OBSAH

Poslední lekce se již věnuje některým teoreticky pokročilým partiím, vycházejícím 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 a 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