Saltar para:
Logótipo
This page in english Ajuda Autenticar-se
Pré-candidaturas mobilidade 2019/2020
Você está em: Início > EIC0110
Autenticação




Mapa das Instalações
Edifício A (Administração) Edifício B (Aulas) - Bloco I Edifício B (Aulas) - Bloco II Edifício B (Aulas) - Bloco III Edifício B (Aulas) - Bloco IV Edifício C (Biblioteca) Edifício D (CICA) Edifício E (Química) Edifício F (Minas e Metalurgia) Edifício F (Minas e Metalurgia) Edifício G (Civil) Edifício H (Civil) Edifício I (Electrotecnia) Edifício J (Electrotecnia) Edifício K (Pavilhão FCNAUP) Edifício L (Mecânica) Edifício M (Mecânica) Edifício N (Garagem) Edifício O (Cafetaria) Edifício P (Cantina) Edifício Q (Central de Gases) Edifício R (Laboratório de Engenharia do Ambiente) Edifício S (INESC) Edifício T (Torre do INEGI) Edifício U (Nave do INEGI) Edifício X (Associação de Estudantes)

Concepção e Análise de Algoritmos

Código: EIC0110     Sigla: CAL

Áreas Científicas
Classificação Área Científica
OFICIAL Programação

Ocorrência: 2014/2015 - 2S Ícone do Moodle

Ativa? Sim
Unidade Responsável: Departamento de Engenharia Informática
Curso/CE Responsável: Mestrado Integrado em Engenharia Informática e Computação

Ciclos de Estudo/Cursos

Sigla Nº de Estudantes Plano de Estudos Anos Curriculares Créditos UCN Créditos ECTS Horas de Contacto Horas Totais
MIEIC 159 Plano de estudos a partir de 2009/10 2 - 6 56 162

Docência - Horas

Teóricas: 2,00
Teórico-Práticas: 2,00
Tipo Docente Turmas Horas
Teóricas Totais 1 2,00
Rosaldo José Fernandes Rossetti 2,00
Teórico-Práticas Totais 6 12,00
Ana Paula Cunha da Rocha 4,00
Tiago Boldt Pereira de Sousa 4,00
Rosaldo José Fernandes Rossetti 4,00

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

Esta Unidade Curricular tem por objectivo complementar e aprofundar os conhecimentos assimilados nas disciplinas de "Programação" e de "Algoritmos e Estruturas de Dados", nomeadamente pela introdução de técnicas de concepção e implementação de algoritmos eficientes para a resolução de diferentes tipos de problemas, assim como a sua análise e avaliação.

Mais especificamenet, pretende-se permitir aos estudantes:

  • conhecer e saber aplicar algoritmos eficientes em grafos, conjuntos e cadeias de caracteres;
  • conhecer e saber aplicar técnicas genéricas de concepção de algoritmos;
  • conhecer alguns problemas intratáveis e algoritmos que fornecem soluções aproximadas para alguns deles. 

Resultados de aprendizagem e competências

No final da Unidade Curricular, espera-se que o estudante seja capaz de:

  • caracterizar o problema que lhe é apresentado;
  • formalizar o problema, identificando dados de entrada, restrições e condições de contorno;
  • conceber algoritmos eficientes para solucionar o problema em mãos;
  • avaliar a solução concebida.

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

É desejável e necessário que os estudantes tenham conhecimentos fundamentais de programação orientada por objectos, estruturas de dados e tipos abstratos de dados. É recomendável que os estudantes já tenham tido frequência às seguintes unidades curriculares: EIC0012 - Programação; EIC0013 - Algoritmos e Estruturas de Dados

Programa


  1. Técnicas de concepção de algoritmos: divisão e conquista; algoritmos gananciosos ("greedy"); programação dinâmica; algoritmos de retrocesso ("backtracking"); algoritmos probabilísticos.

  2. Representação e formalização de algoritmos, análise da sua complexidade (temporal e espacial); verificação e correcção dos algoritmos.

  3. Estruturas de dados avançadas: filas de prioridade com alteração de prioridade; conjuntos disjuntos.

  4. Algoritmos eficientes em grafos: visita em largura e em profundidade; ordenação topológica; componentes biconexos; componentes fortemente conexos; caminho mais curto; árvore de expansão mínima; fluxo máximo e fluxo máximo de custo mínimo em redes de transporte; circuito de Euler e problema do carteiro chinês; problemas de emparelhamento ("matching") e casamentos estáveis.

  5. Algoritmos em "strings": pesquisa exacta ("string matching"); pesquisa aproximada; "substring" comum mais comprida; compressão de texto.

  6. Problemas intratáveis: redução de problemas; teoria dos problemas NP-completos; exemplos de problemas intratáveis em grafos; algoritmos que fornecem soluções aproximadas em tempo polinomial para alguns problemas.

Bibliografia Obrigatória

Thomas H. Cormen... [et al.]; Introduction to algorithms. ISBN: 978-0-262-53305-8
Steven S. Skiena; The algorithm design manual. ISBN: 0-387-94860-0
Sedgewick, Robert; Algorithms in C++ Part 5: Graph Algorithms, 3/E, Addison-Wesley Professional, 2001. ISBN: 0201361183

Observações Bibliográficas

Outros links e materiais de apoio serão disponibilizados no sítio Web da Unidade Curricular.

Métodos de ensino e atividades de aprendizagem

DISTRIBUIÇÃO PERCENTUAL * 60% Teoria: introdução dos diversos conceitos e exemplos de aplicação sobre técnicas de concepção de algoritmos, estruturas em grafos, algoritmos sobre strings e ficheiros, problemas NP-completos. * 40% Prática: práticas de laboratório em que se espera que os estudantes realizem exercícios sobre os tópicos apresentados nas aulas teóricas.

As aulas teóricas são usadas para a exposição formal da matéria, acompanhada da apresentação de exemplos e sua discussão. As aulas práticas são usadas para a resolução de exercícios e desenvolvimento de pequenos programas em C++ para testar os algoritmos desenvolvidos. Os estudantes também deverão realizar trabalhos práticos, em grupos de 2 (dois) estudantes no máximo. Apesar de realizados em grupo, a avaliação terá em consideração o desempenho individual de cada estudante no grupo.

Software

Eclipse C++
Cute C++ Unit Testing Framework (plug-in p/ Eclipse)

Palavras-chave

Ciências Físicas > Matemática > Algoritmos
Ciências Tecnológicas > Tecnologia > Tecnologia de computadores > Tecnologia de software

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação Peso (%)
Defesa pública de dissertação, de relatório de projeto ou estágio, ou de tese 40,00
Exame 60,00
Total: 100,00

Componentes de Ocupação

Designação Tempo (Horas)
Elaboração de projeto 50,00
Estudo autónomo 56,00
Frequência das aulas 28,00
Trabalho laboratorial 28,00
Total: 162,00

Obtenção de frequência

Para obtenção de frequência:

  • O estudante deverá cumprir com o requisito do número máximo de faltas permitido às aulas práticas;
  • Em cada componente da avaliação distribuída, assim como no exame, o estudante deverá obter nota superior a 40% naquele momento de avaliação (>= 8 valoers).

Estudantes que tenham frequentado a Unidade Curricular "Concepção e Análise de Algoritmos" (CAL) no ano lectivo anterior e tenham obtido nota de frequência, estão dispensados de frequentar a cadeira, tendo apenas de realizar o exame final (EF). No entanto, se quiserem melhorar a nota da componente distribuída, terão de frequentar a unidade curricular novamente.

Fórmula de cálculo da classificação final

A nota final é baseada nas seguintes componentes:

  • Exame final (EF) com consulta (somente livros e slides das aulas teóricas), com duração de 2 horas
  • Componente distribuída (CD), composta por dois trabalhos práticos de grupo:
    • Trabalho de grupo 1 (T1) – Grafos
    • Trabalho de grupo 2 (T2) – strings/ficheiros

A classificação CD correspondente à componente distribuída é calculada da seguinte forma:

  • CD = 0,60 *T1 + 0,4 * T2, onde T1 >= 8 valores e T2 >= 8 valores

A nota final (NF) é calculada da seguinte forma:

  • NT = 0,6 * EF + 0,4 * CD, onde EF >= 8 valores

Provas e trabalhos especiais

N/A

Trabalho de estágio/projeto

N/A

Avaliação especial (TE, DA, ...)

Os estudantes que frequentam a Unidade Curricular ao abrigo de estatutos especiais têm os mesmos requisitos de avaliação de frequência dos estudantes regulares, devendo realizar os trabalhos práticos nas épocas estabelecidas. Poderá, entretanto, acordar com o docente das aulas práticas uma data e hora para apresentação dos trabalhos fora dos horários da aula prática.

Melhoria de classificação

A classificação distribuída pode ser melhorada na ocorrência seguinte da unidade curricular. A nota do exame de época normal poderá ser melhorada no exame da época de recurso, no mesmo semestre.

Observações

É aconselhável que os estudantes tenham cursado previamente as Unidades Curriculares de "Programação" e de "Algoritmos e Estruturas de Dados" para potenciar melhor aproveitamento.

Recomendar Página Voltar ao Topo
Copyright 1996-2018 © Faculdade de Engenharia da Universidade do Porto  I Termos e Condições  I Acessibilidade  I Índice A-Z  I Livro de Visitas
Página gerada em: 2018-12-15 às 01:10:37 | Política de Utilização Aceitável | Política de Proteção de Dados Pessoais