Doutorado em Ciência da Computação - CAMPO GRANDE

Números inteiros: algoritmos fundamentais, fatoração, aritmética modular, equações diofantinas. Estruturas algébricas: grupos e subgrupos, grupos cíclicos, teorema de Lagrange, anéis e corpos, corpos finitos. Curvas elíticas.

Métodos de desenvolvimento de algoritmos de aproximação: arredondamento, métrico, primal-dual, probabilístico; métodos baseados em programação semidefinida. Algoritmos de aproximação para problemas de escalonamento, empacotamento unidimensional, satisfatibilidade, e para problemas de otimização em grafos (caixeiro viajante, coberturas, conectividade, cortes, etc). Classificação dos problemas com relação às suas propriedades de aproximabilidade: classes APX, PTAS, FPTAS. Reduções entre problemas. Alguns resultados sobre a não-aproximabilidade de certos problemas.

Arquitetura e modelos de computação paralela. Multiprocessadores e multicomputadores. Operações básicas. Algoritmos para problemas em grafos. Ordenação. Tópicos Avançados.

Problemas Algorítmicos e Correção e Eficiência de Algoritmos. Indução Finita e Solução de Recorrências. Algoritmos de Ordenação, Seleção e Mediana. Estrutura de Dados: Filas, Pilhas, Heaps, Hashing, Árvores de Busca. Divisão e Conquista, Programação Dinâmica e Método Guloso. Algoritmos em Grafos. Noções da teoria de complexidade: as classes P, Np, e CoNP e Algoritmos Aproximados. Tópicos Avançados.

Uma introdução avançada a arquitetura e organização de computadores. Tecnologias e perspectiva histórica. Medidas de desempenho. Conjunto de instruções. Unidades de aritmética e lógica. Projeto básico de um processador. Pipeline. Hierarquia da memória: cache e memória virtual. Dispositivos de I/O.

Arquitetura de SGBDs. SQL avançado. Transações, concorrência e recuperação Segurança e autorização. Otimização de consultas e tuning.

Arquiteturas. Distribuição. Banco de dados federado. Banco de dados paralelo. SGBDD. Processamento e otimização de consulta. Transações, concorrência e recuperação. Integração com DataWarehouse.

Máquinas de Turing e elementos de computabilidade. Máquinas de Turing determinísticas. A tese de Church-Turing. Problemas de decisão, busca e otimização. Indecidibilidade. Problemas de parada. Enumerabilidade recursiva. Tempo polinomial. A classe de complexidade P. Linear Speed-up Theorem. Reduções. Algoritmos polinomiais. Diagonalização. NP e NP-completude. Máquina de Turing não-determinística. A classe NP. NP-completude. O Teorema de Cook-Levin. Transformações polinomiais. Algoritmos pseudo-polinomiais. NP-completude forte. Máquinas de Turing com oráculos. Reduçao de Turing. Complexidade de Espaço.Classees determinísticas de complexidade de espaço. Linear Space Compression Theorem. PSPACE, NPSPACE, PSPACE-completude.

Introdução às principais técnicas para síntese de imagens por computador, a partir de modelos geométricos tridimensionais. Coordenadas homogêneas no plano e no espaço. Transformações euclidianas, afins e projetivas. Transformação de perspectiva. Janelamento; geometria projetiva orientada. Algoritmos geométricos para visibilidade. Algoritmos pontuais para visibilidade. Modelos de iluminação, cor e textura. Cálculo de sombras projetadas. Técnicas para modelagem de sólidos e superfícies. Traçado de raios.

Disciplina para aproveitamento de créditos por conclusão de curso de Mestrado.

Após a integralização curricular de disciplinas, o aluno deverá, com a anuência
de seu orientador, matricular-se semestralmente nesta disciplina. O mesmo procedimento deverá ser adotado pelo aluno que estiver desenvolvendo atividades relacionadas ao curso em outra IES no país ou no exterior

Software e Modelos de Processo de Engenharia de Software, Gerência de Projetos de Software, Planejamento de Projetos de Software, Garantia de Qualidade de Software, Métricas de Software, Princípios e conceitos fundamentais da Análise de Requisitos de Software, Métodos de Análise Estruturada, Métodos Orientados a Objetos, Métodos Alternativos de Análise, Princípios e conceitos fundamentais de Projeto de Software, Projeto de Interface com Usuário, Engenharia de Software Orientada a Objetos, Técnicas de Teste de Software, Estratégias de Teste de Software, Manutenção de Software, Métodos Formais, Engenharia de Software baseada em Componentes, Sistemas de Informação, Ferramentas CASE, Engenharia de Software Cliente/Servidor, Engenharia de Websites, Reengenharia e Gerenciamento de Configuração de Software.

Compreende atribuições relativas a encargos acadêmicos associados a atividades acadêmicas de Graduação, sob a supervisão de seu orientador, seguindo regulamentação específica das agências financiadoras e Regulamento do Curso.

Compreende atribuições relativas a encargos acadêmicos associados a atividades acadêmicas de Graduação, sob a supervisão de seu orientador, seguindo regulamentação específica das agências financiadoras e Regulamento do Curso.

Noções de complexidade. Árvores binárias de busca, árvores balanceadas, árvores AVL, árvores rubro-negras, árvores de difusão, árvore digital, árvores de sufixos, árvores auto-ajustáveis, árvores B. Tabelas de dispersão. Listas de prioridade, heaps. Estruturas para conjuntos disjuntos. Processamento de cadeias: busca de padrão e compactação de dados.

Estudo, sob supervisão do orientador e dos demais professores da área, de tópicos específicos para o desenvolvimento do projeto de pesquisa do aluno.

Projeto e análise de algoritmos para problemas em geometria computacional, incluindo problemas de envoltória convexa, caminho mínimo, busca geométrica, proximidade e intersecções geométricas. Questões de análise de complexidade, quotas inferiores e superiores, e modelos computacionais. Aplicações à computação gráfica, planejamento de movimento, casamento de padrões, etc.

Descrição formal de linguagens de programação. Análise léxica. Análise sintática. Blocos básicos e "traces". Geração de código: geração de código intermediário, seleção de instruções e alocação de registradores. Sistemas de execução: blocos, procedimentos, recursão. Recuperação de erros. Ferramentas para construção de analisadores léxicos, sintáticos e semânticos e para geração de geradores de código. Construção de um compilador para uma linguagem exemplo.

Sistemas de execução para linguagens concorrentes. Análise de fluxo de dados. Técnicas de otimização de código. Ferramentas para construção de geradores de código. Administração de memória. Geração de código para linguagens orientadas a objetos.

Fundamentos e História da IA. Representação do Conhecimento. Sistemas Especialistas. Ferramentas de IA. Aprendizagem. Tópicos Avançados. Perspectivas da IA.

Conceitos básicos de Biologia Molecular. Algoritmos para comparação de sequências biológicas. Busca em bases de dados. Montagem de fragmentos. Árvores filogenéticas.

Motivação: requisitos da segurança da informação. Métodos clássicos de ciframento. Criptoanálise elementar. Cifras de bloco versus cifras de fluxo. Técnicas para ciframento encadeado. Fundamentos matemáticos da criptografia moderna. Técnicas básicas para a geração de números pseudo-aleatórios. Algoritmos modernos de ciframento: simétricos ou de chave secreta; assimétricos ou de chave pública. Assinaturas digitais: algoritmos e protocolos para autenticação de usuários e não-repúdio de envio de mensagens. Funções de espalhamento (hashing) criptográficas: algoritmos mais conhecidos e seu uso em protocolos de autenticação de mensagens. Protocolos de suporte: certificação e gerenciamento de chaves. Técnicas para compartilhamento de informações secretas. Estudo de casos.

Formalismos para descrição de linguagens: Gramáticas e máquinas. Autômatos finitos e linguagens regulares. Autômatos a pilha e linguagens livres de contexto. Máquinas de Turing. Autômatos limitados linearmente e suas linguagens. Problemas indecidíveis.

O Raciocínio Dedutivo. Lógica, Conceitualização. Lógica Proposicional e o Sistema de Dedução Natural. Considerações sobre Correção e Completude. NP-Completude de Lógica proposicional. Lógica de Primeira Ordem e Sistema de Dedução Natural. Semântica para Linguagens de Primeira Ordem. Considerações sobre Correção e Completude para Linguagens de Primeira Ordem. Prova Formal de Correção de Programas. Prova Automática de Teoremas. Decidibilidade e Enumeração Recursiva. Noções sobre os teoremas da incompletude.

Programação Linear (PL): formulando problemas em PL, algoritmo Primal-Simplex, Dualidade em PL, o algoritmo-Dual Simplex e complexidade. Programação Linear Inteira (PLI): formulações e complexidade. Otimalidade: relaxações e limitantes. Problemas de PLI bem resolvidos. Algoritmos de Branch-and-Bound para PLI. Algoritmos de Planos-de-Corte para PLI. Desilgualdades Válidas Fortes: lifting, Combinatória Poliédrica, o problema da separação e a questão da complexidade otimização X separação. Relaxação Lagrangeana: método do subgradiente e heurísticas Lagrangeanas. Otimização de Grande Porte: método de geração de colunas.

Conceituação de processos concorrentes, modelos de sincronização e comunicação entre processos.Linguagens de programação concorrentes e técnicas de prova de correção de programas concorrentes. Conceituação de livelock, deadlock, escalonamento justo e quase justo.

Conceitos básicos de Álgebra Linear. Vetores e matrizes. Algoritmo de Gauss-Jordan. Algoritmo Simplex. Problema canônico primal. Problema canônico dual e dualidade: Lema da dualidade, folgas complementares, Teorema da dualidade. Formulação de problemas de programação linear. Aplicações em problemas de fluxos em redes: problema do caminho de custo mínimo, problema do fluxo máximo, problema do fluxo viável de custo mínimo. Algoritmo Dual-Simplex. Análise de sensibilidade. Decomposição de Dantzig-Wolfe. Algoritmos polinomiais para programação linear.

Conceitos básicos de concorrência. Taxonomia de arquiteturas paralelas: SISD, SIMD, MIMD e SPMD. Arquitetura de hardware para comunicação entre processadores: memória compartilhada, memória distribuída e hierarquia de memórias. Programação com variáveis compartilhadas: processos, sincronização e monitores. Programação distribuída: passagem de mensagens, RPC e paradigmas de interação entre processos. Definição dos passos para a criação de um programa paralelo. Ferramentas para programação paralela: bibliotecas MPI, OpenMP e Pthreads, compiladores paralelizadores e as linguagens Linda, Java e HPF. Análise de desempenho e depuração de programas paralelos. Exemplos de programas paralelos para aplicações específicas.

Introdução a redes de computadores e comunicação de dados. Terminologia, topologias, modelos de referência. Fundamentos de transmissão de dados, codificações analógica e digital. Protocolos e tecnologias de redes locais, metropolitanas, de longa distância e redes sem fio. Interconexão de redes. Arquitetura e protocolos TCP/IP.

Segurança e autenticação. Estudo de casos.

Conceitos fundamentais. Classificadores perceptrons-única chamada. Redes "feedforward" de múltiplas chamadas. Redes que se auto-organizam. Redes recorrentes. Aplicações.

Seminários de pesquisa sobre tópicos de Computação e Tecnologia.

Revisão de conceitos. Noções de Processos Estocásticos. Geração de variáveis aleatórias. Estudo de modelos. Modelagem de sistemas para simulação. Linguagens de simulação.

Multiprocessamento e multiprogramação. Gerenciamento de Processos. Gerenciamento de memória. Sistemas de Arquivo. Entrada e Saída. Estudos de casos. Noções de sistemas operacionais distribuídos.

Histórico. Distribuição em Sistemas Operacionais: O modelo cliente-servidor. O conceito de transparência: acesso, arquivos, processos. Protocolos. Chamadas de procedimentos remotas: taxonomia, implementação. Sistemas de arquivos distribuídos. Migração de Processos. Caching. Estudo de casos de sistemas relevantes.

Grafos e subgrafos. Árvores. Conexidade. Caminhos eulerianos. Circuitos hamiltonianos. Emparelhamentos. Coloração de arestas. Conjuntos independentes. Coloração de vértices. Grafos planares. Grafos orientados. Redes.

Disciplinas de conteúdo variável abordando assuntos de interesse dos orientadores e seus alunos, na área de Banco de Dados, de forma flexível, conforme as necessidades.

Disciplina de conteúdo variável abordando assuntos de interesse dos orientadores e seus alunos, na área de Computação gráfica, de forma flexível, conforme as necessidades.

Disciplinas de conteúdo variável abordando assuntos de interesse dos orientadores e seus alunos, na área de Sistemas de Informação, de forma flexível, conforme as necessidades.

Disciplinas de conteúdo variável abordando assuntos de interesse dos orientadores e seus alunos, na área de Sistemas de Computação, de forma flexível, conforme as necessidades.

Disciplinas de conteúdo variável abordando assuntos de interesse dos orientadores e seus alunos, na área de Sistemas de Informação, de forma flexível, conforme as necessidades.

Disciplinas de conteúdo variável abordando assuntos de interesse dos orientadores e seus alunos, na área de Teoria da Computação, de forma flexível, conforme as necessidades.

Os Tópicos Especiais poderão ser ofertados na forma de disciplinas esporádicas, sem alterar a estrutura curricular do curso, ou utilizados para integralizar o currículo do aluno por convalidação de créditos conforme Norma vigente da Pós-Graduação stricto sensu da UFMS.

Os Tópicos Especiais poderão ser ofertados na forma de disciplinas esporádicas, sem alterar a estrutura curricular do curso, ou utilizados para integralizar o currículo do aluno por convalidação de créditos conforme Norma vigente da Pós-Graduação stricto sensu da UFMS.

Os Tópicos Especiais poderão ser ofertados na forma de disciplinas esporádicas, sem alterar a estrutura curricular do curso, ou utilizados para integralizar o currículo do aluno por convalidação de créditos conforme Norma vigente da Pós-Graduação stricto sensu da UFMS.