AEDII-aula09

Prévia do material em texto

1
Aula 09 – Sobre a prova 01 e a 
Monografia
MC3305
Algoritmos e Estruturas de Dados II
Prof. Jesús P. Mena-Chalco
jesus.mena@ufabc.edu.br
2Q-2014
2
Parte I – Questão 1
A sequência (b) é impossível desde que 
todos os elementos depois de 347 devem 
ser maiores ou iguais do que 347. 
No caso em particular, o elemento 299 
não é possível na busca em uma ABB.
2
399
387
219
266
382
381
278
363
935
278
347
621
299
3
Parte I – Questão 2
Seja o número de operações necessárias para calcular o maior 
elemento de uma matriz com n linhas e m colunas.
Abordagem (a):
Abordagem (b):
Independentemente do número de linhas e colunas, ambas as abordagens 
consomem nm-1 operações (comparações) para calcualr o maior elemento da 
matriz.
4
Parte I – Questão 3
int buscabinaria(int x, int n, int v[ ])
{
 int m;
 int e = ??;
 int d = ??;
 while (e ?? d-1)
 {
 m = (e + d)/2;
 if (v[m] ?? x)
 e = m;
 else 
 d = m; 
 }
 return ??; 
}
5
Parte I – Questão 3
int buscabinaria(int x, int n, int v[ ])
{
 int m;
 int e = -1;
 int d = n;
 while (e < d-1)
 {
 m = (e + d)/2;
 if (v[m] < x)
 e = m;
 else 
 d = m; 
 }
 return d; 
}
Esta função recebe um vetor
crescente v[0..n-1] com n >= 1
e um número x.
Ela devolve um índice j em 0..n 
tal que v[j-1] < x <= v[j].
Sua complexidade é O(lg n)
O algoritmo é tratável pois
existe um algoritmo O(n)
para buscar um elemento x em um
vetor ordenado, isto é, existe uma
Solução polinomial.
6
Parte I – Questão 3
Um problema é considerado
Intratável:
Se ele é tão difícil que não se conhece um algoritmo 
polinomial para resolvê-lo
Ex. Algoritmo do caixeiro viajante
Tratável (bem resolvido):
Se existe um algoritmo polinomial para resolvê-lo.
Ex. Algoritmo de multiplicação de matrizes.
← Algoritmo de Strassen
7
Parte II – Questão 4
O Professor Progresso encontrou um algoritmo de ordenação baseado em 
comparações que gasta tempo.
Considerando-se o limitante inferior para o tempo de ordenação, isso é 
possível? 
8
Parte I – Questão 4
O Professor Progresso encontrou um algoritmo de ordenação baseado em 
comparações que gasta tempo.
Considerando-se o limitante inferior para o tempo de ordenação, isso é 
possível? 
Sim é possível dado que:
Que ainda é uma limitante “assintoticamente boa” para a ordenação baseada em 
comparações.
9
Parte I – Questão 4
Descreva informalmente (não escreva código) um algoritmo que, em tempo 
O(n), ordena n inteiros, cada um deles em {1,2,3,..., n³}. Justifique sua 
resposta. 
A
C
B
10
Parte I – Questão 4
Descreva informalmente (não escreva código) um algoritmo que, em tempo 
O(n), ordena n inteiros, cada um deles em {1,2,3,..., n³}. Justifique sua 
resposta. 
10 → 00001010
26 → 00011010
32 → 00100000
64 → 01000000
98 → 01100010
99 → 01100011
100 → 01100100
11
Parte I – Questão 4
Descreva informalmente (não escreva código) um algoritmo que, em tempo 
O(n), ordena n inteiros, cada um deles em {1,2,3,..., n³}. Justifique sua 
resposta. 
32 → 00100000
10 → 00001010
98 → 01100010
64 → 01000000
100 → 01100100
99 → 01100011
26 → 00011010
00100000
00001010
01100010
01000000
01100100
00011010
01100011
00100000
01000000
01100100
00001010
01100010
00011010
01100011
00100000
01000000
00001010
01100010
00011010
01100011
01100100
00100000
01000000
01100010
01100011
01100100
00001010
00011010
1 2 3 4 5 6 7
00100000
01000000
01100010
01100011
01100100
00001010
00011010
01000000
00001010
00011010
00100000
01100010
01100011
01100100
00001010
00011010
00100000
01000000
01100010
01100011
01100100
← 10
← 26
← 32 
← 64
← 98 
← 99
← 100
Dígito:
12
Parte II – Questão 1
13
Parte II – Questão 1
Melhor caso: 1
Pior caso: lg(n)
14
Parte II – Questão 2
Uma árvore é balanceada no sentido AVL se, para cada nó x, as alturas 
das subárvores que têm raízes x->esq e x->dir diferem de no máximo 
uma unidade. Escreva uma função que decida se uma dada árvore é 
balanceada no sentido AVL.
Escrever sua função de modo que ela visite cada nó no máximo 
uma vez. 
Atividade +1 ponto na P1: Dia 01/08 às 23h50
Os arquivos que deverá submeter pelo Tidia são:
● Código fonte em C/C++
(isAVL-RA.cpp)
● Um PDF contendo um exemplo de execução 
isAVL-RA.pdf)
Nota: o formato desse relatório é livre. Quando mais completo, melhor.
15
Sobre a avaliação
16
Sobre a avaliação
17
Sobre a avaliação
Prova 01: 24 de julho → 30%
Prova 02: 28 de agosto → 30%
Exercícios-problema → 25%
Monografia + apresentação de tópicos especiais →15%
Atribuição de conceitos:
A: nota ≥ 8,5
B: 7 ≤ nota < 8,5
C: 5,5 ≤ nota < 7
D: 5,0 ≤ nota < 5,5
F: nota < 5,0
Substitutiva (apenas de prova): 11 de setembro
18
Sobre a monografia/projeto
Pode ser elaborado por grupos de obrigatoriamente
3 ou 4 alunos.
O tema deve estar relacionado obrigatoriamente com 
algúm tópico da disciplina, não necessáriamente um tópico 
considerado na ementa da disciplina. Assim, podem ser 
considerados tópicos avanzados de Algoritmos ou Estrutura 
de Dados.
Pode também ser considerado o estudo e implementação 
de um artigo científico (publicado em revista ou evento 
internacional) relacionado a aprendizado de máquina.
19
Como identificar um bom projeto de pesquisa?
20
Como identificar um bom projeto de pesquisa?
21
Como identificar um bom projeto de pesquisa?
22
Como procurar bons artigos acadêmicos?
O que é bom?
23
Como procurar bons artigos acadêmicos?
O que é bom?
24
Como procurar bons artigos acadêmicos?
O que é bom?
25
Como procurar bons artigos acadêmicos?
O que é bom?
26
Como procurar bons artigos acadêmicos?
Publicação 
“nasce”
em 2014
(estado-da-arte)
Passado
Hoje: 2014
27
Como procurar bons artigos acadêmicos?
Publicação 
“nasce”
em 2013
(estado-da-arte)
Passado Futuro imediato?
Hoje: 2014
28
Como procurar bons artigos acadêmicos?
O que é bom?
29
Como procurar bons artigos acadêmicos?
O que é bom?
30
Sobre o Projeto
Até 08/08 deve ser cadastrado em um formulário web (a ser 
definido posteriormente) sobre o tópico a ser considerado.
Informações que devem ser registradas:
Título do projeto/monografia.
Resumo (1 paragrafo, menos de 200 palavras)
Membros do grupo
Deverá ser enviado um relatório sobre o projeto.
Apresentações: ultimas 3 aulas
(sorteio de apresentação)
31
Sobre o Projeto: Relatório
O relatório deverá ser um documento simples, sendo limitado 
por 20 páginas.
O relatório deverá conter (idealmente) as seguintes seções:
Título (folha de rosto)
Resumo
Objetivo
Estado-da-arte
Metodologia
Resultados
Conclusões / considerações finais
32
Sobre o Projeto: Apresentação
A apresentação será realizada por um membro do grupo, 
selecionado de forma aleatória, no mesmo dia da 
apresentação.
Tempo: 15-20 minutos (+ 5min de perguntas)
A apresentação será avaliada também pelos pares
Nota do projeto: 
70% ← relatório
30% ← apresentação (60% turma , 40 % professor)
Considerado os quartis 2 e 3.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32