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: |
|
O último trabalho de Optimização Discreta consiste na elaboração de um texto de apoio sobre um tópico proposto pelo Professor. Este trabalho é obrigatório. O texto de apoio deverá ser preparado em LaTeX e deve ser também enviado por correio electrónico para jsoares@mat.uc.pt em attachment. No caso de pretender enviar mais do que um ficheiro deve primeiro comprimi-lo e enviar um único ficheiro.
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 (.ps,.pdf) 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.
Aqueles que quiserem inserir figuras em ficheiros .ps ou .eps devem usar o ficheiro preamble2.tex. Eis um exemplo de ficheiro .tex onde uma figura num ficheiro .eps é inserida. Para inserir figuras em outros formatos, como .jpg por exemplo, deve contactar o Professor.
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.
Neste semestre está a decorrer em simultâneo no Departamento de Matemática do Massachussets Institute of Technology uma disciplina de Tópicos de Optimização Combinatória que é uma espécie de Optimização Discreta II. A disciplina, cuja página-web está disponível aqui, é leccionada por Michel Goemans.
É prática corrente no MIT que no final de cada aula, um aluno(a) fique incumbido de preparar um resumo que será distribuído aos colegas após revisão pelo Professor. Conforme podem observar na página-web, esse procedimento tem vindo a ser utilizado naquela disciplina de Tópicos de Optimização Combinatória e os resumos têm vindo a ser disponibilizados online.
O último trabalho da nossa disciplina é obrigatório, deverá estar concluído no último dia de aulas e deverá ser preparado em grupos de um ou dois alunos. O trabalho consiste em usar um daqueles resumos (disponíveis abaixo) e reescrevê-lo usando as suas próprias palavras, procurando incorporar ilustrações tanto quanto possível.
Cada grupo deve enviar uma mensagem para jsoares@mat.uc.pt para se inscrever num tema. Assim que a sua inscrição seja aceite pelo Professor, pode começar a trabalhar imediatamente. Um trabalho excepcional poderá ser generosamente avaliado.
Irei acrescentando tópicos à medida que o semestre for decorrendo mas deve contactar o Professor se sentir dificuldades de qualquer ordem para a elaboração deste trabalho.
Depois de ter o seu tópico definido deve calendarizar pelo menos uma reunião com o Professor até à penúltima semana de aulas.
|
Tema |
Grupo |
Trabalho |
|
Non-bipartite matching: Tutte-Berge formula, Gallai-Edmonds decomposition, blossoms (.ps,.pdf) |
Tânia Viais |
(.pdf) |
|
Non-bipartite matching: Edmonds' cardinality algorithm and proofs of Tutte-Berge formulas and Gallai-Edmonds decomposition. (.ps,.pdf) |
João Pedro Gonçalves |
(.pdf) |
|
Cubic graphs and matchings, Factor-critical graphs, ear decompositions. (.ps,.pdf) |
Patrícia Bento de
Oliveira |
(.pdf) |
|
Posets and Dilworth theorem. Deduce Konig's theorem for bipartite matchings. Weighted posets and the chain and antichain polytopes. (.ps,.pdf) |
Inês Venâncio |
(.pdf) |
|
Partitioning digraphs by paths and covering them by cycles. Gallai-Milgram and Bessy-Thomasse theorems. Cyclic orderings. (.ps,.pdf) |
Ana Gouveia |
(.pdf) |
|
Proof of the Bessy-Thomasse result. The cyclic stable set polytope. (.ps,.pdf) |
Célia
Pereira |
(.pdf) |
| Bessy-Thomasse theorems (.ps) | ||
|
Marta Umbelino |
(.pdf) |
|
|
Matroids: representability, greedy algorithm, matroid polytope. (.ps,.pdf) |
Susana Ferreira |
(.pdf) |
|
Bárbara Baía |
(.pdf) |
|
|
Matroid intersection, matroid union, Shannon switching game. (.ps,.pdf) |
Pedro Reis |
(.pdf) |
|
Rita Figueirinha |
(.pdf) |
|
|
Interior relativo de um poliedro |
Paula Cristina Calisto |
12 |
|
Caminho mais curto |
Hugo Azevedo |
(.pdf) |
|
Pedro Francisco |
(.pdf) |
|
|
Caracterização de optimalidade para problemas de árvore de peso mínimo (.doc) |
Telmo Parreira |
(.pdf) |
|
Matroid union, packing and covering with spanning trees, strong basis exchange properties (.ps,.pdf) |
|
|
|
Matroid matching: examples, complexity, Lovasz's minmax relation for linear matroids (.ps,.pdf) |
|
|
|
Jump systems: definitions, examples, operations, optimization, and membership (.ps,.pdf) |
|
|
|
Jump systems: membership (.ps) |
|
|
|
Graph orientations, directed cuts (Lucchesi-Younger theorem), submodular flows (.ps,.pdf) |
Nuno Vaz Santos |
(.pdf) |
|
Submodular flows: examples, Edmonds-Giles theorem, reduction to matroid intersection in special cases (.ps,.pdf) |
|
|
|
Splitting off. $k$-connectivity orientations and augmentations (.ps) |
|
|
|
Proof of splitting-off. Submodular function minimization (.ps) |
|
|
|
Multiflow and disjoint path problems. Two-commodity flows (.ps) |
|
|
|
The Okamura-Seymour theorem and the Wagner-Weihe linear-time algorithm (.ps) |
|
|
última actualização em 3 de Junho de 2004
