FenixEdu™

Disciplina

Algoritmos Avançados

Área

Área Científica de Metodologia e Tecnologias da Programação > Algoritmos

Activa nos planos curriculares

MEIC-T 2021 > MEIC-T 2021 > 2º Ciclo > Área Principal > Agrupamentos > Bioinformática e Biologia Computacional > Algoritmos Avançados

MECD2019 > MECD2019 > 2º Ciclo > Opções > Algoritmos Avançados

MEIC-T 2015 > MEIC-T 2015 > 2º Ciclo > Agrupamentos > Bioinformática e Biologia Computacional > Algoritmos Avançados

MEIC-A 2021 > MEIC-A 2021 > 2º Ciclo > Area Principal > Agrupamentos > Tecnologias da Informação e Linguagem > Algoritmos Avançados

MEIC-A 2015 > MEIC-A 2015 > 2º Ciclo > Agrupamentos > Bioinformática e Biologia Computacional > Algoritmos Avançados

MEIC-A 2006 > MEIC-A 2006 > 2º Ciclo > Área de Especialização Complementar > Ciência da Computação > Algoritmos Avançados

DEASegInf2007 > DEASegInf2007 > 3º Ciclo > Engenharia Informática > Metodologia e Tecnologia da Programação > Algoritmos Avançados

MMA 2006 > MMA 2006 > 2º Ciclo > Perfis > Matematica da Computação > Metodologia e Tecnologia da Programação > Algoritmos Avançados

Nível

Exame e componente prática. O exame contribui com 50% para a nota final (FM) e o aluno tem de obter pelo menos 7.5 valores num dos exames. A componente prática contribui 50% para a nota final (FM). FM = 0.5 * max(E1, E2) + 0.5 * P Aprovado se max(E1, E2) >= 7.5 e FM >= 9.5.

Tipo

Não Estruturante

Regime

Semestral

Carga Horária

1º Semestre

Aula Teórica (T): 2.0 h/semana

Aula de Laboratório (PL): 1.5 h/semana

Trabalho Autónomo: 119.0 h/semestre

Créditos ECTS:

Objectivos

Os algoritmos e as estruturas de dados estão na base de qualquer aplicação ou sistema informático, tendo vindo a ganhar cada vez maior relevância com novos desafios no que respeita ao volume de dados a processar, aos requisitos de eficiência e de processamento em tempo real, e à complexidade dos problemas com que nos deparamos hoje em dia. O objectivo desta unidade curricular é portanto a formação avançada em técnicas de desenvolvimento e análise de algoritmos com particular foco em estruturas de dados avançadas para indexação, algoritmos randomizados, algoritmos de aproximação, algoritmos para processamento online e em tempo real, e estruturas de dados e algoritmos para processamento de grandes volumes de dados. Esta unidade curricular seguirá uma abordagem baseda na resolução de problemas em que as técnicas de desenho e análise das estruturas de dados e algoritmos serão motivadas e exploradas de forma intuitiva e construtiva, incluindo as técnicas de implementação relevantes.

Programa

Desenho e análise de estruturas de dados avançadas, como B-trees, splay-trees e árvores cartesianas. Filas com prioridade baseadas em amontoados binomiais, de Fibonacci, e relaxados. Análise amortizada. Estruturas de dados sucintas/compactas. Algoritmos e estruturas de dados para processamento eficiente de strings, como árvores e arrays de sufixos. Algoritmos e estruturas de dados para processamento eficiente de árvores e grafos. Optimização combinatória. Técnicas probabilísticas e de teoria de jogos aplicadas à análise e desenho de algoritmos e estruturas de dados. Algoritmos de aproximação. Algoritmos com escolhas aleatórias. Algoritmos online e sobre streams. Algoritmos e estruturas de dados para processamento de grandes volumes de dados. Técnicas de implementação, utilização prática, e avaliação experimental.

Metodologia de avaliação

Pré-requisitos

Introdução aos Algoritmos e Estruturas de Dados, e Análise e Síntese de Algoritmos, da LEIC, ou UCs com programas semelhantes.

Componente Laboratorial

Aplicação das técnicas discutidas nas aulas teóricas, e estudadas na sequência das mesmas, na resolução de problemas, nomeadamente propostos nos trabalhos práticos e na implementação dos algoritmos e estruturas de dados inerentes às soluções alcançadas.

Princípios Éticos

Todos os membros de um grupo são responsáveis pelo trabalho do grupo. Em qualquer avaliação, todo aluno deve divulgar honestamente qualquer ajuda recebida e fontes usadas. Numa avaliação oral, todo aluno deverá ser capaz de apresentar e responder a perguntas sobre toda a avaliação.

Componente de Programação e Computação

No curso onde esta UC é oferecida estão asseguradas as componentes de Computação e Programação de acordo com o MEPP 2122. Esta UC contribui em particular com técnicas de implementação prática de algoritmos e estruturas de dados avançadas.

Componente de Competências Transversais

Não existindo uma componente explícita de Competências Transversais a desenvolver no âmbito desta UC, o trabalho prático, em grupo, levará ao desenvolvimento de Pensamento Crítico e Inovador, Competências Intrapessoais, e Competências Interpessoais.