Informacje ogólne
Struktury dyskretne to dziwna nazwa – więcej sensu miałaby nazwa Matematyka dyskretna. To w zasadzie oznacza matematykę, która nie jest ciągła (np. rachunek).
Prerequisites
None
Topics Covered
- Sets, functions, relations
- Proof techniques, indukcja
- Teoria liczb i szyfrowanie z kluczem publicznym
- Liczenie i kombinatoryka
- Prawdopodobność
- Logika
- Teoria grafów
- Automaty skończone i języki regularne
- Językifree languages
- Computability and NP-CompletenessWiele czasu poświęcono na dowody i nacisk na dowody przez indukcję.
Obciążenie pracą
Zwykle są cotygodniowe zestawy problemów, 2-3 prelimsy, i finał. Historycznie, praca domowa jest stosunkowo duża część oceny. Nie ma programowania w kursie i obciążenie pracą jest w miarę spójne przez cały semestr. Nie jest znacząco ciężki, ale może zająć do kilku godzin tygodniowo w zależności od tego, jak dobrze rozumiesz tematy.
Ogólne porady
Branie tego równolegle z CS 2110 jest bardzo łatwe do opanowania i pomocne. Istnieje wiele pokrywających się tematów, szczególnie odnoszących się do dowodów przez indukcję i teorii grafów (chociaż nakładanie się ostatnio zmniejszyło się, zwłaszcza że 2110 mniej koncentruje się na dowodach) i pomocne jest zobaczenie informacji dwa razy. Ta klasa jest podstawą dla wielu CS, więc dobrze jest wziąć ją w miarę wcześnie. Nauka teorii grafów i dowodów jest dość ważna dla wielu kursów wyższego poziomu i ogólnego CS.
Zauważyłem, że zalecany/wymagany podręcznik jest bardzo pomocny! Wiele tematów, które zostały pokrótce omówione w klasie, zostało dogłębnie omówionych w podręczniku. Czytanie podręcznika i przeglądanie przykładów podniosło moje wyniki na teście. Ponadto, nie musiałem chodzić na godziny urzędowania, które zazwyczaj były bardzo zatłoczone.
Nie kupuj podręcznika. Również, godziny urzędowania będą zatłoczone w dniach, w których zestawy zadań są należne.
Dowiedz się, który z TA studentów jest magistrem matematyki i poproś ich o pomoc. Będą wiedzieć więcej.
^Ten. 2800 jest klasą teorii, więc matematycy będą wiedzieć o wiele więcej na ten temat niż ludzie CS. Ponadto, jak wspomniano wcześniej, teoria grafów, dowody i większość innych materiałów, których się uczysz, jest bardzo przydatna do rozumowania o różnych problemach.
Testimonials
Z Bartem Selmanem, myślałem, że ta klasa była naprawdę łatwa. Jeśli masz jakąkolwiek ekspozycję na tematy przed tą klasą (matematyka w szkole średniej i / lub inne zajęcia CS, takie jak CS 1114), powinieneś być w stanie spędzić minimalny czas na tej klasie.
Byłem bardzo zaangażowany w matematykę w szkole średniej i zrobiłem trochę teorii liczb / kombinatoryki, a ten kurs nie posunął się dalej niż to. Ponadto, równolegle wziąłem MATH 3360, który jest w zasadzie dużo trudniejszą wersją tego kursu, więc skończyło się na tym, że nie nauczyłem się prawie niczego w 2800.
Zdałem go z Pass. Ta klasa była żartem i nauczyłem się bardzo mało nowego materiału, ale był to dobry przegląd wszystkich przypadkowych matematyk, które w większości nie pojawiły się oficjalnie w moich klasach wcześniej. Niskie utrzymanie i wystarczająco interesujące chociaż.
Z Kozen (Fall 2013) kurs nie był strasznie trudny, ale był trudniejszy niż inne referencje doprowadziłyby cię do uwierzenia. Mieliśmy 8 zestawów problemów w ciągu semestru, z których każdy zajął kilka godzin. W egzaminy były rozsądne trudności mądry, ale w klasie prelims były trudne do zakończenia w danym czasie. (Było mnóstwo czasu na finał.) Zdaj sobie sprawę, że o ile nie wziąłeś już klasy matematyki dyskretnej, będziesz widział wiele tematów po raz pierwszy.
Kozen (jesień 2013): Kozen był bardzo dobrym wykładowcą i wyjaśnił wszystko w szczegółach. Problemem było to, że poszedł o wiele bardziej szczegółowo niż klasa szerokości powinien zrobić, więc byliśmy uczenia się wiele różnych tematów z przyzwoitą głębią bardzo szybko. Nadal nie było to zbyt trudne, ale oznaczało dużo materiału i wiele konkretów do zapamiętania na egzaminy (powyższy testimonial dobrze to wyjaśnia). Notatki z kursu Passa (patrz link poniżej) były bardzo przydatne, ale Kozen poruszał trochę inne tematy. Książka nie była zbyt przydatna, ale była potrzebna, ponieważ kilka problemów było z książki.
Graeme Bailey (wiosna 2014): Byliśmy w na dość niespodziankę. Chociaż ta klasa ma reputację stosunkowo łatwej, w tym semestrze materiał był bardzo trudny. Oprócz zwykłych tematów, Bailey spędził dużą część czasu na różnych tematach algebry abstrakcyjnej, zwłaszcza teorii grup. Około 35% klasy odpadło w terminie.
Tygodniowe prace domowe były zwykle wydawane w środy, aby być należne w następny poniedziałek (obiecano nam 10 dni na ich zrobienie, ale rzadko dostawaliśmy więcej niż 5). Były one bardzo intensywne i zajmowały znaczące 10-15+ godzin czasu. Poza nielicznymi magistrami matematyki, większość wykładowców nie była w stanie pomóc z pracami domowymi, ponieważ nie wiedzieli, jak sami rozwiązywać problemy, i spędzali swoje godziny biurowe po prostu męcząc się z nami.
Niezależnie od tego, Bailey podjął zauważalny wysiłek, aby pomóc swoim studentom, oferując dodatkowe godziny biurowe i szybkie odpowiedzi na Piazzie. Testy były oferowane w klasie lub w stylu wieczorowym i były zaskakująco uczciwe. Uwagi końcowe: Wyszedłem z tej klasy żywy, włożyłem dużo więcej wysiłku, niż chciałem, prawdopodobnie nauczyłem się dużo o matematyce dyskretnej, ale wziąłbym łatwiejszego profesora, gdybym mógł.
George (Wiosna 2020): Osobiście naprawdę podobała mi się ta klasa i uznałem materiał za interesujący, ale YMMV. Obciążenie pracą było możliwe do opanowania, ale dość mocno potrzebowałeś godzin biurowych (które odbywały się naprawdę późno w nocy pre-COVID), aby dobrze sobie poradzić. Dwutygodniowe zestawy problemów były publikowane między poniedziałkiem a środą i wymagalne w piątek następnego tygodnia, i można było pracować nad nimi z partnerem. Na wykładach (pre-COVID), mieliśmy czytać „prep” na wiki kursu przed zajęciami, i spędziliśmy zajęcia głównie robiąc przykłady i pytania iClicker, aby wzmocnić koncepcję. Wykłady po przejściu do trybu online nauczały więcej materiału podczas samego wykładu. Ogólnie dość trudna klasa, ale satysfakcjonująca kiedy już ją skończysz.
Poprzednie oferty
Hopcroft zazwyczaj uczy tego na jesieni i Pass, na wiosnę. Kozen uczy tego w jesieni 2013, chociaż. Michael George przejął to w jesieni 2014. Anke van Zuylen będzie tego nauczać od jesieni 2020.
.