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: 2023/2024 - 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	425	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. Pretende-se igualmente, introduzir os conceitos de problemas de grande complexidade formalizados nos conceitos de hierarquia de complexidade polinomial determinística e não-deterministica, e respectiva técnica de redução polinomial entre problemas e sua abordagem na práctica com o uso de algoritmos de aproximação. Finalmente, esta unidade curricular aborda ainda as técnicas algorítmicas de optimização de problemas usando a formalização de programação linear inteira ou 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

A aferição de frequência nesta UC incide apenas nas componentes de projectos de grupo de programação em que a classificação mínima nos dois projectos é de 8.0. A não obtenção da classificação de 8.0 valores num dos dois projectos resulta num RFF uma vez que a classificação dos projectos não é passível de melhoria.

Não há requisites de presença nas aulas TP `a excepção nas aulas em que há demonstração dos projectos (demo).

Não são aceites classificações de qualquer elemento de classificação de anos anteriores.

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

A nota final é baseada nas seguintes componentes numa escala de 0.0 a 20.0 valores:

 

• 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.

Caso, uma das componentes não tenha classificação supoerior ou igual a 8.0, o estudante é reprovado por falta de componente, e elegível para recurso em que poderá repescar essa componente, ou componentes em falta. 

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, possivelmente com o pagamento de um emolumento. Podem os estudantes, no entanto melhorar uma das notas dos dois mini-testes para os quais não obtiveram a classificação mínima de 8.0 valores. Se desejarem, e por não terem nota mínima num dos dois mini-testes, podem e apenas quando atempadamente requerido e autorizado pelos regentes, repescar ambas os mini-testes (por via de um exame global da matéria), abrindo assim, mão de uma das classificações dos mini-testes que cumpriam com o requisito mínimo e mesmo possivelmente acima de 10 valores. Neste último caso, não necessitam de se inscrever em época de melhoria.

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.