Análise de Algoritmos

1884 palavras 8 páginas
Exibir mais
Trabalho Prático

Análise de Algoritmos II

Introdução
Neste trabalho você deverá modelar alguns problemas usando Programação Linear Inteira (PLI) e resolvê-los utilizando o Xpress, um dos melhores resolvedores comerciais de programação matemática disponíveis no mercado atualmente. Para poder ter acesso à uma versão estudantil do software, compatível apenas com sistema operacional Windows, siga os seguintes passos:
• Acesse o site www.dashoptimization.com, entre no menu Users e escolha Academics e então Free Student Edition.
• Siga as instruções para baixar e instalar esta versão gratuita do resolvedor de programação linear na sua máquina.
• Leia o manual Xpress-MP Essentials dando atenção especial para os capítulos Xpress-IVE, Modeling with Xpress-MP e Further Mosel Topics.
• O manual citado no item acima mais os exemplos do item seguinte devem ser suficientes para você conseguir fazer o trabalho. Contudo, considere a possibilidade de ler também algumas partes do manual Xpress-Mosel User's Guide.
• Execute os exemplos com modelos PLI para os problemas do "Conjunto Independente Máximo" (IS), da "Cobertura por Vétices Mínima" (CV), da "Clique Máxima" e da "Colocaração Mínima" usando como entrada os arquivos de testes (XX.dat) localizados neste mesmo diretório. Veja com cuidado os códigos destes exemplos. Note que para executar uma instância cujos dados estão num arquivo "exemplo.dat", você deve passar este mesmo nome como resposta da pergunta feita pelo programa. Este mecanismo de entrada do nome do arquivo contendo os dados da instância a ser resolvida deverá ser implementado nos programas feitos neste trabalho.
Dica: Antes de tentar implementar os problemas do trabalho, escreva em Mosel as formulações para alguns problemas conhecidos, como, por exemplo, o "Conjunto Dominante Mínimo" (DS), o "Problema do Caixeiro Viajante" (TSP) e o "Problema da Partição" (PAR).
O trabalho deverá ser feito individualmente ou em duplas. Caso seja feito

Relacionados

  • analise algoritmo
    3043 palavras | 13 páginas

    Análise e Complexidade de Algoritmos Análise e Complexidade de Algoritmos Problemas do nosso interesse Análise e Complexidade de Algoritmos Problemas do nosso interesse • Problemas que não admitem solução computacional não são de interesse deste curso Análise e Complexidade de Algoritmos Problemas do nosso interesse • Problemas que não admitem solução computacional não são de interesse deste curso Loana Tito Nogueira Análise e Complexidade de Algoritmos Problemas….

    exibir mais
  • Analise de Algoritmo
    845 palavras | 4 páginas

    Complexidade de Algoritmos Análise de Algoritmos Professor Renan Levenhagen Bustamante Neves Júlio Cezar Ferreira Rocha Varginha 2013 1 - Complexidade de Algoritmos Diferentes computadores, muitas vezes com hardware idênticos, podem levar tempos diferentes para processar um mesmo algoritmo. Quando trocamos algum, ou mais, itens de hardware, esta diferença tende a aumentar ainda mais, por tanto, avaliar o desempenho de um algoritmo com base apenas….

    exibir mais
  • Análise de algoritmo
    287 palavras | 2 páginas

    Universidade Estadual Do Sudoeste Da Bahia - Uesb Departamento de Ciências Exatas – DCE Curso: Ciência da Computação Disciplina: Análise de Algoritmos Professora: Aline Silva Costa ALUNOS: _____________________________________________ Data: _____/_____/____ Atividade de Avaliação – Unidade II - Valor: 3,0 Dada a implementação dos seguintes algoritmos em C++ e Java (escolher uma das duas linguagens) a. Bubblesort b. InsertionSort c. SelectSort….

    exibir mais
  • Análise de algoritmos
    857 palavras | 4 páginas

    Instituto Superior de Ensino e Pesquisa de Ituiutaba FEIT – Fundação Educacional de Ituiutaba UEMG – Universidade do Estado de Minas Gerais ROBERTO GUIMARÃES DUTRA DE OLIVEIRA TRABALHO ANÁLISE DE ALGORITMOS ITUIUTABA – MG MARÇO 2010 OBS: Código Fonte foi desenvolvido junto com o aluno Cássio Borges Matsumoto A) Colocar um contador após o enquanto e dentro do teste (se). Ao final de cada….

    exibir mais
  • Analise de algoritmo
    1276 palavras | 6 páginas

    FACULDADE ANHANGUERA DE CAMPINAS - UNIDADE III CIÊNCIA DA COMPUTAÇÃO ANÁLISE E COMPLEXIDADE DE ALGORITMOS ATPS - Atividades Práticas Supervisionadas (Etapas 1 e 2) Prof. Carlos Papotti Clodoaldo dos Santos Carrero 1053002128 7ª Série Márcia Maria Santos do Rosário 1011780117 Maycon Jéfferson Mascelloni 1001793128 Robson Buzois Marciotto 1033941409 William dos Santos Gomes 7866744 Campinas (SP), 09 de abril de 2013 RELATÓRIO 1 (Etapa 1) Definição das medidas….

    exibir mais
  • Analise de algoritmos
    1892 palavras | 8 páginas

    Analise de Algoritmos II Professor: Leandro S. Marques Eduardo Moreira Pinto nº03 Rgm:074984 Salto 2012 Implementação do Código em C++ #include <stdio.h> #include <time.h> #define Max 500000 #define num_bucket 10 #define tam_bucket 10 void….

    exibir mais
  • Análise de Algoritmos
    291 palavras | 2 páginas

    Exercício 1. Encontre a solução fechada para a sequência T definida por: T(1) = 7 T(n) = 2T(n-1)+1, onde n ≥ 2 Resposta: primeiro tem que expandir: K = 1 : T(n) = 2T(n-1) + 1 K = 2 : T(n) = 2[2T(n - 2) + 1]+1 = 4T(n - 2) + 3 K = 3 : T(n) = 4[2T(n - 3) + 1]+3 = 8T(n - 3) + 7 Segundo: conjecturar, após a expansão, T(n) = 2^nT(n - k) + 2^n – 1 a expansão irá parar quando k = n – 1. T(n) = 2^(n-1)T(n – (n - 1)) + 2^(n-1)-1 T(n) = 2^(n-1)*7+ 2^(n-1)-1=8* 2^(n-1)-1 T(n) = 2^(3 )* 2^(n-1)-1=….

    exibir mais
  • análise de algoritmos
    325 palavras | 2 páginas

    RESUMO AA1 Programação Dinâmica – 4 PASSOS: 1 - Caracterizar a estrutura de uma solução ótima. 2 - Definir recursivamente o valor de uma solução ótima. 3 - Calcular o valor de uma solução ótima em um processo bottom-up. 4 - Construir a solução ótima a partir das informações já calculadas 1 – Escalonamento de Intervalos Ponderados Dada uma coleção S de intervalos, encontrar uma subcoleção disjunta com o máximo valor possível. Sub Estrutura Ótima: Suponha que C seja um conjunto….

    exibir mais
  • Análise de algoritmos
    591 palavras | 3 páginas

    Lista-1 de Exercícios – Elaborar ALGORITMOS e DIAGRAMAS de BLOCOS: 1) Ler 4 notas, calcular a média e apresentar as mensagens “Aprovado” ou “Reprovado” conforme o resultado da média encontrada. Para aprovação, a média deverá ser maior ou igual a 6.0. 2) Faça um algoritmo que receba dois números e exiba o resultado da sua soma. 3) Desenvolva um algoritmo que solicite 2 números e apresente o maior deles. 4) Faça um algoritmo que receba dois números e ao final mostre a soma, subtração….

    exibir mais
  • Analise de algoritmos
    383 palavras | 2 páginas

    analisando os métodos para quatro objetos. Percebemos que o algoritmo guloso ordenado pela densidade sempre será mais custoso que os outros dois, guloso valor e guloso peso, pois ele cria um novo vetor para guardar os valores da divisão do valor pelo peso. Assim como o algoritmo de aproximação linear sempre levará mais tempo que a programação dinâmica, já que ele faz uso desta.(BARBOSA, 2012; PEREIRA et al, 2012) Ao analisar qual dos algoritmos foi mais eficiente temos: Guloso peso e valor terminaram….

    exibir mais

Outros Trabalhos Populares