Generel information
Diskrete strukturer er et mærkeligt navn – det ville give mere mening at kalde det Diskret matematik. Det betyder dybest set matematik, der ikke er kontinuert (dvs. regning).
Forudsætninger
Ingen
Dækkede emner
- Mængder, funktioner, relationer
- Bevisteknikker, induktion
- Nummerteori og kryptering af offentlige nøgler
- Tælling og kombinatorik
- Sandsynlighed
- Logik
- Grafiteori
- Finite automata og regulære sprog
- Kontekst-frie sprog
- Komputerbarhed og NP-komplethedMeget tid brugt på beviser og vægt på beviser ved induktion.
Arbejdsbyrde
Overordnet er der ugentlige problemsæt, 2-3 prelims og en afsluttende prøve. Historisk set udgør lektier en relativt stor del af karakteren. Der er ingen programmering i kurset, og arbejdsbyrden er rimelig ensartet gennem hele semesteret. Ikke væsentligt tungt, men kan tage op til et par timer om ugen afhængig af hvor godt du forstår emnerne.
Generelle råd
Det er meget overskueligt og nyttigt at tage dette sideløbende med CS 2110. Der er en masse overlapning i emnerne, især i forbindelse med beviser ved induktion og grafteori (selv om overlapningen er blevet mindre på det seneste, især fordi 2110 er kommet til at fokusere mindre på beviser), og det er nyttigt at se oplysningerne to gange. Denne klasse er et fundament for en masse CS, så det er godt at tage den rimeligt tidligt. At lære grafteori og beviser er rimeligt vigtigt for mange kurser på højere niveau og generel CS.
Jeg fandt den anbefalede/forudsatte lærebog meget nyttig! En masse emner, der blev kortfattet behandlet i klassen, blev behandlet i dybden i lærebogen. Læsning af lærebogen og gennemlæsning af eksemplerne øgede mine resultater på prøven. Desuden behøvede jeg ikke at gå til kontortid, som normalt var meget overfyldt.
Køb ikke lærebogen. Desuden vil kontortimerne være overfyldte de dage, hvor der skal afleveres problemsæt.
Find ud af, hvilke af de studerende TA’s der har matematik som hovedfag, og bed dem om hjælp. De vil vide mere.
^Dette. 2800 er et teorikursus, så matematikere vil vide meget mere om dette end CS-folk. Desuden, som nævnt før, er grafteori, beviser og det meste af det andet materiale, du lærer, meget nyttigt til at ræsonnere om forskellige problemer.
Testimonials
Med Bart Selman syntes jeg, at denne klasse var virkelig let. Hvis du har nogen eksponering for emnerne før dette kursus (gymnasiematematik og/eller andre CS-klasser, som CS 1114), burde du kunne bruge minimal tid på dette kursus.
Jeg var meget involveret i matematik i gymnasiet og lavede noget talteori/kombinatorik, og dette kursus kom ikke videre end det. Desuden tog jeg samtidig MATH 3360, som dybest set er en meget sværere version af dette kursus, så jeg endte med at lære næsten ingenting i 2800.
Tog det med bestået. Dette kursus var en joke, og jeg lærte meget lidt nyt materiale, men det var en god gennemgang af al den tilfældige matematik, som for det meste ikke officielt var dukket op i mine klasser før. Lav vedligeholdelse og interessant nok dog.
Med Kozen (Fall 2013) var kurset ikke forfærdelig svært, men var sværere end de andre testimonials ville få dig til at tro. Vi havde 8 problemsæt i løbet af semesteret, som hver især tog flere timer. In eksamenerne var rimelige sværhedsgradsmæssigt, men in class prelims var svære at gennemføre inden for den givne tid. (Der var masser af tid til finalen.) Indse, at medmindre du allerede har taget en diskret matematik klasse, vil du se mange af emnerne for første gang.
Kozen (Fall 2013): Kozen var en meget god foredragsholder og forklarede alt i detaljer. Problemet var, at han gik langt mere i detaljer, end en breddeklasse bør gøre, så vi lærte en masse forskellige emner med en ordentlig dybde meget hurtigt. Stadig ikke for svært, men det betød en masse materiale og mange specifikke ting, som skulle læres udenad til eksamen (ovenstående vidnesbyrd forklarer dette godt). Pass’s kursusnoter (se link nedenfor) var meget nyttige, men Kozen dækkede nogle forskellige emner. Bogen var ikke alt for nyttig, men man havde brug for den, da nogle få problemer var fra bogen.
Graeme Bailey (Spring 2014): Vi fik os noget af en overraskelse. Selvom denne klasse har ry for at være relativt let, var materialet i dette semester meget svært. Udover de sædvanlige emner brugte Bailey en stor del af tiden på forskellige emner inden for abstrakt algebra, især gruppeteori. Ca. 35% af klassen faldt fra inden for tidsfristen.
De ugentlige hjemmeopgaver blev normalt udgivet om onsdagen for at skulle afleveres den følgende mandag (vi blev lovet 10 dage til at lave dem, men fik sjældent mere end 5). De var meget bevisintensive og krævede et betydeligt tidsforbrug på 10-15+ timer. Bortset fra de meget få matematikstuderende var de fleste TA’er ikke i stand til at hjælpe med hjemmeopgaverne, da de ikke vidste, hvordan de selv skulle løse problemerne, og de brugte deres kontortid på bare at tøffe med os.
Uanset dette gjorde Bailey en mærkbar indsats for at hjælpe sine studerende, idet han tilbød ekstra kontortid og hurtige svar på Piazza. Prøverne blev tilbudt enten i klassen eller om aftenen og var overraskende retfærdige. Afsluttende bemærkninger: Jeg kom ud af dette kursus i live, gjorde en større indsats end jeg ønskede, lærte sandsynligvis en masse om diskret matematik, men ville tage en lettere professor, hvis jeg kunne.
George (forår 2020): Jeg personligt nød virkelig denne klasse og fandt materialet interessant, men YMMV. Arbejdsbyrden var overkommelig, men man havde stort set brug for kontortid (som blev afholdt virkelig sent om aftenen før COVID) for at klare sig godt. Der blev udgivet to ugentlige problemsæt mellem mandag og onsdag, og de skulle afleveres fredag i den følgende uge, og man kunne arbejde på dem sammen med en partner. Til forelæsninger (før COVID) skulle vi læse “prep” på kursus-wiki’en før undervisningen, og vi brugte timerne mest på at lave eksempler og iClicker-spørgsmål for at styrke begrebet. Under forelæsningerne efter at vi gik online, lærte vi mere om stoffet under selve forelæsningen. Samlet set et ret svært kursus, men givende, når man først er færdig med det.
Past Offerings
Hopcroft underviser typisk i dette i efteråret og Pass, i foråret. Kozen underviser dog i dette i efteråret 2013. Michael George tog over i efteråret 2014. Anke van Zuylen vil undervise dette fra efteråret 2020.