Optimização Discreta Licenciatura
em Matemática
|
|
Optimização Discreta Licenciatura
em Matemática
|
|
Docente:
| João Soares | Email:jsoares@mat.uc.pt |
| Gabinete 6.4 do Dep. Matemática | Tel. 239 791 154 |
| Horário de
Atendimento: Segundas das 14.30 às 15.30 (Gabinete 6.4@DM) |
O último trabalho de Optimização Discreta consiste na apresentação oral de um teorema e respectiva demonstração a uma plateia de colegas e professor. A apresentação deverá ser acompanhada de um texto de apoio a ser distribuído no dia da apresentação.
O resultado a apresentar será escolhido pelo próprio aluno no leque de artigos, extractos de livros, etc. descriminados na tabela abaixo que vai sendo ampliada à medida que o semestre for decorrendo.
A escolha tornou-se definitiva no dia 2 de Maio. Até esta data o aluno podia trocar de tema sempre que a sua nova escolha estivesse disponível. Deve calendarizar pelo menos uma reunião com o Professor até à penúltima semana de Maio.
O texto de apoio deverá ser preparado em Word ou LaTeX e deve ser também enviado por correio electrónico para jsoares@mat.uc.pt em attachment. O LaTeX é um compilador para processamento de texto vocacionado para a escrita de texto matemático. É também muito recomendado para a escrita de relatórios ou dissertações, matemáticas ou não. Para produzir um texto em LaTeX necessita de um processador de texto ascii como o Emacs ou WinEdit onde o ficheiro .tex contendo as instruções é inserido.
Eis um exemplo de um ficheiro .tex. A compilação desse ficheiro produz um ficheiro .dvi ou .pdf ou .ps. O documento preparado por Michel Goemans do MIT descreve um conjunto de instruções elementares que te podem ajudar a escrever em LaTeX. O documento refere-se a um ficheiro preamble.tex que deve estar presente na directoria onde compilares o teu ficheiro .tex.
O Professor Pedro Quaresma do Departamento de Matemática mantém uma página web dedicada ao LaTeX e é autor do livro Introdução ao LaTeX editado pela Escolar Editora. Sugiro que levem o software WinEdit e pratiquem durante as férias.
| Tema | Aluno |
| Comparar diferentes formulações
para o Problema do Caixeiro Viajante Simétrico Bibliografia: Gábor Pataki , Teaching Integer Programming Formulations Using the Traveling Salesman Problem, SIAM Review, volume 45, número 1, pp. 116-123, 2003. Comentário: Saber comparar formulações é essencial para quem pretende resolver problemas práticos. |
Paulo Gonçalves |
| Formulações de OD para o problema
do Jogo da Vida de Conway Bibliografia: Robert A. Bosch, Integer Programming and Conway's Game of Life, SIAM Review, volume 41, número 3, pp. 594-604, 1999. Comentário: Este trabalho mostra como é possível construir modelos de OD para problemas de Teoria de Jogos. |
Marta Umbelino |
| Diagramas de Gantt e um algoritmo
de Lawler para Calendarização de tarefas Bibliografia: Michel X. Goemans, David P. Williamson, Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler, SIAM J. Discrete Math., volume 13, número 3, pp. 281-294, 2000. Comentário: Este artigo (muito bem escrito) apresenta um algoritmo para resolver o problema de sequenciamento de tarefas, que estudámos na aula, quando existem relações de precedência entre as tarefas. |
Joana Fialho |
| Matrizes Equilibradas Bibliografia: Definição e propriedades nas páginas 303-308 do livro de Schrijver'86. Comentário: Uma classe de matrizes relacionada com a Unimodularidade Total e com aplicações em Teoria de Grafos. |
Paula Santos |
| Bases de Hilbert e Sistemas de
Representação TDI Bibliografia: Definição e propriedades nas páginas 232-233 e 315-317 do livro de Schrijver'86. Comentário: Todo o poliedro inteiro admite um sistema de representação algébrico TDI. Demonstração deste resultado enunciado na aula. |
Inês Venancio |
| Fluxo Multi-mercadoria,
Corte Máximo e Carteiro Chinês em grafos planares Bibliografia: Barahona, Francisco Planar multicommodity flows, max cut, and the Chinese postman problem. Polyhedral combinatorics (Morristown, NJ, 1989), 189--202, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 1, Amer. Math. Soc., Providence, RI, 1990. Comentário: Estes três problemas estão relacionados quando o grafo subjacente é planar. |
Nuno Alves |
| Implementação em matlab
de método para resolver sistemas de equações Diofantinas Bibliografia: Algoritmo descrito nas páginas 56-59 do livro de Schrijver'86 e Texto de Apoio Comentário: O método funciona de modo semelhante à Eliminação de Gauss. Este trabalho envolve uma implementação em matlab. |
Bárbara Baía |
| Modelar a elaboração de
horários escolares Bibliografia: A. S. Asratian e D. de Werrab, A generalized class–teacher model for some timetabling problems, European journal of operational research, Volume 143, Número 3, 16 Dezembro 2002, pp 531-542. Comentário: A definição de horários de aulas de forma a compatibilizar professores e alunos pode ser modelada como um problema de Optimização Combinatória. O modelo mais simples é também um problema de coloração de grafos. |
|
| Aproximação Diofantina
(Quanto é |22/7-pi|?) Bibliografia: Algoritmo descrito nas páginas 60-67 do livro de Schrijver'86 e Texto de Apoio. Comentário: Em breve estudaremos nas aulas um método para aproximar um número real positivo por um número racional de baixo denominador (o método das fracções contínuas). Neste trabalho o aluno deve demonstrar alguns resultados teóricos não abordados no Texto de Apoio e apresentar alguns resultados numéricos com uma implementação de domínio público. |
|
| Encontrar um vector de
norma reduzida num reticulado Bibliografia: Algoritmo descrito nas páginas 67-72 do livro de Schrijver'86 Comentário: Um reticulado é, grosso modo, o conjunto de soluções de um sistema de equações lineares Diofantinas (isto é, as soluções são vectores de números inteiros). Este algoritmo visa obter o ponto deste conjunto que está mais próximo da origem. |
|
| Uma prova elementar do Lema de
Farkas Bibliografia: Achiya Dax, An Elementary Proof of Farkas' Lemma, SIAM Review, volume 39, número 3, pp. 503-507, 1997. Comentário: Trabalho teórico muito interessante. |
última actualização em 14 de Maio de 2003
