Información general
Discrete Structures es un nombre raro – tendría más sentido ser llamado Discrete Mathematics. Esto significa básicamente las matemáticas que no son continuas (es decir, el cálculo).
Requisitos previos
Ninguno
Temas tratados
- Conjuntos, funciones, relaciones
- Técnicas de prueba, inducción
- Teoría de números y encriptación de clave pública
- Cuento y combinatoria
- Probabilidad
- Lógica
- Teoría de grafos
- Autómatas finitos y lenguajes regulares
- Lenguajes libres de contextolenguajes libres
- Computabilidad y NP-CompletenessMucho tiempo dedicado a las pruebas y énfasis en las pruebas por inducción.
Carga de trabajo
Por lo general, hay conjuntos de problemas semanales, 2-3 preliminares, y un final. Históricamente, los deberes son una parte relativamente grande de la nota. No hay programación en el curso y la carga de trabajo es razonablemente consistente a lo largo del semestre. No es significativamente pesado, pero puede tomar hasta un par de horas a la semana dependiendo de lo bien que entiendas los temas.
Consejo General
Tomar esto simultáneamente con CS 2110 es muy manejable y útil. Hay mucho solapamiento en los temas especialmente relacionados con las pruebas por inducción y la teoría de grafos (aunque el solapamiento ha disminuido recientemente, especialmente porque 2110 se ha centrado menos en las pruebas) y es útil ver la información dos veces. Esta clase es una base para muchos CS, por lo que es bueno tomarla razonablemente temprano. Aprender la teoría de grafos y las pruebas es razonablemente importante para muchos cursos de nivel superior y CS general.
¡Encontré el libro de texto recomendado/requerido muy útil! Muchos de los temas que se trataron brevemente en clase se trataron en profundidad en el libro de texto. La lectura del libro de texto y el repaso de los ejemplos aumentaron mi puntuación en el examen. Además, no tuve que ir a las horas de oficina que normalmente estaban muy llenas.
No compre el libro de texto. Además, las horas de oficina estarán abarrotadas los días en que hay que entregar los conjuntos de problemas.
Averigua cuáles de los estudiantes de TA son licenciados en matemáticas y pídeles ayuda. Ellos sabrán más.
^Esto. 2800 es una clase de teoría por lo que los matemáticos sabrán mucho más sobre esto que la gente de CS. También, como se mencionó antes, la teoría de grafos, pruebas, y la mayoría del otro material que se aprende es muy útil para el razonamiento sobre diversos problemas.
Testimonios
Con Bart Selman, pensé que esta clase era realmente fácil. Si usted tiene alguna exposición a los temas antes de esta clase (matemáticas de la escuela secundaria y / u otras clases de CS, como CS 1114), usted debe ser capaz de pasar un tiempo mínimo en esta clase.
Estuve muy involucrado en las matemáticas en la escuela secundaria e hice algo de teoría de números / combinatoria, y este curso no avanzó más que eso. Además, tomé simultáneamente MATH 3360, que es básicamente una versión mucho más difícil de este curso, por lo que terminé aprendiendo casi nada en el 2800.
Lo tomé con el aprobado. Esta clase fue una broma y aprendí muy poco material nuevo, pero fue un buen repaso de todas las matemáticas al azar que en su mayoría no habían aparecido oficialmente en mis clases antes. Bajo mantenimiento y lo suficientemente interesante sin embargo.
Con Kozen (Otoño 2013) el curso no era terriblemente difícil, pero era más difícil que los otros testimonios te hacen creer. Tuvimos 8 conjuntos de problemas en el transcurso del semestre, cada uno de los cuales tomó varias horas. Los exámenes internos tenían una dificultad razonable, pero los preliminares en clase eran difíciles de terminar en el tiempo previsto. (Hubo mucho tiempo para el final.) Date cuenta de que a menos que ya hayas tomado una clase de matemáticas discretas, estarás viendo muchos de los temas por primera vez.
Kozen (Otoño 2013): Kozen fue un muy buen profesor y explicó todo con detalle. El problema fue que entró mucho más en detalle de lo que debería hacer una clase de amplitud, por lo que estábamos aprendiendo un montón de temas diferentes con una profundidad decente muy rápidamente. Aún así, no era demasiado difícil, pero eso significaba mucho material y muchos detalles que memorizar para los exámenes (el testimonio anterior lo explica bien). Los apuntes del curso de Pass (ver enlace más abajo) fueron muy útiles, pero Kozen cubrió algunos temas diferentes. El libro no era demasiado útil, pero sí lo necesitabas ya que algunos problemas eran del libro.
Graeme Bailey (primavera 2014): Nos llevamos una gran sorpresa. Aunque esta clase tiene fama de ser relativamente fácil, este semestre el material era muy difícil. Además de los temas habituales, Bailey dedicó una gran parte del tiempo a varios temas de álgebra abstracta, especialmente la teoría de grupos. Aproximadamente el 35% de la clase abandonó en el plazo previsto.
Los trabajos semanales se soltaban normalmente los miércoles para ser entregados el lunes siguiente (se nos prometían 10 días para hacerlos, pero rara vez conseguíamos más de 5). Eran muy intensivos en cuanto a pruebas y requerían un tiempo significativo de 10-15+ horas. Aparte de los pocos licenciados en matemáticas, la mayoría de los tutores no podían ayudar con los trabajos en casa, ya que no sabían cómo hacer los problemas ellos mismos, y pasaban sus horas de oficina simplemente dando vueltas con nosotros.
A pesar de ello, Bailey se esforzó notablemente en ayudar a sus estudiantes, ofreciendo horas de oficina adicionales y respuestas rápidas en Piazza. Los exámenes se ofrecían en clase o por la tarde, y eran sorprendentemente justos. Comentarios finales: Salí vivo de esta clase, me esforcé mucho más de lo que quería, probablemente aprendí mucho sobre matemáticas discretas, pero tomaría un profesor más fácil si pudiera.
George (Primavera 2020): Personalmente disfruté mucho de esta clase y encontré el material interesante, pero YMMV. La carga de trabajo era manejable, pero se necesitaban horas de oficina (que se llevaban a cabo muy tarde en la noche pre-COVID) para hacerlo bien. Los problemas quincenales se publicaban entre el lunes y el miércoles y había que entregarlos el viernes de la semana siguiente, y se podía trabajar en ellos con un compañero. Para las clases (pre-COVID), se suponía que debíamos leer la «preparación» en la wiki del curso antes de la clase, y pasábamos la clase principalmente haciendo ejemplos y preguntas de iClicker para reforzar el concepto. Las conferencias después de ir en línea enseñó más del material durante la propia conferencia. En general una clase bastante difícil, pero gratificante una vez que la terminas.
Ofertas anteriores
Hopcroft normalmente enseña esto en el otoño y Pass, en la primavera. Sin embargo, Kozen lo enseña en otoño de 2013. Michael George tomó el relevo en otoño de 2014. Anke van Zuylen lo enseñará a partir del otoño de 2020.