Informations générales
Les Structures discrètes sont un nom bizarre – il serait plus logique de l’appeler Mathématiques discrètes. Cela signifie essentiellement les mathématiques qui ne sont pas continues (c’est-à-dire le calcul).
Prérequis
Non
Thèmes abordés
- Ensembles, fonctions, relations
- Techniques de preuve, induction
- Théorie des nombres et chiffrement à clé publique
- Comptage et combinatoire
- Probabilité
- Logique
- Théorie des graphes
- Automates finis et langages réguliers
- Langues sans contexte
- Langues sans contexte
- Langues avec contexte.free languages
- Computabilité et NP-CompletenessBeaucoup de temps passé sur les preuves et l’accent mis sur les preuves par induction.
Charge de travail
En général, il y a des ensembles de problèmes hebdomadaires, 2-3 préliminaires et un final. Historiquement, les devoirs représentent une part relativement importante de la note. Il n’y a pas de programmation dans le cours et la charge de travail est raisonnablement cohérente tout au long du semestre. Pas significativement lourd, mais peut prendre jusqu’à quelques heures par semaine en fonction de la façon dont vous comprenez les sujets.
Conseils généraux
Prendre ce cours en même temps que CS 2110 est très gérable et utile. Il y a beaucoup de chevauchement dans les sujets, en particulier en ce qui concerne les preuves par induction et la théorie des graphes (bien que le chevauchement ait diminué récemment, en particulier parce que 2110 est venu à se concentrer moins sur les preuves) et il est utile de voir l’information deux fois. Ce cours est une base pour beaucoup de CS, donc il est bon de le prendre raisonnablement tôt. Apprendre la théorie des graphes et les preuves est raisonnablement important pour beaucoup de cours de niveau supérieur et la CS générale.
J’ai trouvé le manuel recommandé/obligatoire très utile ! Beaucoup de sujets qui ont été brièvement couverts en classe ont été couverts en profondeur dans le manuel. Lire le manuel et regarder les exemples a boosté mes résultats au test. De plus, je n’ai pas eu besoin d’aller aux heures de bureau qui étaient habituellement très bondées.
N’achetez pas le manuel. En outre, les heures de bureau seront bondées les jours où les ensembles de problèmes sont dus.
Découvrez lesquels des étudiants TA sont des majors en mathématiques et demandez-leur de l’aide. Ils en sauront plus.
Ceci. 2800 est un cours de théorie, donc les majors en maths en sauront beaucoup plus que les gens de CS. En outre, comme mentionné précédemment, la théorie des graphes, les preuves et la plupart des autres matériaux que vous apprenez sont très utiles pour raisonner sur divers problèmes.
Témoignages
Avec Bart Selman, je pensais que cette classe était vraiment facile. Si vous avez une exposition aux sujets avant ce cours (mathématiques au lycée et/ou d’autres cours de CS, comme CS 1114), vous devriez être en mesure de passer un minimum de temps sur ce cours.
J’étais très impliqué dans les mathématiques au lycée et j’ai fait un peu de théorie des nombres/combinatoire, et ce cours n’a pas progressé plus que cela. En outre, j’ai pris simultanément MATH 3360, qui est essentiellement une version beaucoup plus difficile de ce cours, de sorte que j’ai fini par apprendre presque rien dans 2800.
La prise avec Pass. Ce cours était une blague et j’ai appris très peu de nouveau matériel, mais c’était une bonne révision de toutes les mathématiques aléatoires qui, pour la plupart, n’avaient pas officiellement montré dans mes classes avant. Peu d’entretien et assez intéressant cependant.
Avec Kozen (automne 2013), le cours n’était pas terriblement difficile, mais il était plus difficile que les autres témoignages vous laisseraient croire. Nous avions 8 ensembles de problèmes au cours du semestre, chacun prenant plusieurs heures. Les examens en classe étaient d’une difficulté raisonnable, mais les examens préliminaires en classe étaient difficiles à terminer dans le temps imparti. (Il y avait beaucoup de temps pour la finale.) Réalisez que, à moins que vous ayez déjà pris un cours de mathématiques discrètes, vous verrez beaucoup de sujets pour la première fois.
Kozen (automne 2013) : Kozen était un très bon conférencier et a tout expliqué en détail. Le problème était qu’il allait beaucoup plus dans les détails que ce qu’une classe d’étendue devrait faire, donc nous apprenions beaucoup de sujets différents avec une profondeur décente très rapidement. Ce n’était pas trop difficile, mais cela signifiait beaucoup de matériel et beaucoup de détails à mémoriser pour les examens (le témoignage ci-dessus l’explique bien). Les notes de cours de Pass (voir le lien ci-dessous) étaient très utiles, mais Kozen a couvert des sujets différents. Le livre n’était pas trop utile, mais vous en aviez besoin car quelques problèmes étaient tirés du livre.
Graeme Bailey (printemps 2014) : Nous avons eu une sacrée surprise. Bien que cette classe ait la réputation d’être relativement facile, ce semestre, le matériel était très difficile. En plus des sujets habituels, Bailey a passé une grande partie du temps sur divers sujets d’algèbre abstraite, en particulier la théorie des groupes. Environ 35% de la classe a abandonné dans les délais.
Les devoirs hebdomadaires étaient généralement libérés le mercredi pour être dus le lundi suivant (on nous a promis 10 jours pour les faire, mais nous avons rarement obtenu plus de 5). Ils étaient très exigeants en matière de preuves et nécessitaient un temps significatif de 10 à 15 heures et plus. À part les très rares majors en mathématiques, la plupart des assistants techniques n’étaient pas en mesure de nous aider avec les devoirs car ils ne savaient pas comment faire les problèmes eux-mêmes, et passaient leurs heures de bureau à patauger avec nous.
Malgré tout, Bailey a fait un effort notable pour aider ses étudiants, offrant des heures de bureau supplémentaires et des réponses rapides sur Piazza. Les tests étaient offerts soit en classe, soit en soirée, et étaient étonnamment justes. Remarques finales : Sorti de cette classe vivante, mis dans beaucoup plus d’efforts que je voulais, probablement appris beaucoup sur les mathématiques discrètes, mais prendrait un professeur plus facile si je pouvais.
George (printemps 2020) : Personnellement, j’ai vraiment apprécié cette classe et j’ai trouvé le matériel intéressant, mais YMMV. La charge de travail était gérable, mais vous aviez pratiquement besoin des heures de bureau (qui se tenaient vraiment tard le soir avant COVID) pour bien faire. Toutes les deux semaines, les problèmes étaient publiés entre le lundi et le mercredi et devaient être rendus le vendredi de la semaine suivante, et vous pouviez travailler dessus avec un partenaire. Pour les cours magistraux (avant COVID), nous étions censés lire la « préparation » sur le wiki du cours avant la classe, et nous passions la classe principalement à faire des exemples et des questions iClicker pour renforcer le concept. Les cours magistraux, après avoir été mis en ligne, enseignaient davantage la matière pendant le cours lui-même. Dans l’ensemble, une classe assez difficile, mais enrichissante une fois que vous l’avez terminée.
Past Offerings
Hopcroft enseigne généralement cela à l’automne et Pass, au printemps. Kozen l’enseigne cependant à l’automne 2013. Michael George prend la relève à l’automne 2014. Anke van Zuylen l’enseignera à partir de l’automne 2020.