Diário de aula

Aqui você encontrará o que foi dado em cada aula e talvez os planos de aulas futuras.

25.02

Preliminares de álgebra linear.

27.02

Fim das preliminares. Programação cônica e exemplos.

04.03

Carnaval.

06.03

Carnaval.

11.03

Alguns exemplos de programação semidefinida: otimização de autovalores e Teorema de Fan, MAXCUT e relaxações, conjuntos independentes e número teta de Lovász (exemplos: códigos binários, número de contato, i.e., kissing number).

13.03

Otimização polinomial. Como resolver problemas de programação semidefinida no computador (usando SAGE). Veja slides.

18.03

Dualidade em programação cônica: relaxação de Lagrange, dualidade fraca, Lema de Farkas, teorema da separação, dualidade forte.

20.03

Exemplos de dualidade em programação semidefinida. Método dos elipsóides; veja notas de aula.

25.03

Conseqüências do método dos elipsóides para programação cônica, resolução de exercícios.

27.03

Não haverá aula!

01.04

A desigualdade de Grothendieck e aplicações: n-vector model, XOR games, MAXCUT.

03.04

Limitantes para a constante de Grothendieck para matrizes laplacianas e positivas semidefinidas: algoritmos de Goemans e Williamson e Nesterov.

08.04

Limitantes para a constante de Grothendieck para matrizes quaisquer: limitante de Grothendieck e limitante de Krivine com interpretação algorítmica. Limitantes para constantes para posto superior a 1.

10.04

Número de independência e número cromático de grafos. Limitantes para o número de independêndia; número teta de Lovász e suas propriedades básicas. Grafos perfeitos e uma aplicação: algoritmo polinomial para o cálculo do número de independência e do número cromático de grafos perfeitos.

15.04

Semana Santa, não haverá aula.

17.04

Semana Santa, não haverá aula.

22.04

Solução de exercícios. Traga suas dúvidas!

24.04

Algumas propriedades do número teta e uma aplicação: encontrar limitantes para códigos binários.

29.04

Uso do teta para cálculo de limitantes para a capacidade de Shannon de um grafo. Exploração de simetria em programação semidefinida (veja a nota sobre simetria).

06.05

Continuação do estudo de simetrias. Teorema de Wedderburn e Artin, diagonalização de álgebras matriciais comutativas, representação regular.

08.05

Hierarquias para programação semidefinida: hierarquia de Lassere para o número teta e fatos relacionados; operador \(N_+\) com prova de convergência.

13.05

Extensões do número teta para grafos infinitos sobre a esfera. Noções de análise funcional: kernels e suas propriedades.

15.05

Número teta de Lovász para códigos esféricos. Teorema de Schoenberg para simplificação baseada em simetria. Limitante de Delsarte, Goethals e Seidel para códigos esféricos; aplicação ao número de contato.

20.05

Número teta para conjuntos que evitam uma distância na esfera. Aplicação ao problema do número cromático mensurável do espaço euclidiano.

22.05

Greve de ônibus; não houve aula.

27.05

Discussão do exercício do MAXCUT. Começo de uma prova do teorema de Schoenberg.

29.05

Finalização da prova do teorema de Schoenberg.

03.06

Aula de dúvidas antes da prova.

05.06

Prova!

10.06

Solução da prova.