AULA 4
2 MAR, QUI |
- Resumo da aula anterior.
- Trailer dos próximos episódios.
|
RECESSO
6 MAR, SEG |
CARNAVAL, não haverá aula.
|
AULA 5
9 MAR, QUI |
- Resumo da aula anterior.
- Trailer dos próximos episódios.
|
AULA 6
13 MAR, SEG |
- Resumo da aula anterior.
- Apresentação: pré-requisitos, programa, provas, ...
- O problema do par mais-próximo.
- Algoritmo Ingênuo (complexidade de tempo O(n2)).
- O problema do par mais-próximo na reta: algoritmo de complexidade de
tempo O(n log n).
- O problema do par mais-próximo na reta: algoritmo por
divisão-e-conquista de complexidade de
tempo O(n log n).
- Trailer dos próximos episódios.
|
AULA 7
16 MAR, QUI |
- Resumo da aula anterior.
- O problema do par mais-próximo no plano: algoritmo por
divisão-e-conquista de complexidade de
tempo O(n log n).
- Cota inferior para o problema do par mais-próximo.
- Trailer dos próximos episódios.
|
AULA 8
20 MAR, SEG |
- Resumo da aula anterior.
- O Problema da Galeria de Arte.
- Definições e conceitos: curva poligonal e polígono.
- Teorema da Galeria de Arte. Todo polígono com n vértices
pode ser coberto por chão(n/3) guardas.
- Diagonias de polígono, triangularizações e k-coloração de
grafos.
- Trailer dos próximos episódios.
|
AULA 9
23 MAR, QUI |
- Resumo da aula anterior.
- Teoria de Triangularização.
- Lema. Todo polígono possui um vértices convexo.
- Lema (Meister). Todo polígono com pelo menos 4 vértices possui
uma diagonal.
- Teorema. Todo polígono pode ser triangularizado através da
adição de diagonais (possivelmente zero).
- Lema (Meister). Todo polígono com pelo menos 4 vértices possui
duas orelhas.
- Teorema. Todo grafo associado a uma triangularização de um
polígono é 3-colorível.
- Trailer dos próximos episódios.
|
AULA 10
27 MAR, SEG |
- Resumo da aula anterior.
- Área de um triângulo: área sinalizada de um triângulo.
- Orientação de um triângulo.
- Área de polígonos convexos.
- Área de quadriláteros (warming-up para o teorema geral).
- Teorema da área de um polígono.
- Trailer dos próximos episódios.
|
AULA 11
30 MAR, QUI |
- Resumo da aula anterior.
- Intersecção de dois segmentos: alguns aspectos de implementação.
- Uso das primitivas LEFT, LEFTON,... para a decidir
se dois segmentos se intersectam.
- Algoritmo ingênuo para determinar todas as intersecção de um conjunto
dado de segmentos (complexidade de tempo O(n2)).
- Algoritmo por linha-de-varredura para determinar todas as intersecções
de um conjunto de segmentos .(complexidade de tempo O((n + i)log
n), onde i é o número de total de intersecções).
- Trailer dos próximos episódios.
|