Aula01-Introducao

Prévia do material em texto

ì
Iniciando …
INF 01203 – Estruturas de Dados
INF01203 
Estruturas de Dados
Apresentação e Contato
ì Renata Galante
ì Email: galante@inf.ufrgs.br
ì Web: www.inf.ufrgs.br/~galante
ì Sala: 205 – prédio 43.425
ì Fone: 3308 7746
renata.galante.1 @renatagalante@rmgalante
mailto:galante@inf.ufrgs.br
http://www.inf.ufrgs.br/~galante
Apresentação e Contato
ì Renata Galante (formação)
ì Londrina – PR
ì Graduação
ì UFRGS
ì Mestrado 1998
ì Doutorado 2003
ì Professor 2005
Apresentação e Contato
ì Renata Galante (atuação UFRGS)
ì Disciplinas na Graduação: 
ì INF01203 – Estruturas de Dados 
ì INF01045 – Fundamentos de Bancos de Dados
ì INF01006 – Projeto de Banco de Dados
ì INF01023 – Arquitetura de Desempenho de BD
ì Disciplina na Pós-Graduação
ì Bancos de Dados para Big Data (INF e ADM)
ì Vice-coordenadora da COMGRAD CIC
ì Comissão de Relacionamento Interno
ì Diretora Administrativa da SBC (Sociedade Brasileira da 
SBC)
Agenda
ì Algoritmos X Estruturas de Dados
ì Assunto da disciplina
ì Organização, metodologia e critérios de avaliação
ì Exercício para entregar
Algoritmos X Estruturas de Dados
Algoritmos
ì INF01203 B :: entrada
ì nome da pessoa mais alta
Algoritmos
1. Pegue a altura da 1a. Pessoa, esta é a máxima no 
momento
2. Percorra cada uma das próximas pessoas e faça:
1. Pegue a altura da pessoa, esta é altura atual
2. Compare altura atual com a máxima
3. Se a altura atual foi maior que a máxima, então faça a 
altura atual se tornar a máxima
Algoritmos
Problema
Implementação
O que deve ser feito
Como executar
Tipos de Dados
ì Inteiro (int)
ì Real (float)
ì Caracter (char)
ì Lógico (bool)
ì Usados para resolver problemas:
ì Variáveis e operadores
ì Controle de fluxo
ì Funções
Tipos de Dados
ì Servem para armazenar conjuntos de dados 
(complexos) em memória principal
ì Vetores ( float v[100] ) 
ì Matrizes (float m[50][40])
ì Cadeia de Caracteres ( char cidade[80] )
ì Estrutura 
struct ponto { 
float x; 
float y}; 
ì Ponteiros (*)
1. Essa solução é eficiente ? 
1. Pegue a altura da 1a. Pessoa, esta é a máxima no momento
2. Percorra cada uma das próximas pessoas e faça:
1. Pegue a altura da pessoa, esta é altura atual
2. Compare altura atual com a máxima
3. Se a altura atual foi maior que a máxima, então faça a altura atual se tornar a máxima
Algoritmos
1. Essa solução é eficiente ? 
2. Se fosse a fila para entrar na sala de aula?
1. Pegue a altura da 1a. Pessoa, esta é a máxima no momento
2. Percorra cada uma das próximas pessoas e faça:
1. Pegue a altura da pessoa, esta é altura atual
2. Compare altura atual com a máxima
3. Se a altura atual foi maior que a máxima, então faça a altura atual se tornar a máxima
Algoritmos
1. Essa solução é eficiente ? 
2. Se fosse a fila para entrar na sala de aula?
3. Se fosse a fila do RU? 
1. Pegue a altura da 1a. Pessoa, esta é a máxima no momento
2. Percorra cada uma das próximas pessoas e faça:
1. Pegue a altura da pessoa, esta é altura atual
2. Compare altura atual com a máxima
3. Se a altura atual foi maior que a máxima, então faça a altura atual se tornar a máxima
Algoritmos
1. Essa solução é eficiente ? 
2. Se fosse a fila para entrar na sala de aula?
3. Se fosse a fila do RU? 
4. Se fosse uma fila única de matrícula para todos os alunos da UFRGS?
1. Pegue a altura da 1a. Pessoa, esta é a máxima no momento
2. Percorra cada uma das próximas pessoas e faça:
1. Pegue a altura da pessoa, esta é altura atual
2. Compare altura atual com a máxima
3. Se a altura atual foi maior que a máxima, então faça a altura atual se tornar a máxima
Algoritmos
1. Essa solução é eficiente ? 
2. Se fosse a fila para entrar na sala de aula?
3. Se fosse a fila do RU? 
4. Se fosse uma fila única de matrícula para todos os alunos da UFRGS?
5. E se as pessoas estivessem organizadas na fila em ordem alfabética?
1. Pegue a altura da 1a. Pessoa, esta é a máxima no momento
2. Percorra cada uma das próximas pessoas e faça:
1. Pegue a altura da pessoa, esta é altura atual
2. Compare altura atual com a máxima
3. Se a altura atual foi maior que a máxima, então faça a altura atual se tornar a máxima
Algoritmos
1. Essa solução é eficiente ? 
2. Se fosse a fila para entrar na sala de aula?
3. Se fosse a fila do RU? 
4. Se fosse uma fila única de matrícula para todos os alunos da UFRGS?
5. E se as pessoas estivessem organizadas na fila em ordem alfabética?
6. E se as pessoas já estivessem organizadas na fila por ordem de altura? 
1. Pegue a altura da 1a. Pessoa, esta é a máxima no momento
2. Percorra cada uma das próximas pessoas e faça:
1. Pegue a altura da pessoa, esta é altura atual
2. Compare altura atual com a máxima
3. Se a altura atual foi maior que a máxima, então faça a altura atual se tornar a máxima
Algoritmos
Estruturas de Dados
ìQuais são os problemas que 
ED resolve?
1 – Representação dos Dados
Tipos de Dados
ì Inteiro (int)
ì Real (float)
ì Caracter (char)
ì Lógico (bool)
ì Usados para resolver problemas:
ì Variáveis e operadores
ì Controle de fluxo
ì Funções
ì Servem para armazenar conjuntos de dados 
(complexos) em memória principal
ì Vetores ( float v[100] ) 
ì Matrizes (float m[50][40])
ì Cadeia de Caracteres ( char cidade[80] )
ì Estrutura 
struct ponto { 
float x; 
float y}; 
ì Ponteiros (*)
Tipos de Dados
2 – Operações
2 – Operações
ì Insere Post
ì Insere Amigo
ì Remove Amigo
ì Insere Foto
ì Remove Foto
ì Altera Dados Pessoais
3 – Ordem dos Dados
Timeline Facebook
3 – Ordem dos Dados
3 – Ordem dos Dados
3 – Ordem dos Dados
3 – Ordem dos Dados
3 – Ordem dos Dados
3 – Ordem dos Dados
3 – Ordem dos Dados
4– Eficiência na Implementação
2,27 bilhões de 
usuários
ATIVOS/Mês
1,5 bilhão
acesso diário
130 milhões
usuários ATIVOS 
no Brasil
Dados Jan/2019
1o. India 
2o. USA 
3o. Brasil
4– Eficiência na Implementação
EX1: Meus amigos 
EX2: Usuários do Brasil
EX3: todos os usuários
5 – Armazenamento de Dados
2,27 bilhões de 
usuários
ATIVOS/Mês
1,5 bilhão
acesso diário
130 milhões
usuários ATIVOS 
no Brasil
Dados Jan/2019
1o. India 
2o. USA 
3o. Brasil
As estruturas de dados Estáticas não dão suporte para as operações
de inserir/remover elementos dinamicamente na estrutura de dados.
Estruturas
de Dados 
ESTÁTICAS
Tipos de Dados
ì Servem para armazenar conjuntos de dados 
(complexos) em memória principal
ì Vetores ( float v[100] ) 
ì Matrizes (float m[50][40])
ì Cadeia de Caracteres ( char cidade[80] )
ì Estrutura 
struct ponto { 
float x; 
float y};
ì Ponteiros (*)
Tipos Dados X Estruturas de Dados
ì Tipos Estruturados (ESTÁTICO)
ì Construção de tipos
ì Fornecido pelas linguagens de programação
ì Estruturas de Dados (DINÂMICO)
ì Organização conceitual dos dados
ì Reflete um relacionamento lógico entre os dados 
ì No problema considerado
ì Possui operacões associadas
37
Assunto da Disciplina
Objetivo da Disciplina
ì Estudo das principais técnicas de 
representação e manipulação de dados 
na MEMÓRIA PRINCIPAL
OperaçõesModelos
Modelagem de Dados 
1.Identificação dos Dados
• Abstração do mundo real
2. Modelo Lógico
• Relacionamento entre os dados
• DADOS + OPERAÇÕES
3. Modelo Físico
• Alternativas de Implementação
• ALGORITMOS PARA AS OPERAÇÕES
Exemplo 01: Lista de Frequência
Exemplo 01: Lista de Frequência
1 – Identificação dos Dados
ì Abstração
ì Omitir detalhes irrelevantes
ì Adaptar e guardar detalhes úteis
Realidade
Dados
Abstração
Exemplo 01: Lista de Frequência
Aluno
Typedef aluno {
int cartao;
char nome[80];
int ano_ingresso;
char curso[40];
char conceito;
}TAluno;
2 – Modelo Lógico
ì Identificar as relações Lógicas existentes entre os 
dados
ì Identificar as operações entre os dados 
Ordem linear
Pai / filhos
... 
Criação
Manutenção
Inserção
Remoção
Alteração
Consulta
3 – Modelo Físico
ì Escolher a representação física para implementação 
em uma linguagem de programação
ì Preservar as relações lógicas
ì Implementar operações atravésde funções simples e 
eficientes
As operações definidas sobre os dados 
influenciam decisivamente na escolha 
da representação física a ser adotada
Estruturas de Dados
Listas
Árvores
Grafos
Estruturas de Dados
ì Para cada ED:
ì Formas de organizar (estruturar os dados)
ì Algoritmos e manipulação (operações)
ì Opções de armazenamento
Lista
ì Relação de Ordem
ì Exemplos de Aplicações
Lista
ì Relação de Ordem
ì Exemplos de Aplicações
SEQUENCIAL
LINEAR
Lista
ì Relação de Ordem
ì Exemplos de Aplicações
ì Fila de banco
ì Cadastro de funcionário
SEQUENCIAL
LINEAR
Árvore
ì Relação de Ordem
ì Exemplos de Aplicações
Árvore
ì Relação de Ordem
ì Exemplos de Aplicações
HIERARQUIA
Árvore
ì Relação de Ordem
ì Exemplos de Aplicações
ì Árvore genealógica
ì Organograma de funções
ì Árvore Binária de Busca (ABP)
ì Precedência de Operadores (calculadora)
HIERARQUIA
GRAFO
ì Relação de Ordem
ì Exemplos de Aplicações
GRAFO
ì Relação de Ordem
ì Exemplos de Aplicações
LIVRE
GRAFO
ì Relação de Ordem
ì Exemplos de Aplicações
ì Construção de Estradas
ì Redes Sociais
LIVRE
57
Organização, Metodologia e Avaliação
Posicionamento no Curso
1ª Etapa
INF01202
INF 05008
INF01203 INF 01124 INF 01145
2ª Etapa 3ª Etapa 4ª Etapa
INF 05512
CIC e ECP
CIC e ECP ECP
INF 01003
INF 01006
Ciência da Computação
ì Sistemas Operacionais
ì Controle de processos (fila de espera por recurso)
ì Compiladores
ì Validação das operações de uma LP (pilha de instruções)
ì Banco de Dados
ì Resultados de consultas (listas de dados)
ì Indexação de arquivos de dados (árvores)
ì Computação Gráfica
ì Manipulação de imagens (matrizes)
ì Simulação de objetos hierarquivos (árvores)
Pré-Requisitos
ì Programação básica
ì Incluindo programacão fluente usando funções, passagem de parâmetros
ì Variáveis simples
ì Int, float, char, boolean
ì Variáveis Estruturadas
ì Array
ì Struct
ì ARQUIVO (para o trabalho final)
ì RECURSIVIDADE
ì PONTEIRO
Moodle do INF
TUDO no MOODLE
• Material
• Envio dos trabalhos
• E-mails 
Planilha Online (google drive)
Chamada no final da aula 
(antes dos exercícios)
Se precisar sair antes,
seja discreto J
Aulas Teóricas
ì Slides no moodle
ì Metade do período – aula teórica
ì Metade do período – exercícios
ì Questionários no moodle
Aulas Práticas
ì Implementação de uma aplicação (ou parte) durante
a aula
ì Mostrar para o professor no final da aula
ì Submeter no moodle
7 ou 8 labs
Provas
ì Prova teórica – em sala de aula
ì Individual
ì 25% - Prova 01 (listas)
ì 25% - Prova 02 (árvores)
ì 25% - Prova 03 (grafos)
ì Cola Auxiliar
ì A4 frente/verso (manuscrita)
ì Entregar junto com a prova
Exercícios
ì Laboratório
ì Implementação de aplicações/funções
ì Individual ou em duplas
ì PESO 2
ì Exercícios de Aula
ì Exercícios entregues durante a aula
ì Duplas ou trios
ì PESO 1
ì Questionários
ì 5 ou 10 questões sobre o fechamento de um assunto
ì Individual ou em duplas
ì PESO 1
Trabalho Final
ì Implementacão de uma aplicacão real
ì Proposta de uma ou mais estruturas de dados para
solucionar o problema
ì Trabalho em duplas
15% da NOTA
Média Final
ì 25% Prova 01
ì 25% Prova 02
ì 25% Prova 03
ì 10% Exercícios
ì 15% Trabalho Final
Recuperação
Prova teórica envolvendo TODO conteúdo
Troca pela menor nota de prova
*** trabalhos não são recuperados
Bibliografia
1. Estruturas de Dados. Nina Edelweiss, 
Renata Galante, Editora Bookman – Série de 
Livros Didáticos Informática UFRGS, 2009, 
Primeira Edição. (Livro texto da disciplina 
para a parte de listas e árvores. Boa 
cobertura, tanto em abrangência quanto em 
profundidade)
3. Grafos: Teoria, Modelos, Algoritmos. Paulo 
Oswaldo Boaventura Netto, Editora LTC -
Livros Técnicos e Científicos, 1994, Segunda 
Segunda edição revisada e ampliada. (Livro 
texto da disciplina para a parte de grafos)
5. Estruturas de Dados e Algoritmos em Java. 
Michael T. Goodrich, Roberto Tamassia, 
Editora Bookman, 2002 , segunda edição. 
(Exemplos de implementações de listas, 
árvores e grafos)
Exercícios
ì Para cada aplicação
( ) lista
( ) árvore
( ) grafo
Ordem dos dados: 
Operações:
ì insere
ì remove
ì consulta
Últimas
Notícias
Resultados domingo, 11/08/2019
Libertadores 2019 – Tabela de Jogos
Resultados domingo, 11/08/19
Resultados domingo, 11/08/19
Libertadores 2019 – Classificação por grupo
Links da Web
Links da Web
Links da Web
Links da Web
Sistemas de Arquivos
Avançar/Voltar Navegadores da Web
Moodle: upload de trabalhos
Tráfego Aéreo ao vivo
Twitter :: Postagens
Twitter :: Seguidos e Seguidores
Bom Semestre!! Bom Trabalho!!