MAC0102 CAMINHOS NO BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO * Hoje: Yoshiharu Kohayakawa, MAC/IME/USP http://www.ime.usp.br/~yoshi/ ** Minhas áreas de interesse - Combinatória e teoria dos grafos; aspectos teóricos da computação * Hoje: Trilha de Teoria da Computação: módulo Matemática Discreta ** Trilha de Teoria da Computação Para receber um certificado o aluno deve cursar as obrigatórias de pelo menos 2 módulos (4 ou 5 disciplinas); e pelo menos 7 disciplinas da trilha. *** Módulos **** Matemática Discreta ***** Obrigatórias - MAT0206 Análise Real - MAT0264 Anéis e corpos [MAT0213 Álgebra II] - MAC0320 Introdução à Teoria dos Grafos ***** Demais - MAT0311 Cálculo Diferencial e Integral V - MAT0225 Funções Analíticas - MAT0313 Álgebra III - MAT0234 Medida e Integração - MAE0221 Probabilidade I - MAE0224 Probabilidade II - MAE0228 Noções de Probabilidade e Processos Estocásticos - MAE0326 Aplicações de Processos Estocásticos - MAC0414 Autômatos, Computabilidade e Complexidade - MAC0436 Tópicos de Matemática Discreta **** Algoritmos ***** Obrigatórias - MAC0328 Algoritmos em Grafos - MAC0414 Autômatos, Computabilidade e Complexidade ***** Demais - MAC0325 Otimização Combinatória - MAC0327 Desafios de Programação - MAC0331 Geometria Computacional - MAC0450 Algoritmos de Aproximação - MAC0336 Criptografia para Segurança de Dados - MAC0465 Biologia Computacional - MAC0466 Teoria dos Jogos Algorítmica **** Otimização ***** Obrigatórias - MAC0315 Programação Linear - MAC0325 Otimização Combinatória ***** Demais - MAC0300 Métodos Numéricos da Álgebra Linear - MAC0418 Tópicos Especiais de Programação Matemática - MAC0419 Métodos de Otimização em Finanças - MAC0427 Programação Não-linear - MAC0452 Tópicos de Otimização Combinatória - MAC0450 Algoritmos de Aproximação - MAC0452 Tópicos de Otimização Combinatória - MAC0461 Introdução ao Escalonamento e Aplicações - MAC0??? Programação Inteira (a ser criada) *** Ementas das obrigatórias **** MAT0206 Análise Real ***** Objetivos Introduzir conceitos básicos da análise real, visando tornar os estudantes familiarizados com a linguagem formal e técnicas de demonstração em matemática. ***** Informações detalhadas - Créditos Aula: 6 - Carga Horária Total: 90h - Programa 1. Números reais: introdução axiomática. Sequências numéricas. Limites superior e inferior. Sequências de Cauchy. Sequências limitadas e monótonas limitadas. Intervalos encaixantes. 2. Continuidade: teoremas do anulamento, do máximo e do mínimo, preservação da conexidade. Continuidade por sequências. Continuidade uniforme. 3. Derivabilidade: diferencial e teorema do valor médio. 4. Integral de Riemann: definição e exemplos especiais. Integrabilidade de funções contínuas e teorema fundamental do Cálculo. Critérios de integrabilidade. 5. Séries numéricas: critérios de convergência. 6. Sequências e séries de funções convergência pontual e uniforme, teste-M de Weierstrass. Continuidade, integrabilidade e derivabilidade com convergência uniforme. 7. Séries de potências e propriedades. **** MAT0264 Anéis e Corpos [Álgebra II] ***** Objetivos Introdução às noções básicas de estruturas algébricas: anéis e corpos. ***** Informações detalhadas - Créditos Aula: 4 - Carga Horária Total: 60h - Programa 1. Anéis, homomorfismos, ideais, anel quociente, domínios de integridade, corpos de frações. 2. Anéis fatoriais, domínios de ideais principais, domínios euclidianos. 3. Anéis de polinômios. 4. Extensões de corpos. 5. Construções com régua e compasso. **** MAC0320 Introdução à Teoria dos Grafos ***** Objetivos A teoria dos grafos é usada na modelagem de muitos problemas computacionais. Esta disciplina tem o objetivo de introduzir o aluno à linguagem e aos problemas básicos da teoria. A disciplina complementa MAC0328 Algoritmos em Grafos, que trata dos aspectos mais algorítmicos da teoria. ***** Informações detalhadas - Créditos Aula: 4 - Carga Horária Total: 60h - Programa (em evolução) 1. Grafos. Isomorfismo 2. Caminhos e circuitos. Subgrafos. Cortes e pontes 3. Árvores 4. Grafos eulerianos 5. Grafos hamiltonianos 6. Emparelhamentos em grafos bipartidos 7. Conexidade e Teorema de Menger 8. Conjuntos estáveis e cliques 9. Coloração de arestas 10. Coloração de vértices 11. Noções de planaridade * Resultados estruturais x resultados algorítmicos ** Emparelhamentos perfeitos em grafos bipartidos *** [[file:bip_match.pdf][O problema através de um exemplo]] *** Boa caracterização de grafos bipartidos com emparelhamentos perfeitos (É um problema em NP e também em coNP) ** Historicamente Algoritmos eficientes (polinomiais) são em geral descobertos quando há boa caracterização *** [[file:Rado.jpg][Prova da boa caracterização]] ** Conclusão - Vale a pena entender problemas computacionais de forma estrutural * Análise, álgebra, probabilidade, processos estocásticos...? * Matemática e ciência da computação ** [[file:Concrete.jpg][Matemática concreta]] - A foundation for computer science R. L. Graham, D. E. Knuth e O. Patashnik "But what exactly is Concrete Mathematics? It is a blend of CONtinuous and disCRETE mathematics." + Uma [[file:PNT.jpg][fórmula]] do Matemática concreta (Cap. 9, Asymptotics) + Um [[file:prime_n.jpg][parágrafo]] do Matemática concreta ** Um artigo de Knuth D. E. Knuth http://www-cs-faculty.stanford.edu/~uno/ + Algorithmic thinking and mathematical thinking D. E. Knuth, American Mathematical Monthly, 1985 - For many years I have been convinced that computer science is primarily the study of algorithms. - I tend to think of algorithms as encompassing the whole range of concepts dealing with well-defined processes, including the structure of data that is being acted upon as well as the structure of the sequence of operations being performed. ** Nome da área - Ciência da Computação / Informática / Cibernética / Matemática aplicada ** Escolha de Knuth seria - Algorithmics (J. F. Traub, 1964) ** Características comuns entre computação e matemática - Natureza abstrata, com várias camadas de abstração - Precisão e rigor - Relações quantitativas - Ampla gama de aplicações *** Na verdade Escrito em 1956 sobre matemática por A. D. Aleksandrov + A. D. Aleksandrov, A. N. Kolmogorov e M. A. Lavrent'ev, eds, Mathematics: it's contents, methods, and meaning 1, 1956 (trad. 1963) ** Raciocínio algorítmico - 2% na população * Você poderia ser um pouco mais concreto? ** Ou fazer mais sentido? ** O que dizem sobre cientistas da computação teóricos - "Theoretical computer scientists are said to be mathematicians in a hurry." + Bernard Chazelle, [[file:Chazelle.jpg][The discrepancy method]]---randomness and complexity, 2000 - Teoria da discrepância + Quão "uniformemente" pode ser distribuído um conjunto finito de pontos em um dado "ambiente"? ** Parte de uma resenha do livro de Chazelle *** There is an extensive discussion of the problem of placing points as uniformly as possible on the unit-radius sphere in three dimensions. *** To quote the author, "if you ever harbored any doubt about the unity of mathematics, this is required reading. You will witness all branches of mathematics coming together in spectacular fashion." *** A digression into modular forms follows, touching upon their role in the proof of Fermat's Last Theorem by Wiles. *** Lower bound techniques form the focus of Chapter 3. These are often approached via the L^2 norm of the discrepancy function. Various analytic techniques are presented, including Haar wavelets [and] Fourier transforms [...]. *** Computação? The final chapter includes a proof that the minimum spanning tree of a connected graph with n vertices and m edges can be computed deterministically in O(m α(m,n)) time, where α is the classical inverse of Ackermann's function. * E com matemática mais elementar...? ** Álgebra linear ** Álgebra de polinômios; corpos ** Probabilidade/processos estocásticos ** Combinatória "pura" ** Exemplos *** PageRank + Distribuição estacionária de uma certa cadeia de Markov = autovalor principal de uma certa matriz estocástica + PageRank e futebol http://www.bbc.co.uk/programmes/p032rf5d *** Teoria de códigos + Uso essencial de corpos finitos * Conclusão - Teoria da computação e matemática discreta são inseparáveis * PS - Instituto de estudo avançado, Princeton + Avi Wigderson + http://www.math.ias.edu/csdm * Grade curricular 2016 http://bcc.ime.usp.br/curriculo2016/index.html