1

Classificação e Pesquisa de Dados

Aula 01Apresentação da Disciplina; Introdução à

Classificação; Definições

UFRGS INF01124

Histórico do material

1. Preparado inicialmente pelo prof.Paulo Alberto Azeredo em forma textual

2. Adaptado para apresentação pela profa. Nina Edelweiss3. Transformado para PowerPoint e aperfeiçoado pela Profa.

Maria aparecida M. Souto4. Revisado e reformulado pelos profs. José Palazzo M. de

Oliveira, Daniela Remião de Macedo, Manuel Menezes de Oliveira Neto e José Valdeni de Lima

Objetivos da disciplina

Capacitar o aluno para seleção e análise de:n Algoritmos para classificação de dadosn Algoritmos para pesquisa de dados n Técnicas de organização e de compactação

de arquivos

Estruturas de dados consideradas n em memória vs. em disco

Qual é a diferença?

Em memória n acesso é direto às estruturas de dados (qualquer

palavra da memória é diretamente acessível).

Em disco n é preciso buscar os elementos de dados de um

dispositivo através de ações mecânicas (considerações de tempo de acesso).

Devemos considerar as diferenças quando da especificação dos algoritmos

Súmula

1. Métodos de Classificação de Dados

2. Introdução à Análise de Complexidade de Algoritmos

3. Métodos de Armazenamento e Pesquisa de Dados em Tabelas

4. Técnicas de Organização de Arquivos

5. Técnicas de Compactação de Arquivos

Bibliografia

AZEREDO, P.A. Métodos de Classificação de Dados e Análise de suas Complexidades. Editora Campus, RJ, 1995.

KNUTH, D.: The Art of Computer Programming: Sorting and Searching. Vol. 2. Addison-Wesley, Reading, Mass, 1973.

CORMEN, T., LEISERSON, C. E RIVEST, R.: Introduction to Algorithms. The MIT Press. Cambridge, Massachusetts, 1990.

SANTOS, C.S. e AZEREDO, P. A. Tabelas: Organização e Pesquisa. Série Livros Didáticos, Editora Sagra Luzzato, Porto Alegre, 2001.

VELOSO, P.A.S; SANTOS, C.S; AZEREDO, P.A; FURTADO, A.L.: Estruturas de Dados. Editora Campus, Rio de Janeiro, 1985.

FURTADO, A.L. e SANTOS, C.S. dos. Organização de Banco de Dados. Editora Campus, Rio de Janeiro, 1988.

SZWARCFITER, Jayme L. e MARKENZON, Lilian. Estrutura de Dados e seus algoritmos. Rio de Janeiro: LTC, 1994.

2

Avaliação

São realizadas duas provas (P1 e P2), um trabalho prático (T1). É considerada a participação em aula, a contribuição individual e a presença.A média geral (MG) é a média ponderada dos graus obtidos na provas e trabalho acima referidos. 0,0 = MG < 4,0 → conceito D (reprovado).4,0 = MG < 6,0 → sem conceito (recuperação).6,0 = MG < 7,5 → conceito C (aprovado).7,5 = MG < 9,0 → conceito B (aprovado).9,0 = MG = 10,0 → conceito A (aprovado).

Avaliação - observações

1. Somente serão calculadas as médias gerais daqueles alunos que tiverem, ao longo do semestre, obtido um índice de freqüência às aulas igual ou superior a 75% das aulas previstas. Aos que não satisfizerem este requisito, será atribuído o conceito FF (Falta de Freqüência).

2. Para poder realizar a prova de recuperação, o aluno deve ter realizado as duas provas (P1 e P2), ter entregue o trabalho prático T1, ter 70% de participação no ROODA e ter apresentado o seminário final. Os que não se enquadrarem nesta situação receberão conceito D.

Avaliação - recuperação

Não há recuperação das provas P1 e P2 por não comparecimento, exceto nos casos previstos na legislação (saúde, parto, serviço militar, convocação judicial, luto etc, devidamente comprovados).

Avaliação - recuperação

Os alunos cujas médias gerais forem inferiores a 6,0 (seis) e maiores ou iguais a 4,0 (quatro), tenha pelo menos uma das notas da prova igual ou superior a 6,0 e que satisfizerem as condições 1 e 2 acima, poderão prestar prova de recuperação, a qual versará sobre toda a matéria da disciplina.

Serão considerados aprovados na recuperação os alunos que obtiverem um aproveitamento de no mínimo 60 % da prova. A estes será atribuído o conceito C. Aos demais, o conceito D.

Classificação de Dados

UFRGS INF01124

Processo de organizar ítens em ordem(de)crescente, segundo algum critério

Também chamado de ordenação

Aplicações de Sortingn Preparação de dados para facilitar pesquisas futuras

w Exemplo: dicionários e listas telefônicasn Agrupar ítens que apresentam mesmos valores

w Para eliminação de elementos repetidosn Batimento entre ítens presentes em mais de um arquivo

w Para combinação de dados presentes nos vários arquivosw Para consolidação dos vários arquivos em um único

Classificação (Sorting)

3

Sejam R1, R2, …, RN , N ítens (chamados registros)

Cada registro Ri, é formado por uma chave Ci e poroutros dados ditos satélites

A ordenação dos registros é feita definindo-se umarelação de ordem “<“ sobre os valores das chaves

O objetivo da ordenação é determinar umapermutação dos índices 1 ≤ i1, i2, …, iN ≤ N das chaves, tal que Ci1 ≤ Ci2 ≤ … ≤ CiN.

Um conjunto de registros é chamado de arquivo

Definições

Uma relação de ordem “<“ (leia-se precede) devesatisfazer as seguintes condições para quaisquervalores a, b e c:

(i) Uma e somente uma das seguintes possibilidades éverdadeira: a < b, a = b ou b < a (lei da tricotomia)

(ii) Se a < b e b < c, então a < c (transitividade)

As propriedades (i) e (ii) definem o conceito de ordem linear ou ordem total

Relação de Ordem

Um algoritmo de classificação é dito estável, se elepreserva a ordem relativa original dos registros com mesmo valor de chave.

Classificação local: feita sobre a mesma área físicaonde se encontram as chaves (não há necessidadede memória extra).

Algoritmos de ordenação podem ser classificadoscomo internos (todos os registros mantidos em RAM) ou externos.

Mais Definições

Qual a importância prática de algoritmos de classificação estável? Exemplifique.

n Controle de filas de prioridades em sistemas operacionais.

Pergunta

Escreva um algoritmo para classificar um conjuntode 5 números em ordem crescente.

Exercício Formas de Representação do Resultado

n Reorganização Física

n Encadeamento

n Vetor Indireto de Ordenação (VIO) ouíndice

4

Classificação de Dadoscom Reorganização Física

10

19

13

12

7

1

2

3

4

5

chave dados satélites

Antes da classificação

7

10

12

13

19

1

2

3

4

5

chave dados satélites

Após a classificação

10

19

13

12

7

1

2

3

4

5

chave dados satélites

10

19

13

12

7

1

2

3

4

5

0

Classificação de Dadosatravés de Encadeamento

5

cabeça da lista

Antes da classificação

chave dados satélites

1

4

3

2

Após a classificação

n Somente acesso sequencial aos registrosordenados!

10

19

13

12

7

1

2

3

4

5

chave dados satélites chave apontador

Classificação de Dadospor Vetor Indireto de Ordenação (VIO)

1

2

3

4

5

5

1

4

3

2

7

10

12

13

19

n Acesso sequencial, por pesquisa binária e direto, mas sempre por via indireta

VIOA Memória tem tempo de acesso constante e igual para cada posição (hoje de 5 a 70 ns)O Disco tem tempo de acesso variável e dependente da região onde estão localizados os dados (hoje de 5 a 15 ms)Há diferença de duas ordens de grandeza entre o acesso a memória e o acesso ao discoMatrizes (arrays) em memória e arquivos em disco

Memória e disco

Para Comparação:

Milesegundos 10-3 (ms) <- DISCOMicrosegundos 10-6 (us ou letra grega micro+s). Nanosecond 10-9 (ns or nsec) <- RAMPicosegundos 10-12 (ps)Femtosegundos 10-15 <- Tecnologia laser Attosegundos 10-18 < - Pesquisa com photon

Obs: 1 ps está para 1s assim como 1s está para 315 séculos.

Exemplo de uma oferta

Enlarge ImageLaCie Big Disk Extreme 1 TB Hard DriveExternal - Type: Standard - Interface Type: USB, Firewire, USB 2.0 - 7200 Rpm -Access Time: 10 msPrice Range: $383 to $698