MC558 - Projeto e Análise
de
Algoritmos II - 2021
Prof. Flávio Keidi Miyazawa
Informações sobre a
disciplina
Docente da Disciplina
Plano de desenvolvimento da disciplina: Avaliação, atendimentos, bibliografia, etc.
Notas das provas e laboratórios
Avisos:
Link do Google Meet para as aulas foi divulgado no Classroom.
Os avisos do curso serão disponibilizados pelo Classroom.
Docente: Flávio Keidi
Miyazawa Sala: IC-30
Grafos: Definição e representação de
grafos e de digrafos; Isomorfismos; Vizinhanças, cortes e graus;
Caminhos e ciclos; Subgrafos; Grafos conexos e componentes conexas;
Conjuntos independentes, cliques e coberturas; Colorações de vértices;
Emparelhamentos; Colorações de arestas. Algoritmos em Grafos: Representação
por lista de adjacência e matriz de adjacência; busca em profundidade;
busca em largura; ordenação topológica; componentes fortemente
conexos; árvore geradora mínima: algoritmos gulosos de Prim e Kruskal
(uso do "union-find" e análise amortizada); caminhos mínimos com uma
única fonte: algoritmos de Dijkstra, Bellman-Ford e DAG; caminhos
mínimos entre todos os pares de vértices: algoritmos da multiplicação
de matrizes e Floyd-Warshall.
Reduções entre problemas: Para
obtenção de cotas superiores; para obtenção de cotas inferiores;
reduções entre problemas envolvendo grafos.
Programação Linear: Formulação de problemas como PLs.
Classes de Problemas: A hierarquia de
Complexidade. As classes P, NP, NP-completo e NP-difícil; Noção de
completude e o Teorema de Cook; Problemas e reduções fundamentais em
NP-completude; Outras classes de problemas: co-NP, PSPACE, problemas
indecidíveis (Problema da Parada).
Material usado nas aulas teóricas (textos, transparências, códigos,...):
Aulas e Atendimento:
As aulas serão nas segundas-feiras e quartas-feiras e terão início às 14:00.
A disciplina contará com o apoio de
um PED, Hismael Costa ([nome].[sobrenome]@gmail.com,
trocando [nome] e [sobrenome] pelos termos
adequados), e seu horário de atendimentor será nas segundas-feiras,
às 18hs. Para utilizar o atendimento do PED, os alunos interessados
deverão enviar email para o PED com um dia de antecedência,
confirmando o atendimento. O atendimento começará no início do
horário estabelecido para o atendimento; não havendo outros alunos
a serem atendidos, o horário de atendimento daquele dia será
encerrado.
As aulas serão ministradas nos dias
e horários estipulados para a disciplina e suas gravações serão
disponibilizadas através da plataforma Google Classroom. Avisos serão
enviados na plataforma do Google Classroom. A primeira aula da
disciplina será no dia 09/Agosto/2021. O atendimento do professor será
nas quartas-feiras logo após as aulas teóricas. Não havendo outros
alunos a serem atendidos, o horário de atendimento daquele dia será
encerrado.
Datas Importantes
3 Projetos de Implementação: Prazo de pelo menos uma semana após a divulgação de cada projeto.
Teste 1: 13/Setembro/2021.
Teste 2: 13/Outubro/2021.
Teste 3: 06/Dezembro/2021.
Exame: 15/Dezembro/2021.
Listas
de Exercícios
Faça exercícios do livro Introduction to Algorithms: A Creative Approach. U. Manber.
Faça exercícios do livro Introduction to Algorithms. T.H. Cormen, C.L. Leiserson, R.L. Rivest, C. Stein.
Bibliografia
Sobre técnicas de
demonstração e outros aspectos de matemática discreta
Daniel J. Velleman . How to Prove it: A structured
approach, Second edition, 2012. G. Polya . How to Solve it: A
New Aspect of Mathematical Method, Second Edition, 1973. E. Lehman, F.T. Leighton,
A. R. Meyer . Mathematics
for Computer Science, 2012. A. Gomide, J. Stolfi. Elementos
de Matemática Discreta para Computação, 2014.. K. H. Rosen. Discrete Mathematics and its Applications. S. Seiden.Theoretical Computer
Science Cheat Sheet by Steve Seiden A good book to learn probability
Dimitri P. Bertsekas and John N. Tsitsiklis.
Introduction to Probability,
2nd Edition, 2008. G. Brassard, P. Bratley, Fundamentals of Algorithmics,
Prentice Hall, 1995.
T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to
Algorithms, MIT Press, Third Edition, 2009.
S. Dasgupta, C. H. Papadimitriou, and
U. V. Vazirani. Algorithms 1ed.. 2006. McGraw-Hill Education.
J. Erickson, Models of Computations - Lecture Notes, 2015,.
J. Kleinberg, E. Tardos, Algorithm Design, ADDISON
WESLEY, 2005.
C. E. Ferreira, Y. Wakabayashi, Combinatória Poliédrica e Planos-de-Corte Faciais., livro para a X Escola de Computação, UNICAMP, julho de 1996.
U. Manber, Algorithms: A Creative Approach,
Addison-Wesley, 1989.
F.K. Miyazawa, Programação
Inteira, XI Escola Regional de Informática SBC -
Paraná, pp. 49-90, Setembro, 2003. Transparências.
F.K. Miyazawa e C.C. de Souza, Introdução à Otimização Combinatória,
Jornadas de Atualização em Informática - Congresso da Sociedade
Brasileira de Computação - JAI-SBC, 2015.
I. Parberry
http://www.eng.unt.edu/ian/books/free/. Problems on Algorithms.
C. H. Papadimitriou, K. Steiglitz Combinatorial Optimization:
Algorithms and Complexity, Dover, 1982.
M. Bazaraa, J. Jarvis, H. Sherali. Linear Programming and Network Flows (4a. edição), Wiley (2009).
L. A. Wolsey. Integer Programming, Wiley (1998).
R. Sedgewick, K. Wayne Algorithms, 4th ed, Addison-Wesley (2011).
V. Vazirani. Approximation Algorithms. 2001. Springer-Verlag.
D.P. Williamson and D.B. Shmoys. The Design of Approximation
Algorithms. Cambridge University Press, 2011.
J. L. Szwarcfiter, Grafos e Algoritmos Computacionais, 1984.
N. Ziviani, Projeto de Algoritmos, Thompson, segunda
edição, 2004.