Embed Size (px)
Citation preview
LNCC
GA-024: Ciência da Computação – Estruturas de Dados e Aplicações
Antônio Tadeu A. Gomes, D.Sc.
[email protected] http://wiki.martin.lncc.br/atagomes-cursos-lncc-ga024
Sala 2C-01
LNCC
Objetivos do curso l Apresentar as principais técnicas de projeto e
codificação de estruturas de dados
l Induzir uso de estruturas de dados em problemas práticos na área de computação científica
l Analisar desempenho das estruturas de dados considerando complexidade de tempo e espaço l GA-026
l Exercitar uso de estruturas de dados na prática
- Linguagem ANSI C como base
LNCC
Ementa do curso (I)
l Parte 0: Fundamentos - Algoritmos, estruturas de dados, arquitetura e programas - Tipos abstratos de dados - Alguns paradigmas básicos de projeto de algoritmos
l Parte 1: Estruturas de dados elementares
- Matrizes (incluindo matrizes esparsas) - Listas ligadas - Pilhas e filas - Cadeias de caracteres
LNCC
Ementa do curso (II)
l Parte 2: Estruturas de dados para pesquisa em memória primária
- Pesquisa sequencial e binária - Árvores binárias - Árvores Trie e Patricia - Tabelas de dispersão (hash)
l Parte 3: Estruturas de dados para pesquisa em
memória secundária - Acesso sequencial indexado - Árvores B e B*
LNCC
Ementa do curso (III)
l Parte 4: Grafos (GA-054) - Formas de representação - Busca em largura e profundidade - Alguns problemas clássicos em grafos
LNCC
Avaliação
l Trabalhos ao longo do período - Implementações em ANSI C
l Prova teórica ao final do período
LNCC
Bibliografia l Rangel Neto, J. L. M.; Cerqueira, R. F. de G.; Celes Filho, W. (2004) Introdução a
Estrutura de Dados – com Técnicas de Programação em C, Campus. l Ziviani, N. (2007) Projeto de Algoritmos – com Implementações em Java e C++,
Thomson.
l Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. & Stein, C. (2001) Introduction to Algorithms, Second Edition, MIT Press.
l Szwarcfiter, J. L.; Markenzon, L. (1994) Estruturas de dados e seus algoritmos, Livros Tecnicos e Científicos.
l Knuth, D. E. (1997) The Art of Computer Programming, Vol 1, Fundamental Algorithms, Third Edition, Addison Wesley.
l Knuth, D. E. (1998) The Art of Computer Programming, Vol 3, Sort and Searching, Second Edition, Addison Wesley.
l Barret, R.; Berry, M., Chan, T.F.; Demmel, J.; Donato, J.M.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; Van der Vorst, H. (2006). Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM books.
LNCC
Sobre estes slides
l Parte dos slides é baseada em slides de cursos de Estrutura de Dados da PUC-Rio e da UFMG:
- http://www.inf.puc-rio.br/~inf1620/
- http://homepages.dcc.ufmg.br/~meira/aeds2/
- http://www2.dcc.ufmg.br/livros/algoritmos-java/transparencias.php
LNCC
Parte 0: Introdução GA-024
Antônio Tadeu A. Gomes, D.Sc.
[email protected] http://wiki.martin.lncc.br/atagomes-cursos-lncc-ga024
Sala 2C-01
LNCC
Introdução
l Algoritmos, estruturas de dados, arquitetura e programas
l Tipos abstratos de dados
l Alguns paradigmas básicos de projeto
LNCC
Algoritmos, estruturas de dados, arquitetura e programas (I)
l Algoritmo: sequência de ações executáveis (possivelmente abstratas) para a obtenção de uma solução para um problema
l Estrutura de dados: conjunto de dados que representam a situação real associada ao problema
- Representação dos dados: determinada, entre outros fatores, pelas operações a serem realizadas por um algoritmo sobre esses dados
LNCC
Algoritmos, estruturas de dados, arquitetura e programas (II)
l Programas: formulações concretas de algoritmos e representações dos dados em uma linguagem de programação
l Arquitetura: abstração de programas como composições de elementos e das interações entre esses elementos l GA-031
Mastercontrol
input circularshifter alphabetizer output
Array ofcharacters Word index Alphabetized
index
Conjuntode linhas
Índicepermutado
setchar(l, w, c, ch
)
numw
ords( l )
getchar( l, w, c )
getcschar( s, w, c )
cssetup()
ith( i )
alph()
inputoutput
Mastercontrol
Line storage Circular shifter Alphabetizer
Conjuntode linhas Índice
permutado
LNCC
Tipos abstratos de dados (I) l Tipos básicos: inteiro, booleano, caracter, ponto
flutuante...
l Tipos estruturados: registros, vetores, uniões, enumerações...
- Construídos a partir de tipos básicos ou de outros tipos estruturados
l Tipos abstratos de dados (TADs): estilo arquitetural para modelos de dados acompanhados de operações definidas sobre os mesmos
- Representação de um modelo realizada mediante uma estrutura de dados (de tipo básico ou estruturado)
LNCC
Tipos abstratos de dados (II)
l Ex.: “Lista” - “Criar uma lista vazia” - “Obter primeiro elemento da lista” - “Inserir elemento na lista”
l Vantagens de TADs:
- Manutenção e reutilização de código - Abstração
l Para utilizar um TAD é necessário conhecer a sua funcionalidade (interface), mas não a sua forma de implementação
- Ex.: Lista implementada como um vetor de registros
LNCC
Tipos abstratos de dados (III)
l A interface de um TAD em uma linguagem de programação é composta:
- pela identificação do tipo l Ex.: “List”
- pelas assinaturas das operações l Ex.: “create” l Ex.: “getFirstElement” l Ex.: “insertElement”
l A implementação de um TAD define:
- A representação de dados para seu modelo - O código das operações definidas na sua interface
LNCC
Tipos abstratos de dados (IV) l Ex.: TAD “Point” em C
- Modelo de um ponto no R2
l Tipo registro “Point” (alocado dinamicamente em memória) com 2 campos “x” e “y” de tipo ponto flutuante
- Operações: l Point* point_create(float,float) l void point_destroy(Point*) l point_get(Point*,float*,float*) l point_set(Point*,float,float) l float point_distance(Point*,Point*)
struct point { float x; float y; } typedef struct point Point; Point* point_create(float x, float y) { Point* p = (Point*) malloc(sizeof(Point)); if (p == NULL) { printf("Memória insuficiente!\n"); exit(1); } p->x = x; p->y = y; return p; } void point_set(Point *p, float x, float y){...} ...
Notem convenção!
LNCC
Tipos abstratos de dados (V) l Exemplo de aplicação:
- Para compilar
(usando compilador Gnu C):
l Problemas com a solução: - Encapsulamento ruim
arquivo point.c: #include <stdio.h> #include <stdlib.h> ... /* definições do TAD “Point” int main (void) { float x, y; Point* p = point_create(2.0,1.0); Point* q = point_create(3.4,2.1); float d = point_distance(p,q); printf("Distância entre pontos: %f\n",d); point_destroy(q); point_destroy(p); return 0; }
> gcc -c point.c -o point.o > gcc -o point point.o
LNCC
Tipos abstratos de dados (VI)
l Módulos e compilação em separado em C:
- Módulo: arquivo com funções que representam apenas parte da implementação de um programa completo
- Arquivo objeto: resultado da compilação de um módulo l geralmente com extensão .o ou .obj
- Ligador (estático): une todos os arquivos objeto em um
único arquivo executável
LNCC
Tipos abstratos de dados (VII)
l Interface de um TAD em C usando um módulo:
- Arquivo contendo: l os protótipos (assinaturas) das funções oferecidas pelo
módulo l os nomes dos tipos de dados exportados pelo módulo
- Em geral possui:
l nome igual ao do módulo ao qual está associado l extensão de arquivo “.h”
LNCC
Tipos abstratos de dados (VIII)
l Ex.: interface do TAD “Point” em C Arquivo point.h: /**** Tipo exportado ****/ typedef struct point Point; /**** Funções exportadas ****/ /* Aloca e retorna um ponto com coordenadas (x,y) */ Point* point_create(float x, float y); /* Libera a memória de um ponto previamente criado */ void point_destroy(Point* p); /* Retorna os valores das coordenadas de um ponto */ void point_get(Point* p, float* x, float* y); /* Atribui novos valores às coordenadas de um ponto */ void point_set(Point* p, float x, float y); /* Retorna a distância entre dois pontos */ float point_distance(Point* p1, Point* p2);
LNCC
Tipos abstratos de dados (IX) l Exemplo (revisto) de aplicação:
- Onde está a
implementação?
arquivo main.c: #include <stdio.h> #include <stdlib.h> #include “point.h” int main (void) { float x, y; Point* p = point_create(2.0,1.0); Point* q = point_create(3.4,2.1); float d = point_distance(p,q); printf("Distância entre pontos: %f\n",d); point_destroy(q); point_destroy(p); return 0; }
LNCC
Tipos abstratos de dados (X)
l Implementação de um TAD em C usando módulo
- Arquivo contendo: l as implementações das operações oferecidas pelo TAD,
conforme definido na sua interface (arquivo “.h”) l a definição dos tipos de dados associados ao TAD
- Devem ser visíveis apenas dentro do módulo l as variáveis globais e funções auxiliares
- Devem ser declaradas como estáticas - Também devem ser visíveis apenas dentro do módulo
- Em geral possui:
l extensão de arquivo “.c”
LNCC
Tipos abstratos de dados (XI)
l Para compilar o módulo:
l Para compilar a aplicação:
l Para ligar a aplicação ao módulo:
Arquivo point.c: struct point { float x; float y; } Point* point_create(float x, float y) { Point* p = (Point*) malloc(sizeof(Point)); if (p == NULL) { printf("Memória insuficiente!\n"); exit(1); } p->x = x; p->y = y; return p; } void point_set(Point *p, float x, float y){...} ...
> gcc -c point.c -o point.o
> gcc -c main.c -o main.o
> gcc -o point main.o point.o
LNCC
Tipos abstratos de dados (XII) l Note que, na implementação do TAD “Point” em C:
- O módulo referencia a interface (#include “point.h”) l Garante que as funções implementadas correspondem às
funções da interface - Compilador verifica se os parâmetros das funções
implementadas equivalem aos parâmetros dos protótipos - Os módulos e aplicações que utilizarem esse TAD:
l não poderão acessar diretamente os campos do tipo de dados definido pelo registro “point”
l só terão acesso aos dados mantidos por ele através das funções exportadas em sua interface
- Novos TADs podem ser definidos a partir desse TAD, sem comprometer o seu encapsulamento
l Ex.: TAD “Circle”
LNCC
Tipos abstratos de dados (XIII)
l TADs em C++ - Structs de C com semântica adicional - Classes (unidades de encapsulamento)
LNCC
Paradigmas básicos de projeto (I)
l Recursividade
l Tentativa e erro
l Divisão e conquista
LNCC
Paradigmas básicos de projeto (II) l Recursividade:
- Operação chama a si mesmo consecutivamente (direta ou indiretamente), até um critério de parada
- Permite uma descrição mais clara e concisa de algoritmos: l cujos problemas são recursivos por natureza
- Ex.: números fatoriais l cujas estruturas de dados associadas são recursivas
- Ex.: busca em árvores - Algoritmos recursivos podem ser expressos na forma:
- Se um valor numérico for usado como critério de parada, esses algoritmos podem ser expressos mais concretamente como:
P => if B then ρ[Si, P]
P(n) => if n>0 then ρ[Sn, P(n-1)]
LNCC
Paradigmas básicos de projeto (III) l Recursividade é comumente usada em conjunto com outras
técnicas (ex.: tentativa e erro, divisão e conquista) l Quando não usar recursividade:
- Quando o algoritmo puder ser facilmente caracterizado como uma iteração
- Iterações geram códigos em geral menos sucintos (ou claros), porém mais eficientes
l Implementação de chamadas de funções nas linguagens de programação recorre a empilhamento de parâmetros
l Um resultado computado anteriormente pelo algoritmo pode ser usado diversas vezes nesse algoritmo
LNCC
Paradigmas básicos de projeto (IV)
l Ex.: números de Fibonacci - 0, 1, 1, 2, 3, 5, 8, 13... - Qual o n-ésimo número
da série?
- Versão recursiva:
- Versão não recursiva:
- Comparação (estimativa):
int fibRec( int n ) { if (n<2) return n; else return fibRec(n-1)+fibRec(n-2); }
int fibIter( int n ) { int i=1; int f=0; for(int k=1; k<=n; k++) { f+=i; /* número corrente */ i=f-i; /* número anterior */ } return f; }
LNCC
Paradigmas básicos de projeto (V) l Algoritmos tentativa e erro (backtracking)
- Objetivo: chegar a uma solução final, se existir - Estratégia:
l Decompor uma tarefa pai em um número finito de tarefas filhas parciais
l Cada tarefa filha pode ser decomposta, como sua tarefa pai, em novas tarefas (geralmente de modo recursivo), construindo assim uma árvore de tarefas
- Caso uma tarefa não chegue a uma solução final e não possa ser decomposta, ela pode ser retirada do conjunto de subtarefas em processamento
LNCC
Paradigmas básicos de projeto (VI)
l Problemas com algoritmos de tentativa e erro - Possibilidade de explosão no número de tarefas
l Solução: uso de algoritmos aproximados ou
heurísticas
LNCC
Paradigmas básicos de projeto (VII)
l Ex.: passeio do cavalo no xadrez - Dado um tabuleiro n X n, encontrar, a partir de uma
posição inicial (xo,yo) no tabuleiro, um passeio do cavalo com n2-1 movimentos, tal que todos os pontos do tabuleiro são visitados uma única vez
- Pseudo-algoritmo:
- Algoritmo em C++: [Ziviani, 2007, págs. 429-430]
void tenta ( ) { inicializa seleção de movimentos; do { seleciona próximo candidato ao movimento; if (aceitável ) { registra movimento; if ( tabuleiro não está cheio) { tenta novo movimento ; / / Chamada recursiva para tenta() if (não sucedido) apaga registro anterior ; } } } while (movimento não sucedido e não acabaram candidatos a movimento) ; }
LNCC
Paradigmas básicos de projeto (VIII)
l Algoritmos divisão e conquista
- Estratégia: l Dividir o problema a ser resolvido em subproblemas menores
(de mesmo tamanho/complexidade)
l Encontrar soluções para esses subproblemas (possivelmente redividindo esses subproblemas, recursivamente)
l Combinar as soluções para os subproblemas em uma solução global
LNCC
Paradigmas básicos de projeto (IX) l Ex.: encontrar
simultaneamente o maior e o menor elemento de um vetor de inteiros
l Algoritmo em C++: [Ziviani, 2007, págs. 430-431]
void maxMin( int* min, int* max, int* v, int linf, int lsup) { if (lsup - linf <= 1) { if(v[linf] < v[lsup]) { *max = v[lsup]; *min = v[linf]; } else { *max = v[linf]; *min = v[lsup]; } } else { int meio = (linf+lsup)/2; maxMin(min, max, v, linf, meio); int max1 = *max; int min1 = *min; maxMin(min, max, v, meio+1, lsup); int max2 = *max; int min2 = *min; if (max1 > max2) *max = max1; else *max = max2; if (min1 < min2) *min = min1; else *min = min2; } }
