Obecné informace
Diskrétní struktury je divný název – smysluplnější by byl název Diskrétní matematika. V podstatě to znamená matematiku, která není spojitá (tj. kalkulus).
Předpoklady
Žádné
Probíraná témata
- Množiny, funkce, relace
- Důkazové techniky, indukce
- Teorie čísel a šifrování s veřejným klíčem
- Počítání a kombinatorika
- Pravděpodobnost
- Logika
- Teorie grafů
- Konečné automaty a regulární jazyky
- Kontext-jazyky
- Výpočetnost a NP-úplnostDostatek času věnovaného důkazům a důraz na důkazy indukcí.
Pracovní zátěž
Obvykle se jedná o týdenní soubory úloh, 2-3 předmaturitní testy a závěrečný test. Historicky tvoří domácí úkoly poměrně velkou část známky. V předmětu se neprogramuje a pracovní zátěž je v průběhu semestru přiměřeně rovnoměrná. Není výrazně těžká, ale může zabrat až několik hodin týdně v závislosti na tom, jak dobře rozumíte tématům.
Všeobecné rady
Souběžná výuka s CS 2110 je velmi dobře zvládnutelná a užitečná. Témata se hodně překrývají, zejména pokud jde o důkazy indukcí a teorii grafů (i když v poslední době se překrývání zmenšilo, zejména proto, že 2110 se na důkazy zaměřuje méně), a je užitečné vidět informace dvakrát. Tato třída je základem pro mnoho CS, takže je dobré ji absolvovat přiměřeně brzy. Naučit se teorii grafů a důkazy je přiměřeně důležité pro spoustu kurzů vyšší úrovně a obecné CS.
Považuji doporučenou/povinnou učebnici za velmi užitečnou! Spousta témat, která byla stručně probrána v hodinách, byla v učebnici probrána do hloubky. Čtení učebnice a prohlížení příkladů mi zvýšilo skóre v testu. Také jsem nemusel chodit na úřední hodiny, které byly obvykle velmi přeplněné.
Učebnici si nekupujte. Také kancelářské hodiny budou přeplněné ve dnech, kdy se mají řešit sady úloh.
Zjistěte si, kteří ze studentských asistentů jsou matfyzáci, a požádejte je o pomoc. Budou vědět víc.
^Toto. 2800 je teoretická třída, takže matematici o tom budou vědět mnohem víc než lidé z CS. Také, jak už bylo zmíněno, teorie grafů, důkazy a většina dalšího materiálu, který se naučíte, je velmi užitečná pro uvažování o různých problémech.
Odměny
S Bartem Selmanem jsem si myslel, že tento předmět je opravdu snadný. Pokud jste se s tématy setkali už před touto hodinou (matematika na střední škole a/nebo jiné předměty z oblasti CS, například CS 1114), měli byste být schopni strávit na této hodině minimum času.
Na střední škole jsem se hodně věnoval matematice a dělal jsem teorii čísel/kombinatoriku a tento předmět mě nijak dál neposunul. Navíc jsem souběžně chodil na MATH 3360, což je v podstatě mnohem těžší verze tohoto předmětu, takže jsem se nakonec v 2800 nenaučil skoro nic.
Zapsal jsem ho s prospěchem. Tento předmět byl vtip a naučil jsem se jen velmi málo nové látky, ale bylo to dobré zopakování veškeré náhodné matematiky, která se většinou oficiálně neobjevila v mých předchozích hodinách. Nenáročný a dostatečně zajímavý, i když.
S Kozenem (podzim 2013) předmět nebyl strašně těžký, ale byl těžší, než by se podle ostatních referencí mohlo zdát. V průběhu semestru jsme měli 8 úloh, z nichž každá zabrala několik hodin. Zkoušky ve třídě byly přiměřené obtížnosti, ale předzkoušky ve třídě bylo těžké dokončit v daném čase. (Na finále bylo času dost.) Uvědomte si, že pokud jste již neabsolvovali hodiny diskrétní matematiky, budete se s mnoha tématy setkávat poprvé.
Kozen (podzim 2013): Kozen byl velmi dobrý přednášející a vše podrobně vysvětlil. Problém byl v tom, že šel mnohem více do detailů, než by se na širokou třídu slušelo, takže jsme se velmi rychle učili spoustu různých témat se slušnou hloubkou. Přesto to nebylo příliš těžké, ale znamenalo to hodně látky a mnoho konkrétních věcí k zapamatování na zkoušky (výše uvedená reference to dobře vysvětluje). Velmi užitečné byly Passovy poznámky ke kurzu (viz odkaz níže), ale Kozen se věnoval i jiným tématům. Kniha nebyla příliš užitečná, ale potřebovali jste ji, protože několik problémů bylo z knihy.“
Graeme Bailey (jaro 2014): Čekalo nás docela překvapení. Ačkoli má tento předmět pověst relativně snadného, v tomto semestru byla látka velmi obtížná. Kromě obvyklých témat věnoval Bailey velkou část času různým tématům abstraktní algebry, zejména teorii grup. Přibližně 35 % třídy odpadlo v termínu.
Týdenní domácí úkoly byly obvykle vydávány ve středu s termínem odevzdání následující pondělí (bylo nám slíbeno 10 dní na jejich vypracování, ale málokdy jsme dostali více než 5). Byly velmi náročné na dokazování a zabraly značných 10-15+ hodin času. Kromě několika málo matematiků většina TA nebyla schopna s domácími úkoly pomoci, protože sami nevěděli, jak problémy řešit, a své úřední hodiny trávili jen tím, že se s námi trápili.
Přesto Bailey věnoval znatelnou snahu pomoci svým studentům, nabízel úřední hodiny navíc a rychlé odpovědi na Piazze. Testy byly nabízeny buď ve třídě, nebo večerní formou a byly překvapivě spravedlivé. Závěrečné poznámky: Z této třídy jsem vyšel živý, vynaložil jsem mnohem více úsilí, než jsem chtěl, pravděpodobně jsem se naučil hodně o diskrétní matematice, ale kdybych mohl, vzal bych si lehčího profesora.
George (jaro 2020): Osobně mě tento předmět opravdu bavil a látka mi přišla zajímavá, ale YMMV. Pracovní zátěž byla zvládnutelná, ale člověk docela potřeboval úřední hodiny (které se před-COVID konaly opravdu pozdě v noci), aby se mu dařilo. Dvoutýdenní soubory problémů byly vydávány mezi pondělím a středou a odevzdávány v pátek následujícího týdne a mohli jste na nich pracovat s partnerem. Na přednášky (před-COVIDem) jsme si měli před hodinou přečíst „přípravu“ na wiki kurzu a hodinu jsme většinou strávili řešením příkladů a otázkami na iClickeru, abychom si upevnili daný koncept. Na přednáškách po přechodu na online se učilo více látky během samotné přednášky. Celkově dost obtížný předmět, ale obohacující, jakmile ho dokončíte.
Předchozí nabídky
Hopcroft obvykle vyučuje tento předmět na podzim a Pass, na jaře. Kozen ji však vyučuje na podzim 2013. Michael George ji převzal na podzim 2014. Anke van Zuylen ji bude vyučovat od podzimu 2020.
Podle ní se bude vyučovat od podzimu 2020.