Allmän information
Diskreta strukturer är ett konstigt namn – det skulle vara vettigare om det hette diskret matematik. Det betyder i princip matematik som inte är kontinuerlig (dvs. kalkyl).
Förutsättningar
Ingen
Teman som behandlas
- Mängder, funktioner, relationer
- Bevisningstekniker, induktion
- Nummerteori och kryptering av offentliga nycklar
- Räkning och kombinatorik
- Sannolikhet
- Logik
- Grafteori
- Finita automater och reguljära språk
- Kontext-fria språk
- Beräknelighet och NP-kompletthet Mycket tid läggs på bevis och tonvikt på bevis genom induktion.
Arbetsbelastning
I vanliga fall finns det problemställningar varje vecka, 2-3 förprov och ett slutprov. Historiskt sett utgör läxor en relativt stor del av betyget. Det finns ingen programmering i kursen och arbetsbördan är någorlunda jämn under hela terminen. Inte nämnvärt tungt, men kan ta upp till några timmar i veckan beroende på hur väl du förstår ämnena.
Allmänt råd
Att läsa denna samtidigt med CS 2110 är mycket hanterbart och nyttigt. Det finns en hel del överlappning i ämnena, särskilt när det gäller bevis genom induktion och grafteori (även om överlappningen har minskat på senare tid, särskilt eftersom 2110 har kommit att fokusera mindre på bevis) och det är bra att se informationen två gånger. Den här kursen är en grund för många CS-kurser, så det är bra att läsa den ganska tidigt. Att lära sig grafteori och bevis är ganska viktigt för många kurser på högre nivå och allmän CS.
Jag tyckte att den rekommenderade/krävda läroboken var mycket användbar! Många ämnen som behandlades kortfattat i klassen behandlades på djupet i läroboken. Att läsa läroboken och titta på exemplen ökade mina resultat på provet. Dessutom behövde jag inte gå till kontorstiderna som vanligtvis var väldigt fullsatta.
Köp inte läroboken. Dessutom kommer kontorstiderna att vara överfulla de dagar som problemuppgifterna ska lämnas in.
Finn ut vilka av de studerande assistenterna som har matematik som huvudämne och be dem om hjälp. De kommer att veta mer.
^Detta. 2800 är en teoriklass, så matematiklärare kommer att veta mycket mer om detta än forskare i datavetenskap. Dessutom, som tidigare nämnts, är grafteori, bevis och det mesta av det andra materialet du lär dig mycket användbart för att resonera kring olika problem.
Testimonials
Med Bart Selman tyckte jag att den här klassen var riktigt lätt. Om du har någon exponering för ämnena före den här kursen (gymnasiematematik och/eller andra CS-kurser, som CS 1114) bör du kunna lägga ner minimalt med tid på den här kursen.
Jag var mycket engagerad i matematik i gymnasiet och gjorde en del talteori/kombinatorik, och den här kursen gick inte längre än så. Dessutom läste jag samtidigt MATH 3360, som i princip är en mycket svårare version av den här kursen, så det slutade med att jag lärde mig nästan ingenting i 2800.
Tog den med godkänt. Den här kursen var ett skämt och jag lärde mig väldigt lite nytt material, men det var en bra genomgång av all slumpmässig matematik som oftast inte officiellt hade dykt upp i mina kurser tidigare. Låg underhåll och tillräckligt intressant dock.
Med Kozen (hösten 2013) var kursen inte fruktansvärt svår men var svårare än vad de andra vittnesmålen får en att tro. Vi hade 8 problemställningar under terminen som var och en tog flera timmar. In tentorna var rimliga svårighetsgradsmässigt, men de preliminära tentorna i klassen var svåra att slutföra på den givna tiden. (Det fanns gott om tid för finalen.) Inse att om du inte redan har tagit en kurs i diskret matematik kommer du att se många av ämnena för första gången.
Kozen (hösten 2013): Kozen var en mycket bra föreläsare och förklarade allt i detalj. Problemet var att han gick mycket mer i detalj än vad en breddklass bör göra, så vi lärde oss många olika ämnen med ett hyfsat djup väldigt snabbt. Fortfarande inte alltför svårt, men det innebar mycket material och många detaljer att memorera inför tentorna (ovanstående vittnesmål förklarar detta väl). Pass kursanteckningar (se länk nedan) var mycket användbara, men Kozen tog upp en del olika ämnen. Boken var inte alltför användbar, men du behövde den eftersom några problem var från boken.
Graeme Bailey (våren 2014): Vi fick oss en rejäl överraskning. Även om den här klassen har ett rykte om sig att vara relativt lätt var materialet den här terminen mycket svårt. Förutom de vanliga ämnena ägnade Bailey en stor del av tiden åt olika ämnen inom abstrakt algebra, särskilt gruppteori. Ungefär 35 % av klassen hoppade av inom tidsfristen.
De veckovisa hemuppgifterna släpptes vanligtvis på onsdagar för att lämnas in följande måndag (vi lovades 10 dagar för att göra dem, men fick sällan mer än 5). De var mycket bevisintensiva och krävde en betydande tidsåtgång på 10-15+ timmar. Bortsett från de mycket få matematikstudenterna kunde de flesta lärare inte hjälpa till med hemuppgifterna eftersom de inte visste hur de skulle lösa problemen själva, och de tillbringade sina kontorstimmar med att bara famla med oss.
Oavsett detta gjorde Bailey en märkbar ansträngning för att hjälpa sina studenter, genom att erbjuda extra kontorstimmar och snabba svar på Piazza. Testerna erbjöds antingen i klassrummet eller på kvällstid och var förvånansvärt rättvisa. Avslutande kommentarer: Jag kom ut ur den här kursen levande, ansträngde mig mer än jag ville, lärde mig förmodligen mycket om diskret matematik, men skulle ta en lättare professor om jag kunde.
George (våren 2020): Jag personligen gillade verkligen den här kursen och tyckte att materialet var intressant, men YMMV. Arbetsbelastningen var hanterbar men man behövde ganska mycket kontorstimmar (som hölls riktigt sent på kvällen före COVID) för att klara sig bra. Problemställningar som kom ut varannan vecka mellan måndag och onsdag och skulle lämnas in fredagen veckan därpå, och man kunde arbeta med dem tillsammans med en partner. För föreläsningar (före COVID) var det meningen att vi skulle läsa ”prep” på kurswikin före lektionerna och tillbringade lektionerna mest med att göra exempel och iClicker-frågor för att förstärka konceptet. På föreläsningarna efter att vi började använda nätet lärde vi ut mer av materialet under själva föreläsningen. Överlag en ganska svår kurs, men givande när man väl är klar med den.
Past Offerings
Hopcroft undervisar vanligtvis denna kurs på hösten och Pass, på våren. Kozen undervisar dock denna hösten 2013. Michael George tog över hösten 2014. Anke van Zuylen kommer att undervisa detta från och med hösten 2020.