Informazioni generali
Discrete Structures è un nome strano – avrebbe più senso il nome Discrete Mathematics. Questo significa fondamentalmente la matematica che non è continua (cioè il calcolo).
Pre-requisiti
Nessuno
Temi trattati
- Insiemi, funzioni, relazioni
- Tecniche di dimostrazione, induzione
- Teoria dei numeri e crittografia a chiave pubblica
- Conteggio e combinatoria
- Probabilità
- Logica
- Teoria dei grafi
- Automi finiti e linguaggi regolari
- Linguaggi senza contestofree languages
- Computabilità e NP-CompletenessMolto tempo dedicato alle prove e all’enfasi sulle prove per induzione.
Carico di lavoro
Di solito ci sono serie di problemi settimanali, 2-3 preliminari e un finale. Storicamente, i compiti a casa sono una parte relativamente grande del voto. Non c’è programmazione nel corso e il carico di lavoro è ragionevolmente costante per tutto il semestre. Non è significativamente pesante, ma può richiedere fino a qualche ora a settimana a seconda di quanto bene si capiscono gli argomenti.
Consiglio generale
Prendere questo corso in concomitanza con CS 2110 è molto gestibile e utile. C’è molta sovrapposizione negli argomenti, specialmente per quanto riguarda le prove per induzione e la teoria dei grafi (anche se la sovrapposizione è diminuita di recente, specialmente perché il 2110 si è concentrato meno sulle prove) ed è utile vedere le informazioni due volte. Questa classe è un fondamento per molto CS, quindi è bene prenderla abbastanza presto. Imparare la teoria dei grafi e le prove è ragionevolmente importante per molti corsi di livello superiore e per la CS in generale.
Ho trovato il libro di testo consigliato/richiesto molto utile! Molti argomenti che sono stati trattati brevemente in classe sono stati approfonditi nel libro di testo. Leggere il libro di testo e guardare gli esempi ha aumentato i miei punteggi nel test. Inoltre, non ho dovuto andare agli orari di ricevimento che erano solitamente molto affollati.
Non comprate il libro di testo. Inoltre, gli orari d’ufficio saranno affollati nei giorni in cui i problemi sono dovuti.
Trova quali degli studenti TA sono laureati in matematica e chiedi loro aiuto. Ne sapranno di più.
^Questa. 2800 è una classe di teoria quindi i matematici ne sapranno molto di più di quelli di CS. Inoltre, come detto prima, la teoria dei grafici, le prove e la maggior parte dell’altro materiale che si impara è molto utile per ragionare su vari problemi.
Testimonianze
Con Bart Selman, ho pensato che questo corso fosse davvero facile. Se avete qualche esposizione agli argomenti prima di questo corso (matematica del liceo e/o altri corsi di CS, come CS 1114), dovreste essere in grado di dedicare un tempo minimo a questo corso.
Sono stato molto coinvolto nella matematica al liceo e ho fatto un po’ di teoria dei numeri/combinatoria, e questo corso non è andato oltre a questo. Inoltre, ho preso contemporaneamente MATH 3360, che è fondamentalmente una versione molto più difficile di questo corso, quindi ho finito per imparare quasi nulla in 2800.
Preso con Pass. Questo corso era uno scherzo e ho imparato pochissimo materiale nuovo, ma è stato un buon ripasso di tutta la matematica casuale che per lo più non si era presentata ufficialmente nei miei corsi prima. Comunque, poco impegnativo e abbastanza interessante.
Con Kozen (autunno 2013) il corso non è stato terribilmente difficile, ma è stato più difficile di quanto le altre testimonianze farebbero credere. Abbiamo avuto 8 set di problemi nel corso del semestre, ognuno dei quali ha richiesto diverse ore. Gli esami erano di difficoltà ragionevole, ma i preliminari in classe erano difficili da finire nel tempo dato. (Rendetevi conto che, a meno che non abbiate già seguito un corso di matematica discreta, vedrete molti argomenti per la prima volta.
Kozen (autunno 2013): Kozen è stato un ottimo docente e ha spiegato tutto in dettaglio. Il problema era che è andato molto più in dettaglio di quanto una classe di ampiezza dovrebbe fare, quindi stavamo imparando un sacco di argomenti diversi con una profondità decente molto rapidamente. Ancora non troppo difficile, ma questo significava molto materiale e molte specifiche da memorizzare per gli esami (la testimonianza di cui sopra lo spiega bene). Gli appunti del corso di Pass (vedi link sotto) sono stati molto utili, ma Kozen ha coperto alcuni argomenti diversi. Il libro non era troppo utile, ma ne avevi bisogno, dato che alcuni problemi erano tratti dal libro.
Graeme Bailey (primavera 2014): Abbiamo avuto una bella sorpresa. Anche se questa classe ha la reputazione di essere relativamente facile, questo semestre il materiale era molto difficile. Oltre ai soliti argomenti, Bailey ha speso una gran parte del tempo su vari argomenti di algebra astratta, specialmente la teoria dei gruppi. Circa il 35% della classe ha abbandonato entro la scadenza.
I compiti settimanali erano di solito rilasciati il mercoledì per essere consegnati il lunedì successivo (ci erano stati promessi 10 giorni per farli, ma raramente ne abbiamo avuti più di 5). Erano molto intensivi e richiedevano 10-15+ ore di tempo. A parte i pochissimi laureati in matematica, la maggior parte degli assistenti non erano in grado di aiutare con i compiti a casa perché non sapevano come fare i problemi da soli, e passavano le loro ore d’ufficio a discutere con noi.
Nonostante, Bailey ha fatto un notevole sforzo per aiutare i suoi studenti, offrendo ore d’ufficio extra e risposte veloci su Piazza. I test sono stati offerti sia in classe che di sera, e sono stati sorprendentemente equi. Osservazioni conclusive: Sono uscito vivo da questa classe, mi sono impegnato molto più di quanto volessi, probabilmente ho imparato molto sulla matematica discreta, ma prenderei un professore più facile se potessi.
George (Primavera 2020): Personalmente ho apprezzato molto questa classe e ho trovato il materiale interessante, ma YMMV. Il carico di lavoro era gestibile, ma avevi praticamente bisogno di ore di ufficio (che si tenevano davvero a tarda notte pre-COVID) per fare bene. I set di problemi bisettimanali venivano rilasciati tra lunedì e mercoledì e dovevano essere consegnati il venerdì della settimana successiva, e si poteva lavorare su di essi con un partner. Per le lezioni (pre-COVID), dovevamo leggere la “preparazione” sul wiki del corso prima della lezione, e trascorrevamo la lezione principalmente facendo esempi e domande iClicker per rafforzare il concetto. Le lezioni dopo essere andate online hanno insegnato più del materiale durante la lezione stessa. Nel complesso un corso piuttosto difficile, ma gratificante una volta finito.
Offerte passate
Hopcroft lo insegna tipicamente in autunno e Pass, in primavera. Kozen lo insegna in autunno 2013, però. Michael George è subentrato nell’autunno 2014. Anke van Zuylen lo insegnerà a partire dall’autunno 2020.