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: 2021/2022 - 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	365	Plano Oficial	2	-	6	52	162

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

Esta unidade curricular complementa e aprofunda os conhecimentos assimilados na unidade curricular de Algoritmos e Estruturas de Dados, pela introdução de técnicas de conceção de algoritmos para a resolução de diferentes tipos de problemas.

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 conceção de algoritmos;
• conhecer e saber aplicar algoritmos avançados em grafos;
• conhecer e saber aplicar algoritmos em cadeias de caracteres;
• identificar problemas intratáveis e algoritmos que fornecem soluções aproximadas;
• identificar problemas de otimização matemática e conhecer e saber aplicar algoritmos para resolução de alguns tipos de problemas de otimização linear e nã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 tido frequência às seguintes unidades curriculares: L.EIC009 - Programação; L.EIC011 - Algoritmos e Estruturas de Dados

Programa

1. Técnicas de conceção de algoritmos: divisão e conquista; algoritmos gananciosos; programação dinâmica; algoritmos de retrocesso; aplicações.


2. Programação linear: problemas de otimização com restrições; resolução pelo algoritmo simplex.


3. Algoritmos avançados em grafos: fluxo máximo e fluxo de custo mínimo em redes de transporte; circuito de Euler e problema do carteiro chinês; problemas de emparelhamento e casamentos estáveis.


4. Algoritmos em strings: pesquisa exata; pesquisa aproximada; compressão de texto.


5. Problemas intratáveis: teoria dos problemas NP-completos; redução de problemas; exemplos de problemas intratáveis; algoritmos polinomiais aproximados.


6. Algoritmos numéricos: determinação de raízes de funções; resolução de sistemas de equações lineares e não lineares; determinação de mínimos locais pelo método da descida de gradiente; análise do erro; aplicações.

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

A metodologia de ensino desta unidade curricular é caracterizada pela adoçã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 resolução de exercícios e desenvolvimento de pequenos programas para testar os algoritmos desenvolvidos, com acompanhamento tutorial.

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 mais integrada e holística de todo o conhecimento adquirido, a realização de um projeto completo, como principal suporte da avaliação prática permite ao estudante consolidar as competências anteriormente mencionadas, e ainda iv) avaliar, tanto analítica assim como empiricamente a qualidade da solução concebida, a nível de eficiência e de correção. A partir do exame final, o estudante deve demonstrar autonomamente os conhecimentos adquiridos, tanto a nível prático assim como a nível teórico. Desta forma, os métodos de ensino e de avaliação propostos suportam a efetiva consolidação das quatro competências enunciadas anteriormente.

Software

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

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 (%)
Exame	70,00
Trabalho prático ou de projeto	30,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 esta Unidade Curricular 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 condicionada na parte prática (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);
• Trabalho de grupo 2 (T2);

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

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

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

• NT = 0,7 * EF + 0,3 * 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.