Informação Geral
Estruturas Discretas é um nome estranho – faria mais sentido ser chamado de Matemática Discreta. Isto basicamente significa matemática que não é contínua (isto é, cálculo).
Prrequisitos
Nenhum
Tópicos Cobertos
- Sets, funções, relações
- Técnicas à prova, indução
- Teoria do número e criptografia de chave pública
- Contagem e combinatórias
- Probabilidade
- Lógica
- Teoria do gráfico
- Autómatos finitos e linguagens regulares
- Contexto-idiomas livres
- Computabilidade e NP-CompletenessUma grande quantidade de tempo gasto em provas e ênfase em provas por indução.
Carga de trabalho
Usualmente há conjuntos de problemas semanais, 2-3 preliminares, e uma final. Historicamente, o trabalho de casa é uma porção relativamente grande da nota. Não há programação no curso e a carga de trabalho é razoavelmente consistente ao longo do semestre. Não é significativamente pesado, mas pode levar até algumas horas por semana até que você entenda bem os tópicos.
Conselho Geral
Tocalizar isso concomitantemente com o CS 2110 é muito manejável e útil. Há muita sobreposição em tópicos especialmente relacionados a provas por indução e teoria gráfica (embora a sobreposição tenha diminuído recentemente, especialmente porque o 2110 passou a focar menos em provas) e é útil ver as informações duas vezes. Esta aula é uma base para muitas CS, por isso é bom tomar razoavelmente cedo. A teoria e as provas dos gráficos de aprendizagem é razoavelmente importante para muitos cursos de nível superior e CS gerais.
Eurou muito útil o livro-texto recomendado/requerido! Muitos tópicos que foram brevemente abordados nas aulas foram abordados em profundidade no livro didático. A leitura do livro didático e a leitura dos exemplos melhoraram a minha pontuação no teste. Além disso, não tive que ir ao horário de expediente, que normalmente era muito lotado.
Não compre o livro didático. Além disso, o horário de expediente estará lotado nos dias em que os problemas forem resolvidos.
Encontre quais das TAs dos alunos são de matemática e peça ajuda a eles. Eles saberão mais.
^Esta. 2800 é uma aula teórica para que os alunos de matemática saibam muito mais sobre isso do que os alunos de CS. Também, como mencionado anteriormente, teoria gráfica, provas e a maioria do outro material que você aprende é muito útil para raciocinar sobre vários problemas.
Testemunhos
Com Bart Selman, eu achei que esta aula foi muito fácil. Se você tiver alguma exposição aos tópicos antes desta aula (matemática do ensino médio e/ou outras aulas de CS, como CS 1114), você deve ser capaz de gastar um tempo mínimo nesta aula.
Eu estava muito envolvido com matemática no ensino médio e fiz alguma teoria/combinatória de números, e este curso não progrediu mais do que isso. Além disso, eu também fiz MATH 3360, que é basicamente uma versão muito mais difícil deste curso, então eu acabei aprendendo quase nada em 2800.
Tornei-o com Pass. Esta aula foi uma brincadeira e aprendi muito pouco material novo, mas foi uma boa revisão de toda a matemática aleatória que na sua maioria não tinha aparecido oficialmente nas minhas aulas antes. Com Kozen (Outono de 2013) o curso não foi muito difícil, mas foi mais difícil do que os outros depoimentos o levariam a acreditar. Tivemos 8 conjuntos de problemas ao longo do semestre, cada um dos quais demorou várias horas. Os exames foram de dificuldade razoável, mas os exames preliminares em sala de aula foram difíceis de terminar no tempo dado. (Havia muito tempo para a final.) Perceba que a menos que você já tenha feito uma aula de matemática discreta, você estará vendo muitos dos tópicos pela primeira vez.
Kozen (Outono de 2013): Kozen foi um excelente orador e explicou tudo em detalhe. O problema é que ele entrou muito mais em detalhes do que uma aula de matemática deveria fazer, então nós estávamos aprendendo muitos tópicos diferentes com uma profundidade decente muito rapidamente. Ainda não foi muito difícil, mas isso significou muito material e muitas especificidades para memorizar para os exames (o testemunho acima explica bem isto). As notas de curso do passe (ver link abaixo) foram muito úteis, mas Kozen cobriu alguns assuntos diferentes. O livro não foi muito útil, mas você precisou dele, pois alguns problemas foram do livro.
Graeme Bailey (Primavera de 2014): Estávamos para uma grande surpresa. Embora esta aula tenha a reputação de ser relativamente fácil, neste semestre o material foi muito difícil. Além dos tópicos habituais, Bailey passou uma grande parte do tempo em vários tópicos de álgebra abstrata, especialmente a teoria de grupo. Aproximadamente 35% da turma caiu dentro do prazo.
Os trabalhos de casa semanais geralmente eram liberados às quartas-feiras para serem entregues na segunda-feira seguinte (nos foi prometido 10 dias para fazê-los, mas raramente conseguimos mais de 5). Eles eram muito intensivos e demoravam mais de 10-15 horas. Além das poucas áreas de matemática, a maioria dos TAs não conseguiam ajudar com os trabalhos de casa, pois não sabiam como fazer os problemas por conta própria, e passavam as horas de expediente apenas a flertar connosco.
Independentemente disso, Bailey fez um esforço notável para ajudar os seus alunos, oferecendo horas extras de expediente e respostas rápidas da Piazza. Os testes foram oferecidos em sala de aula ou à noite, e foram surpreendentemente justos. Observações finais: Saí desta aula vivo, esforcei-me muito mais do que eu queria, provavelmente aprendi muito sobre matemática discreta, mas seria mais fácil para um professor se eu pudesse.
George (Primavera de 2020): Eu pessoalmente gostei muito desta aula e achei o material interessante, mas o YMMV. A carga de trabalho era manejável, mas você precisava muito do horário de expediente (que era realizado muito tarde à noite antes do COVID) para se sair bem. Os conjuntos de problemas quinzenais foram liberados entre segunda e quarta e na sexta-feira da semana seguinte, e você poderia trabalhar neles com um parceiro. Para as palestras (pré-COVID), nós deveríamos ler “prep” no wiki do curso antes da aula, e passamos a aula principalmente fazendo exemplos e perguntas do iClicker para reforçar o conceito. As palestras após a entrada on-line ensinaram mais material durante a própria palestra. Em geral, uma aula bastante difícil, mas gratificante quando terminada.
Past Offerings
Hopcroft normalmente ensina isso no outono e Pass, na primavera. Kozen está ensinando isso no outono de 2013, no entanto. Michael George assumiu no outono de 2014. Anke van Zuylen estará ensinando isso no outono de 2020.