Desenho e Analise de Algoritmos

Pedro Ribeiro

DCC/FCUP

2014/2015

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 1 / 13

Informacoes Gerais

Site: http://www.dcc.fc.up.pt/~pribeiro/aulas/daa1415/

Piazza: http://piazza.com/up.pt/fall2014/cc2001

Aulas teoricas:I 2a Feira: 15:30 as 16:30 (Sala 0.40, FC4)I 4a Feira: 15:00 as 16:00 (Sala 0.40, FC4)

Aulas praticas:I PL1: 3a Feira: 09:00 as 11:00 (Lab4, Veronica Orvalho)I PL2: 4a Feira: 11:00 as 13:00 (Lab2, Pedro Ribeiro)I PL3: 5a Feira: 10:00 as 12:00 (Lab2, Pedro Ribeiro)I PL4: 2a Feira: 10:00 as 12:00 (Lab1, Veronica Orvalho)I PL5: 3a Feira: 16:00 as 18:00 (Lab3, Pedro Ribeiro)

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 2 / 13

Obtencao de Frequencia

Nao serao registadas presencas (teoricas e praticas)

Semanalmente, serao feitos questionarios:I Sao obrigatorios, mas nao contam para notaI Cada um estara online durante uma semanaI Sao constituıdos essencialmente por perguntas de escolha multiplaI Para obter frequencia e necessario ter respondido a 80%

12 questionarios → so podem nao responder a 2

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 3 / 13

Formula de Calculo da Avaliacao

NP: nota obtida num teste pratico de programacao com avaliacaoautomatica pelo sistema Mooshak (peso de 20% na nota final);Nota mınima, NP > 0 (escala da nota: 0 a 4)

E: exame escrito final (peso de 80% na nota final, nota de 0 a 20)

F: media de dois testes escritos (TE1 e TE2) a realizar durante osemestre para dispensa de exame final (TE1 e TE2 incidirao sobreconjuntos de materias diferentes). Os estudantes com classificacaoinferior a 6.0 no primeiro teste nao poderao realizar o segundo.F = 0.5*TE1 + 0.5*TE2. Para dispensa de exame, F >= 7.0.

Classificacao da epoca normal: C = max(E ,F ) ∗ 0.8 + NP >= 9.5Classificacao da epoca de recurso: C = E ∗ 0.8 + NP >= 9.5

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 4 / 13

Datas dos Testes

Estas datas sao neste momento provisorias:

1o teste escrito: 14 de Novembro

2o teste escrito: 19 de Dezembro

Teste pratico de programacao: semana de 5 a 9 de Janeiro

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 5 / 13

Pre-requisitos

Conhecimentos de C/C++ ou Java

Conhecimentos de algoritmos basicos(contagem, pesquisa, ordenacao, ...)

Conhecimentos de estruturas de dados basicas(arrays, listas, pilhas, filas, ...)

Preferencialmente ter concluıdo as unidades curriculares de”Introducao a Programacao” e ”Estruturas de Dados”(ou equivalente)

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 6 / 13

Objectivos da Unidade Curricular

Competencia na area de tecnicas de concepcao e analise de algoritmoseficientes:

Competencia na analise da complexidade de algoritmos ecompreensao de algumas classes de complexidade

Enriquecimento do conhecimento sobre modelos genericos de tiposde problemas e tecnicas algorıtmicas a eles associadas.

Experiencia pratica na aplicacao de algoritmos genericos aproblemas concretos.

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 7 / 13

Visao Geral do Programa

Analise assintotica do tempo de execucao de algoritmos:

Notacao Big O (O, Ω e Θ)

Analise de programas iterativos

Analise de programas recursivos

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 8 / 13

Visao Geral do Programa

Tecnicas de Desenho de Algoritmos

Pesquisa exaustiva

Dividir para conquistar

Algoritmos greedy

Programacao dinamica

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 9 / 13

Visao Geral do Programa

Algumas estruturas de dados especializadas

Filas de prioridade

Conjuntos disjuntos

Arvores binarias de pesquisa equilibradas (dependendo do tempo)

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 10 / 13

Visao Geral do Programa

Algoritmos de grafos

Representacao de grafos

Pesquisa em largura e pesquisa em profundidade

Arvores de cobertura mınima

Caminhos mınimos

Redes de fluxo (dependendo do tempo)

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 11 / 13

Visao Geral do Programa

Introducao a teoria da complexidade(dependendo do tempo)

Classes P, NP e co-NP

A questao P!=NP

Nocoes de reducao de problemas

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 12 / 13

Funcionamento das aulas

Teoricas: slides +uso do computador do docente +exposicao no quadro

Praticas: guiao com exercıcios (em papel) +implementacao em codigo (C/C++ ou Java)

Material auxiliar: divulgado no site, em portugues e/ou inglesslides, apontamentos, animacoes, applets, ...

Pedro Ribeiro (DCC/FCUP) Desenho e Analise de Algoritmos 2014/2015 13 / 13