Allgemeine Informationen
Diskrete Strukturen ist ein seltsamer Name – es würde mehr Sinn machen, wenn man es Diskrete Mathematik nennt. Das bedeutet im Grunde Mathe, die nicht kontinuierlich ist (z.B. Kalkül).
Voraussetzungen
Keine
Behandelte Themen
- Mengen, Funktionen, Beziehungen
- Beweisverfahren, Induktion
- Zahlentheorie und Public-Key-Verschlüsselung
- Zählen und Kombinatorik
- Wahrscheinlichkeit
- Logik
- Graphentheorie
- Finite Automaten und reguläre Sprachen
- Kontext-freie Sprachen
- Berechenbarkeit und NP-VollständigkeitViel Zeit wird auf Beweise verwendet und der Schwerpunkt liegt auf Beweisen durch Induktion.
Arbeitsaufwand
In der Regel gibt es wöchentliche Problemstellungen, 2-3 Vorklausuren und eine Abschlussprüfung. Historisch gesehen machen die Hausaufgaben einen relativ großen Teil der Note aus. Im Kurs wird nicht programmiert, und die Arbeitsbelastung ist während des gesamten Semesters relativ gleichmäßig. Er ist nicht besonders schwer, kann aber einige Stunden pro Woche in Anspruch nehmen, je nachdem, wie gut Sie die Themen verstehen.
Allgemeine Ratschläge
Dieser Kurs kann gleichzeitig mit CS 2110 belegt werden und ist sehr überschaubar und hilfreich. Es gibt viele Überschneidungen bei den Themen, vor allem in Bezug auf Beweise durch Induktion und Graphentheorie (obwohl die Überschneidungen in letzter Zeit abgenommen haben, vor allem weil 2110 sich weniger auf Beweise konzentriert) und es ist hilfreich, die Informationen zweimal zu sehen. Dieser Kurs ist eine Grundlage für viele CS-Kurse, daher ist es gut, ihn relativ früh zu belegen. Das Erlernen der Graphentheorie und der Beweise ist für viele Oberstufenkurse und allgemeines CS sehr wichtig.
Ich fand das empfohlene/verlangte Lehrbuch sehr hilfreich! Viele Themen, die in der Vorlesung kurz behandelt wurden, wurden im Lehrbuch ausführlich behandelt. Die Lektüre des Lehrbuchs und das Durchsehen der Beispiele haben meine Punktzahl in der Prüfung erhöht. Außerdem musste ich nicht zu den Sprechstunden gehen, die normalerweise sehr überfüllt waren.
Kaufen Sie das Lehrbuch nicht. Außerdem werden die Sprechstunden an den Tagen, an denen die Aufgabenstellungen fällig sind, überfüllt sein.
Finden Sie heraus, welche der studentischen Assistenten Mathematik studiert haben und bitten Sie sie um Hilfe. Sie werden mehr wissen.
^Das. 2800 ist ein Theoriekurs, also werden Mathe-Majors viel mehr darüber wissen als CS-Leute. Außerdem sind, wie bereits erwähnt, Graphentheorie, Beweise und die meisten der anderen Materialien, die man lernt, sehr nützlich, um über verschiedene Probleme nachzudenken.
Testimonials
Mit Bart Selman dachte ich, dass dieser Kurs wirklich einfach war. Wenn man sich vor diesem Kurs mit den Themen beschäftigt hat (Highschool-Mathematik und/oder andere CS-Kurse, wie CS 1114), sollte man in der Lage sein, nur wenig Zeit für diesen Kurs aufzuwenden.
Ich hatte in der Highschool viel mit Mathematik zu tun und habe etwas Zahlentheorie/Kombinatorik gemacht, und dieser Kurs ging nicht weiter als das. Außerdem habe ich gleichzeitig MATH 3360 belegt, was im Grunde eine viel schwierigere Version dieses Kurses ist, so dass ich am Ende so gut wie nichts in 2800 gelernt habe.
Ich habe ihn mit „bestanden“ abgeschlossen. Dieser Kurs war ein Witz und ich habe sehr wenig neues Material gelernt, aber es war eine gute Wiederholung von all der zufälligen Mathematik, die meistens nicht offiziell in meinen vorherigen Kursen aufgetaucht war. Der Kurs ist nicht sehr anspruchsvoll und interessant genug.
Bei Kozen (Herbst 2013) war der Kurs nicht furchtbar schwer, aber schwieriger als die anderen Zeugnisse vermuten lassen. Wir hatten 8 Problemstellungen im Laufe des Semesters, die jeweils mehrere Stunden in Anspruch nahmen. Die Klausuren waren vom Schwierigkeitsgrad her angemessen, aber die Vorklausuren waren in der vorgegebenen Zeit nur schwer zu bewältigen. (Für die Abschlussprüfung war genug Zeit.) Man muss sich darüber im Klaren sein, dass man viele der Themen zum ersten Mal sieht, wenn man nicht bereits einen Kurs in diskreter Mathematik belegt hat.
Kozen (Herbst 2013): Kozen war ein sehr guter Dozent und hat alles sehr detailliert erklärt. Das Problem war, dass er viel mehr ins Detail gegangen ist, als es ein Breitenkurs tun sollte, so dass wir sehr schnell viele verschiedene Themen mit einer anständigen Tiefe gelernt haben. Trotzdem war es nicht zu schwer, aber das bedeutete eine Menge Stoff und viele Besonderheiten, die man sich für die Prüfungen merken musste (der obige Erfahrungsbericht erklärt das gut). Die Kursnotizen von Pass (siehe Link unten) waren sehr nützlich, aber Kozen behandelte einige andere Themen. Das Buch war nicht allzu nützlich, aber man brauchte es, da einige Probleme aus dem Buch stammten.
Graeme Bailey (Frühjahr 2014): Wir haben eine ziemliche Überraschung erlebt. Obwohl dieser Kurs den Ruf hat, relativ einfach zu sein, war der Stoff in diesem Semester sehr schwierig. Zusätzlich zu den üblichen Themen verbrachte Bailey einen großen Teil seiner Zeit mit verschiedenen Themen der abstrakten Algebra, insbesondere der Gruppentheorie. Ungefähr 35% der Klasse haben innerhalb der Frist abgebrochen.
Die wöchentlichen Hausaufgaben wurden in der Regel mittwochs ausgegeben und waren am folgenden Montag fällig (uns wurden 10 Tage versprochen, um sie zu bearbeiten, aber wir bekamen selten mehr als 5). Sie waren sehr beweisintensiv und erforderten einen erheblichen Zeitaufwand von 10-15+ Stunden. Abgesehen von den wenigen Mathe-Hauptfächern waren die meisten Betreuer nicht in der Lage, uns bei den Hausaufgaben zu helfen, da sie selbst nicht wussten, wie man die Probleme löst, und ihre Sprechstunden damit verbrachten, uns zu vertrösten.
Ungeachtet dessen bemühte sich Bailey spürbar, seinen Studenten zu helfen, indem er zusätzliche Sprechstunden anbot und schnelle Antworten auf Piazza gab. Die Prüfungen wurden entweder in der Klasse oder am Abend angeboten und waren überraschend fair. Abschließende Bemerkungen: Ich bin lebendig aus diesem Kurs herausgekommen, habe mich mehr angestrengt, als ich wollte, habe wahrscheinlich eine Menge über diskrete Mathematik gelernt, würde aber einen einfacheren Professor nehmen, wenn ich könnte.
George (Frühjahr 2020): Ich persönlich habe diesen Kurs wirklich genossen und fand das Material interessant, aber YMMV. Das Arbeitspensum war überschaubar, aber man brauchte die Sprechstunden (die in der Zeit vor COVID wirklich spät in der Nacht stattfanden), um gut abzuschneiden. Zweiwöchentliche Problemstellungen wurden zwischen Montag und Mittwoch veröffentlicht und waren am Freitag der folgenden Woche fällig, und man konnte sie mit einem Partner bearbeiten. Für die Vorlesungen (vor COVID) sollten wir vor dem Unterricht die „Vorbereitung“ im Kurs-Wiki lesen und den Unterricht hauptsächlich mit Beispielen und iClicker-Fragen verbringen, um das Konzept zu festigen. In den Vorlesungen, nachdem wir online gegangen waren, wurde der Stoff eher in der Vorlesung selbst vermittelt. Insgesamt ein ziemlich schwieriger Kurs, aber lohnend, wenn man ihn beendet hat.
Vergangene Angebote
Hopcroft unterrichtet dies normalerweise im Herbst und Pass im Frühjahr. Kozen unterrichtet dies jedoch im Herbst 2013. Michael George hat es im Herbst 2014 übernommen. Anke van Zuylen wird dies ab Herbst 2020 unterrichten.