CS251: Grandes Ideias da Ciência da Computação Teórica

• O curso CS251 da CMU trata do estudo rigoroso da computação, um elemento fundamental do universo, da sociedade, das novas tecnologias e da nossa mente que busca compreendê-los.
• É importante ter a linguagem e as ferramentas adequadas para estudar a computação.
• Este curso explora resultados e questões centrais sobre a natureza da computação.

Formalização da computação

Módulo 1: Introdução

• O principal objetivo é explicar, em alto nível, o que é a ciência da computação teórica e estabelecer o contexto adequado para o que será abordado adiante.
• Começa com formas de representar dados formalmente e de definir formalmente o conceito de problema computacional.

Módulo 2: Autômatos finitos

• O objetivo é apresentar os autômatos finitos determinísticos (DFA), um modelo de computação simples e limitado.
• Os DFA são interessantes por si só e têm aplicações úteis, mas aqui são usados como um primeiro passo para definir formalmente o conceito de algoritmo.

Módulo 3: Formalização da computação

• O principal objetivo é apresentar a definição da máquina de Turing, o modelo matemático padrão para todo tipo de dispositivo computacional.
• O estudo rigoroso das máquinas de Turing oferece insights não apenas sobre o que um notebook pode fazer, mas também sobre o que o universo pode ou não pode fazer computacionalmente.

Módulo 4: Limites da computação

• Demonstra que a maioria dos problemas é indecidível e apresenta exemplos concretos de problemas indecidíveis.
• Utiliza duas técnicas centrais: diagonalização e redução.

Módulo 5: Limites do raciocínio humano

• Foi necessário formalizar matematicamente o raciocínio matemático, o que incluiu formalizar “algoritmo” ou “computação”.
• Usa a linguagem da ciência da computação teórica para responder de forma eficaz a questões importantes sobre os fundamentos da matemática.

Complexidade computacional

Módulo 6: Complexidade de tempo

• Muitos problemas são, de fato, decidíveis, mas se o algoritmo mais eficiente exigir um número muito grande de etapas computacionais, então o problema é praticamente indecidível.
• Estuda a complexidade computacional em relação a vários recursos, incluindo a complexidade de tempo, mas com foco especial nesta última.

Módulo 7: Teoria dos grafos

• Os grafos desempenham um papel muito fundamental na abstração de problemas computacionais que surgem na ciência da computação.
• É possível usar a vasta literatura sobre teoria dos grafos para compreender melhor a complexidade computacional dos problemas em grafos.

Módulo 8: P versus NP

• Apresenta a classe de complexidade NP e discute o problema P versus NP, o mais importante problema em aberto da ciência da computação.
• Se muitas linguagens naturais e amplamente estudadas pertencentes a NP puderem ser decididas em tempo polinomial, aplicações surpreendentes se tornarão possíveis.

Módulo 9: Algoritmos aleatórios

• A aleatoriedade é um conceito e uma ferramenta essenciais para modelar e analisar a natureza.
• Algoritmos aleatórios são algoritmos que podem acessar fontes de aleatoriedade, como geradores de números aleatórios, e podem cometer erros com probabilidade extremamente baixa.

Módulo 10: Criptografia

• Com a revolução da ciência da computação, o campo da criptografia começou a prosperar enormemente.
• O estudo da complexidade computacional revolucionou completamente a criptografia.

Destaques da ciência da computação teórica

Módulo 11: Tópicos adicionais

• Apresenta destaques selecionados da ciência da computação teórica.

Opinião do GN⁺

• Este curso oferece uma compreensão profunda dos aspectos teóricos da ciência da computação e dá aos estudantes a oportunidade de explorar a natureza da computação e aprender tópicos importantes como teoria da complexidade e criptografia.
• Em especial, a discussão de problemas em aberto como P versus NP oferece aos estudantes insights sobre as pesquisas que estão acontecendo na fronteira da ciência da computação.
• Este curso desempenha um papel importante na construção dos fundamentos da ciência da computação e oferece conhecimentos essenciais para se tornar um engenheiro de software com base teórica sólida.
• O módulo de criptografia destaca a importância da segurança de dados e da privacidade no mundo moderno, estabelecendo a base para se tornar um especialista nessa área.
• Este curso é muito valioso por ajudar estudantes que desejam construir uma carreira em ciência da computação a desenvolver a base teórica e as habilidades de resolução de problemas que são essenciais.

[quack337]

Ah... lembro de sofrer arrancando os cabelos na época da faculdade.
Provavelmente eu ainda não vou entender, mas mesmo assim vou tentar assistir com atenção.

[GN⁺]

Comentários do Hacker News

• Esta aula apresenta vários conceitos e se concentra especialmente em melhorar a capacidade de resolver problemas.

  • O método da aula dá aos alunos apenas definições básicas de um novo tópico a cada semana e exige que resolvam problemas que normalmente seriam vistos na terceira semana de um curso que trata desse tema de forma especializada.
  • Esse método é aplicado repetidamente e pode ser muito frustrante, mas isso é intencional.
  • Ao tentar sempre resolver problemas difíceis de alcançar, desenvolve-se estratégias melhores para pensar sobre o problema dado.

• Ciência da computação teórica pode ser divertida, mas às vezes também pode ser muito irritante.

• Vi um post no Reddit perguntando como resolver um problema de ciência da computação teórica, e depois descobriu-se que era uma tentativa de resolver de forma desonesta uma tarefa de COMS 331 (Theory of Computing) da Iowa State University.

  • Ninguém ajudou, e o autor apagou a postagem.
  • O problema parecia interessante, então tentei resolvê-lo como um desafio divertido de curta duração.
  • Eu era formado em matemática, mas cursei todas as disciplinas de graduação em ciência da computação teórica e, embora tenha esquecido muita coisa depois de cerca de 35 anos, achei que lembraria do básico, já que o problema vinha do primeiro conjunto de exercícios de COMS 331.
  • Passei alguns dias nisso sem fazer nenhum progresso e, desde então, já pensei no problema várias vezes por algumas horas ou até um dia inteiro, mas continuo fracassando.

• Se você quiser aprender essas ideias diretamente por meio da programação, recomendo "Understanding Computation From Simple Machines to Impossible Programs", de Tom Stuart.

• Uma versão mais completa desta aula pode ser vista em uma playlist no YouTube.

• Há outra versão desta aula que inclui o "método probabilístico", e não consigo imaginar uma prova sobre obstáculos em espaços topológicos de solução sem a forma moderna de pensar demonstrações existenciais (não construtivas).

• Se você se interessa por esse tema, pode conferir o site do Boaz Barak e o livro-texto disponível em PDF.

• As duas ideias mais importantes da ciência da computação teórica:

  1. Listas move-to-front podem levar até o dobro do tempo da busca ideal em lista ordenada, mas frequentemente são muito melhores do que uma ordenação estática da lista.
  2. Algoritmos aleatórios (como quicksort) muitas vezes levam o mesmo tempo que algoritmos não aleatórios mesmo no pior caso, mas na prática costumam ser muito mais rápidos do que variantes não aleatórias.

• Como seria uma versão desta aula em outras áreas?

  • Dá para imaginar uma disciplina de "grandes ideias" em física teórica, física experimental, economia etc.
  • Certa vez lecionei uma disciplina chamada "Invenções da Era da Informação", na qual discutíamos todas as invenções e ideias necessárias para que a civilização reproduzisse nossa era da informação, da escrita até a infraestrutura moderna de computação. Como não era um curso de uma única área, foi mais divertido.

• Lembro de uma aula sobre complexidade de tempo na universidade. O professor chamava alunos aleatoriamente e perguntava a complexidade de tempo de algoritmos complicados; se a resposta estivesse errada, ele chamava outro aluno.

• Como podemos entender a computação como uma propriedade fundamental do universo? Como plantas e animais realizam computação?