Általános információk
A diszkrét struktúrák furcsa név – több értelme lenne, ha diszkrét matematikának hívnák. Ez alapvetően olyan matematikát jelent, ami nem folytonos (pl. számtan).
Előfeltételek
Nincs
Topics Covered
- Sets, functions, relations
- Proof techniques, indukció
- Számelmélet és nyilvános kulcsú titkosítás
- Számlálás és kombinatorika
- valószínűség
- logika
- gráfelmélet
- véges automaták és szabályos nyelvek
- Kontextus…free languages
- Computability and NP-CompletenessSok időt töltöttünk bizonyítással és hangsúlyt fektettünk az indukciós bizonyításra.
Munkaterhelés
Általában heti feladatsorok, 2-3 elővizsga és egy záróvizsga. Történelmileg a házi feladat a jegy viszonylag nagy részét teszi ki. A kurzuson nincs programozás, és a munkaterhelés viszonylag egyenletes a félév során. Nem jelentősen nehéz, de hetente akár néhány órát is igénybe vehet, attól függően, hogy mennyire érti a témákat.
Általános tanácsok
A CS 2110-el párhuzamosan történő felvétele nagyon jól kezelhető és hasznos. Sok átfedés van a témakörökben, különösen az indukciós bizonyításokkal és a gráfelmélettel kapcsolatban (bár az átfedések az utóbbi időben csökkentek, különösen mivel a 2110 kevésbé összpontosít a bizonyításokra), és hasznos, ha kétszer látod az információkat. Ez az óra sok CS alapját képezi, ezért jó, ha viszonylag korán felveszik. A gráfelmélet és a bizonyítások elsajátítása meglehetősen fontos sok felsőfokú kurzushoz és általános CS-hez.
Az ajánlott/kötelező tankönyvet nagyon hasznosnak találtam! Sok olyan témát, amit az órán röviden tárgyaltunk, a tankönyvben mélyrehatóan tárgyaltunk. A tankönyv elolvasása és a példák átnézése növelte a pontszámomat a vizsgán. Emellett nem kellett elmennem az irodai órákra, amelyek általában nagyon zsúfoltak voltak.
Ne vegye meg a tankönyvet. Az irodai órák is zsúfoltak lesznek azokon a napokon, amikor a feladatsorokat kell megoldani.
Tudd meg, hogy a tanársegédek közül kik a matematika szakos hallgatók, és kérj tőlük segítséget. Ők többet fognak tudni.
^Ez. 2800 egy elméleti tárgy, így a matematika szakosok sokkal többet fognak tudni erről, mint a CS-esek. Továbbá, ahogy már említettem, a gráfelmélet, a bizonyítások és a legtöbb más anyag, amit tanulsz, nagyon hasznos a különböző problémákról való gondolkodáshoz.
Testimonials
Bart Selman, azt hittem, hogy ez az óra nagyon könnyű volt. Ha ezt az órát megelőzően volt már valamilyen érintkezése a témákkal (középiskolai matematika és/vagy más CS órák, mint például a CS 1114), akkor minimális időt kell erre az órára fordítania.
A középiskolában nagyon sokat foglalkoztam matematikával és némi számelmélettel/kombinatorikával, és ez a kurzus ennél tovább nem haladt. Emellett párhuzamosan vettem fel a MATH 3360-at, ami alapvetően ennek a kurzusnak egy sokkal nehezebb változata, így végül szinte semmit sem tanultam a 2800-ban.
Passzal vettem fel. Ez az óra egy vicc volt, és nagyon kevés új anyagot tanultam, de jó volt az összes véletlenszerű matematika átismétlése, ami többnyire nem jelent meg hivatalosan az eddigi óráimon. Alacsony fenntartású és elég érdekes viszont.
Kozen (2013 ősz) a kurzus nem volt borzasztó nehéz, de nehezebb volt, mint a többi beszámoló alapján gondolnánk. A félév során 8 feladatsorunk volt, amelyek mindegyike több órát vett igénybe. A zárthelyik elfogadható nehézségűek voltak, de a zárthelyi előfeladatokat nehéz volt befejezni a megadott idő alatt. (A záróvizsgára bőven volt idő.) Vegye tudomásul, hogy hacsak nem vett már részt diszkrét matematika órán, akkor sok témát először fog látni.”
Kozen (2013 ősz): Kozen nagyon jó előadó volt, és mindent részletesen elmagyarázott. A probléma az volt, hogy sokkal jobban belement a részletekbe, mint amennyire egy szélessávú órán kellene, így nagyon gyorsan megtanultunk egy csomó különböző témát tisztességes mélységgel. Ettől még nem volt túl nehéz, de ez rengeteg anyagot és sok konkrétumot jelentett, amit meg kellett jegyezni a vizsgákra (a fenti beszámoló ezt jól kifejti). Pass tanfolyami jegyzetei (lásd az alábbi linket) nagyon hasznosak voltak, de Kozen más témákat is érintett. A könyv nem volt túl hasznos, de szükség volt rá, mivel néhány feladat a könyvből származott.”
Graeme Bailey (2014 tavasz): Meglepetés ért bennünket. Bár ennek az órának az a híre, hogy viszonylag könnyű, ebben a félévben az anyag nagyon nehéz volt. A szokásos témák mellett Bailey az idő nagy részét különböző absztrakt algebrai témákra fordította, különösen a csoportelméletre. Az osztály kb. 35%-a esett ki a határidőn belül.
A heti házi feladatokat általában szerdán adták ki, hogy a következő hétfőn legyenek esedékesek (10 napot ígértek nekünk, hogy megcsináljuk őket, de ritkán kaptunk többet 5 napnál). Nagyon bizonyításigényesek voltak, és jelentős 10-15+ órát vettek igénybe. A nagyon kevés matematika szakos hallgatótól eltekintve a legtöbb tanársegéd nem tudott segíteni a házi feladatokban, mivel ők maguk sem tudták, hogyan kell megoldani a problémákat, és az irodai órákat csak azzal töltötték, hogy velünk flangáltak.
Ettől függetlenül Bailey érezhetően igyekezett segíteni a diákjainak, extra irodai órákat és gyors Piazza-válaszokat kínált. A teszteket vagy az órán, vagy esténként kínálták, és meglepően korrektek voltak. Záró megjegyzések: Élve jöttem ki ebből az órából, sokkal több erőfeszítést tettem, mint amennyit akartam, valószínűleg sokat tanultam a diszkrét matematikáról, de ha tehetném, könnyebb professzort választanék.
George (2020 tavasz): Én személy szerint nagyon élveztem ezt az órát és érdekesnek találtam az anyagot, de YMMV. A munkaterhelés kezelhető volt, de elég nagy szükséged volt az irodai órákra (amiket nagyon késő este tartottak a COVID előtt), hogy jól teljesíts. A kéthetente megjelenő feladatsorokat hétfő és szerda között adták ki, és a következő hét péntekén kellett leadni, és egy partnerrel együtt lehetett dolgozni rajtuk. Az előadásokhoz (a COVID előtt) a kurzus wikijén kellett elolvasnunk az “előkészületeket” az óra előtt, és az órát többnyire példákkal és iClicker-kérdésekkel töltöttük, hogy megerősítsük a koncepciót. Az előadások azután, hogy online mentek, többet tanítottak az anyagból magának az előadásnak a során. Összességében egy elég nehéz óra, de kifizetődő, ha egyszer befejezted.
Past Offerings
Hopcroft jellemzően ősszel és Pass, tavasszal tanítja ezt. Kozen viszont 2013 őszén tanítja ezt. Michael George 2014 őszén vette át. Anke van Zuylen fogja ezt tanítani 2020 őszétől.