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: 2017/2018 - 2S

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

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.