Yleistä tietoa
Diskreetit rakenteet on outo nimi – olisi järkevämpää, jos se olisi nimeltään Diskreetti matematiikka. Tämä tarkoittaa periaatteessa matematiikkaa, joka ei ole jatkuvaa (eli laskentaa).
Edellytykset
Ei mitään
Käsiteltävät aiheet
- Määrät, funktiot, relaatiot
- Todistustekniikat, induktio
- Lukuteoria ja julkisen avaimen salaus
- Laskenta ja kombinatoriikka
- Todennäköisyys
- Logiikka
- Graafiteoria
- Finite automata ja säännölliset kielet
- Konteksti- ja logiikkateoria
- Logiikka
- Logiikka
- Graafiteoria
- Konteksti-free languages
- Computability and NP-CompletenessPaljon aikaa käytetty todistuksiin ja korostettu induktiotodistuksia.
Työmäärä
Viikoittaisia tehtäväsarjoja, 2-3 alkukirjaa ja loppukirja. Historiallisesti kotitehtävät ovat suhteellisen suuri osa arvosanasta. Kurssilla ei ole ohjelmointia ja työmäärä on kohtuullisen tasainen koko lukukauden ajan. Ei merkittävästi raskas, mutta voi viedä jopa muutaman tunnin viikossa riippuen siitä, kuinka hyvin ymmärrät aiheet.
Yleisiä neuvoja
Tämän kurssin suorittaminen samanaikaisesti CS 2110:n kanssa on hyvin hallittavissa ja hyödyllistä. Aiheissa on paljon päällekkäisyyttä erityisesti induktiotodistuksiin ja graafiteoriaan liittyvissä aiheissa (joskin päällekkäisyys on vähentynyt viime aikoina, varsinkin kun 2110:ssä on alettu keskittyä vähemmän todistuksiin), ja on hyödyllistä nähdä tiedot kahdesti. Tämä kurssi on perusta monille CS:n kursseille, joten se on hyvä suorittaa kohtuullisen aikaisin. Graafiteorian ja todistusten oppiminen on kohtuullisen tärkeää monia ylemmän tason kursseja ja yleistä CS:ää varten.
Suositeltu/pakollinen oppikirja oli mielestäni erittäin hyödyllinen! Monet aiheet, joita käsiteltiin lyhyesti tunnilla, käsiteltiin perusteellisesti oppikirjassa. Oppikirjan lukeminen ja esimerkkien läpikäyminen paransivat pisteitäni kokeessa. Minun ei myöskään tarvinnut mennä toimistotunneille, jotka olivat yleensä hyvin täynnä.
Älkää ostako oppikirjaa. Myös toimistotunnit ovat täynnä niinä päivinä, jolloin tehtäväsarjat on täytettävä.
Tiedä, ketkä opiskelijoiden apulaisopettajista ovat matematiikan pääaineopiskelijoita, ja pyydä heiltä apua. He tietävät enemmän.
^Tämä. 2800 on teoriakurssi, joten matematiikan pääaineopiskelijat tietävät tästä paljon enemmän kuin CS-opiskelijat. Lisäksi, kuten aiemmin mainittiin, graafiteoria, todistukset ja suurin osa muusta oppimastasi materiaalista on erittäin hyödyllistä erilaisten ongelmien päättelyssä.
Testimonials
Bart Selmanin kanssa luulin, että tämä kurssi oli todella helppo. Jos olet tutustunut aiheisiin ennen tätä kurssia (lukion matematiikkaa ja/tai muita CS-kursseja, kuten CS 1114), sinun pitäisi pystyä käyttämään minimaalisesti aikaa tähän kurssiin.
Olin hyvin mukana matematiikassa lukiossa ja tein jonkin verran numeroteoriaa/kombinatoriikkaa, eikä tämä kurssi edennyt sen pidemmälle. Lisäksi suoritin samanaikaisesti MATH 3360:n, joka on periaatteessa paljon vaikeampi versio tästä kurssista, joten päädyin oppimaan lähes mitään 2800:lla.
Suoritin sen hyväksytysti. Tämä kurssi oli vitsi ja opin hyvin vähän uutta materiaalia, mutta se oli hyvä kertauskurssi kaikesta satunnaisesta matematiikasta, jota enimmäkseen ei ollut virallisesti näkynyt kursseillani aiemmin. Matala ja tarpeeksi mielenkiintoinen kuitenkin.
Kosken (syksy 2013) kurssi ei ollut hirveän vaikea, mutta oli vaikeampi kuin muut suosittelut antavat ymmärtää. Meillä oli lukukauden aikana 8 ongelmakokonaisuutta, joista jokainen kesti useita tunteja. Tentit olivat vaikeusasteeltaan kohtuullisia, mutta luokkakohtaiset alkukokeet oli vaikea suorittaa annetussa ajassa. (Finaaliin oli runsaasti aikaa.) Ymmärtäkää, että ellette ole jo käyneet diskreetin matematiikan kurssia, näette monet aiheet ensimmäistä kertaa.”
Kozen (syksy 2013): Kozen oli erittäin hyvä luennoitsija ja selitti kaiken yksityiskohtaisesti. Ongelmana oli se, että hän meni paljon enemmän yksityiskohtiin kuin leveysluokassa pitäisi, joten opimme paljon eri aiheita kunnon syvyydellä hyvin nopeasti. Ei silti liian vaikea, mutta se tarkoitti paljon materiaalia ja monia yksityiskohtia, jotka piti painaa mieleen tenttejä varten (yllä oleva suositus selittää tämän hyvin). Passin kurssimuistiinpanot (ks. linkki alla) olivat erittäin hyödyllisiä, mutta Kozen käsitteli joitakin eri aiheita. Kirja ei ollut kovin hyödyllinen, mutta sitä kyllä tarvittiin, koska muutamat ongelmat olivat kirjasta.”
Graeme Bailey (kevät 2014): Olimme melkoisen yllätyksen edessä. Vaikka tällä kurssilla on maine suhteellisen helppona, tänä lukuvuonna materiaali oli erittäin vaikeaa. Tavallisten aiheiden lisäksi Bailey käytti suuren osan ajasta erilaisiin abstraktin algebran aiheisiin, erityisesti ryhmäteoriaan. Noin 35 % luokasta jätti kurssin kesken määräajassa.
Viikoittaiset kotitehtävät julkaistiin yleensä keskiviikkoisin, jotta ne olisi pitänyt tehdä seuraavana maanantaina (meille luvattiin 10 päivää aikaa tehdä ne, mutta harvoin saimme yli 5 päivää). Ne olivat hyvin todistusintensiivisiä ja veivät huomattavasti 10-15+ tuntia aikaa. Lukuun ottamatta hyvin harvoja matematiikan pääaineopiskelijoita, useimmat apulaisopettajat eivät pystyneet auttamaan kotitehtävien kanssa, koska he eivät osanneet tehdä ongelmia itse, ja viettivät virka-aikansa vain pähkäilemällä kanssamme.
Bailey kuitenkin pyrki näkyvästi auttamaan opiskelijoitaan tarjoamalla ylimääräisiä virka-aikoja ja nopeita Piazzan vastauksia. Kokeet tarjottiin joko luokassa tai iltaisin, ja ne olivat yllättävän reiluja. Loppuhuomautukset: Tulin ulos tältä kurssilta elossa, panostin paljon enemmän kuin halusin, luultavasti opin paljon diskreetistä matematiikasta, mutta ottaisin helpomman professorin, jos voisin.
George (kevät 2020): YMMV: Itse nautin tästä kurssista ja pidin materiaalia mielenkiintoisena, mutta YMMV. Työmäärä oli hallittavissa, mutta tarvitsit melko paljon toimistotunteja (jotka pidettiin todella myöhään illalla ennen COVIDia) pärjätäkseen hyvin. Kahdesti viikossa julkaistiin ongelmakokonaisuuksia maanantain ja keskiviikon välisenä aikana, ja ne piti toimittaa seuraavan viikon perjantaina, ja niitä saattoi työstää parin kanssa. Luentoja varten (ennen COVIDia) meidän piti lukea ”prep” kurssin wikistä ennen tuntia, ja tunnilla tehtiin lähinnä esimerkkejä ja iClicker-kysymyksiä käsitteen vahvistamiseksi. Verkkoon siirtymisen jälkeisillä luennoilla opetettiin enemmän materiaalia itse luennon aikana. Kaiken kaikkiaan aika vaikea kurssi, mutta palkitseva, kun sen on suorittanut.
Past Offerings
Hopcroft opettaa tätä tyypillisesti syksyllä ja Pass, keväällä. Kozen tosin opettaa tätä syksyllä 2013. Michael George tuli tilalle syksyllä 2014. Anke van Zuylen opettaa tätä syksystä 2020 alkaen.