Saltar para:
Logótipo
This page in english Ajuda Autenticar-se
Formação regular da Biblioteca |fevereiro a maio
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: 2018/2019 - 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 176 Plano de estudos a partir de 2009/10 2 - 6 56 162

Docência - Responsabilidades

Docente Responsabilidade
Rosaldo José Fernandes Rossetti Regente

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 7 14,00
João Caetano Soares Filgueiras 2,00
Francisco Xavier Richardson Rebello de Andrade 4,00
Luís Filipe Guimarães Teófilo 2,00
Liliana da Silva Ferreira 2,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 e análise 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 fronteira;
  • conceber algoritmos eficientes para solucionar o problema em mãos;
  • avaliar a solução concebida do ponto de vista da sua eficiência e correção.

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. Formalização de problemas; representação de algoritmos; análise da sua complexidade (temporal e espacial); verificação da 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 3 (três) estudantes. Apesar de realizados em grupo, a avaliação terá em consideração o desempenho individual de cada estudante no grupo.

Software

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

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.

O primeiro trabalho prático (T1) deve ser entregue até ao final do dia 8 de abril de 2018.

O segundo trabalho prático (T2) deve ser entregue até ao final do dia 20 de maio de 2018.

Recomendar Página Voltar ao Topo
Copyright 1996-2019 © 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: 2019-05-22 às 20:23:19 | Política de Utilização Aceitável | Política de Proteção de Dados Pessoais