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: 2024/2025 - 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	367	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 na reprovação da UC com RFF uma vez que a classificação dos projectos não é passível de melhoria. A não obtenção de classificação de 8.0 valores num dos dois testes resulta na reprovação `a UC com RFF.

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

A melhoria de classificação é feita através de um exame escrito (exame global), a realizar na época de recurso, sobre toda a matéria lecionada durante o semestre.

Não é possível melhorar a classificação de testes individuais, nem dos trabalhos práticos realizados.

Não é permitida a melhoria por frequência.

A inscrição no exame de melhoria de classificação está sujeita ao pagamento de um emolumento, de acordo com os valores indicados na Tabela de Emolumentos da Universidade do Porto, que deve ser liquidado previamente à realização do exame.

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.