Desenho de Algoritmos

Código:

L.EIC016

Sigla:

DA

Áreas Científicas
Classificação	Área Científica
OFICIAL	Engenharia Informática e Computação

Ocorrência: 2022/2023 - 2S

Ativa?	Sim
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Licenciatura 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
L.EIC	422	Plano Oficial	2	-	6	52	162

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

Esta unidade curricular visa complementar e aprofundar os conhecimentos de implementação e concepção de algoritmos assimilados na unidade curricular de Algoritmos e Estruturas de Dados (AED), pela introdução de técnicas de concepção de algoritmos para a resolução de diferentes tipos de problemas, dado particular relevo a técnicas estruturantes como “brute-force”, “backtracking”, “divide-and-conquer”, “greedy” e “dynamic programming” ubíquas em algoritmos avançados na vida real.

Resultados de aprendizagem e competências

No final da unidade curricular, espera-se que o estudante seja capaz de:

• Conhecer e saber aplicar técnicas genéricas de concepção de algoritmos;
• Conhecer e saber aplicar algoritmos avançados em árvores e grafos;
• Identificar problemas intratáveis e algoritmos que fornecem soluções aproximadas;
• Identificar problemas de optimização matemática e conhecer e saber aplicar algoritmos para resolução de alguns tipos de problemas de optimização usando técnicas de backtracking e de optimização linear.

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 concluído com sucesso as seguintes unidades curriculares: L.EIC009 - PROG; L.EIC011 – AED.

Programa

1. 
   
   
   
   1. Revisão de Notação de Complexidade Assimptótica e Estruturas de Dados Básicas.
   
   
   2. 
      

      Abordagem Algorítmica de Força-Bruta (“Brute-Force”) e aplicação em problemas de optimização de peuena escala.

      
      
   
   
   3. 
      

      Algoritmos Gulosos (“Greedy”) e suas Aplicações.

      
      
   
   
   4. 
      

      Algoritmos de Divisão e Conquista (“Divide-and-Conquer”) com aplicações em algoritmos numéricos.

      
      
   
   
   5. 
      

      Algoritmos de Programação Dinâmica.

      
      
   
   
   6. 
      

      Optimização usando Programação Linear (LP) e introdução a programação linear inteira (ILP).

      
      
   
   
   7. 
      

      Algoritmos com retrocesso (“backtracking”) e expansão e poda (“Branch-and-Bound”)

      
      
   
   
   8. 
      

      Problemas de complexidade exponencial. redução entre problemas e utilização de técnicas de aproximação polynomial.

      
      
   
   
   
   

Bibliografia Obrigatória

Thomas H. Cormen... [et al.]; Introduction to algorithms. ISBN: 978-0-262-53305-8

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

A metodologia de ensino desta unidade curricular é caracterizada pela adopção de componentes teóricas e práticas de forma integrada, tanto nas aulas como nos vários momentos de avaliação. 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 consolidação da matéria teórica recorrendo a exemplos ilustrativos bem como para apoio dos alunos na concepção e implementação dos 2 projectos de programação que fazem parte integrante da avaliação desta disciplina.

A consolidação prática do conhecimento teórico adquirido, numa perspectiva de "aprender fazendo" permite então ao estudante adquirir competências em: i) caracterizar um dado problema; ii) formalizar o problema de maneira precisa; e, iii) identificar a técnica de concepção de algoritmos mais apropriada para a sua solução. Numa perspectiva integrada e holística de todo o conhecimento adquirido, os alunos realizarão 2 projetos de programação (recorrendo a técnicas e competências adquiridas na disciplina de AED), e de uma forma faseada, em que aplicam várias das técnicas de desenho e implementação de algoritmos complexos.

Software

GoogleTest, Google's C++ test framework
The CLion cross-platform IDE for C and C++ by JetBrains

Palavras Chave

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

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Designação	Peso (%)
Trabalho prático ou de projeto	40,00
Teste	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

Não há aferição de frequência das aulas prácticas (TP), exepto para efeitos de demonstração dos projectos de programação durante as quais todos os elementos do grupo teem que estar presentes.

 Notas Mínimas nos vários elementos de avaliação:

• Todos os elementos de classificação possuem nota mínima de 8.0 valores (sem arredondamento) sendo o aluno automaticamente inscrito na época de recurso.
• Os dois projectos de programação não são passíveis de recurso ou de melhoria, pelo que a não obtenção de nota mínima num deles, implica a reprovação à disciplina.

A título excepcional, este ano apenas, alunos que reprovaram no ano anterior de 2021/22 e desejem manter as classificações dos dois projectos de programação (P1 e P2) poderão fazê-lo, tendo apenas de realizar os mini-testes (T1 e T2).

No entanto, para os anos que se seguem esta política não vai ser seguida.

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

A nota final é baseada nas seguintes componentes:

• Dois mini-testes individuais (T1 e T2), escritos e sem consulta com duração de 1.5 horas (e tolerância de 30 mins).
• Dois projectos de programação (P1 and P2) em grupos de 3 alunos (máximo) e 2 alunos (mínimo).

A nota individual em cada projecto reflecte uma componente de 75% em grupo e uma componente de 25% individual. A componente de avaliação colectiva reflecte a correção da implementação da solução do problema bem como a abordagem seguida, enquanto que a componente individual reflecte a esforço individual na execução do projecto. Cada grupo, além de submeter a sua solução e respectivos inputs e output selecionados, deverá igualmente submeter um relatório simples descrevendo a sua solução evidenciando os eventuais aspectos inovadores da mesma.

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

NF = (0.30 *(T1 + T2)) + (0.20 * (P1+P2)) 

onde T1, T2, P1 e P2 terão que ser superiores ou iguais a 8.0, sendo apenas depois deste cálculo, arredondada as unidades.

Provas e trabalhos especiais

N/A

Trabalho de estágio/projeto

Esta componente inclui a realização de 2 projetos (P1 e P2) de programação (recorrendo a técnicas e competências adquiridas na disciplina de AED), e de uma forma faseada, em que aplicam várias das técnicas de desenho e implementação de algoritmos complexos. Os trabalhos serão realizados por grupo no máximo de 3 alunos em focarão em problemas específicos para os quais se vias a aplicação de técnicas e soluções algorítmicas estudadas nesta disciplina de desenho de algoritmos (DA). Deverão ser realizados e demonstrados recorrendo ao ambiente de programação desenvolvido na disciplina de AED. No entanto, e á descrição do regente da disciplina, e em consulta com os docentes auxiliares da mesma, poderão aos alunos requerer o desenvolvimento e demonstração dos mesmos noutros ambientes de desenvolvimento.

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

Os estudantes que frequentam a Unidade Curricular ao abrigo de estatutos especiais (e.g., Trabalhador-Estudante ou Atletas de Alta-Competição) 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

Apenas as classificações dos mini-testes em época normal poderão ser melhoradas (ou “represcadas” caso não cumpram com o requisito de nota mínima) na época de recurso, no mesmo semestre.

Observações

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