Slides de Estrutura de Dados e Arquivos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Estrutura de Dados e Arquivos
Unidade 1
Introdução
Estrutura do curso
	Conteúdo da disciplina:
		ftp://arthur@materias.ucb.br 
	Pasta EDA
	Para mensagens e pedidos enviar email para:
		arthur@ucb.br
	Para exercícios enviar para:
		Nossa turma no Moodle
	Plano de ensino (está no FTP e no Moodle)
Unidade 1
	Reflexão sobre a solução de problemas
	Estudo de caso
	Tipos de dados abstratos / concretos
	Abstração / implementação
	Objetivos da disciplina
	Representações dos dados
Reflexão sobre a solução de problemas
	A disciplina de EDA, juntamente com as disciplinas de programação, constituem a base da formação de um profissional de TI
	Se a base é fraca...
	Muito além do enfoque conceitual ou teórico, o que o aluno deve buscar é desenvolver sua capacidade de resolver problemas.
	Resolver problemas em TI é saber raciocinar de forma estruturada, algoritmica. É desenhar uma solução que possa ser implementada em um computador.
Reflexão sobre a solução de problemas
	O “desenho” de uma solução em TI começa pela identificação dos dados a serem manipulados: tipo, estrutura, valores possíveis (mínimo e máximo), distribuição (esparsa ou contínua), quantidade, precisão exigida (casas decimais), etc.
	Uma vez identificados os dados “abstratos”, ou seja, os dados tais como eles se apresentam na realidade, é necessário “traduzi-los” para estruturas de dados que o computador saiba manipular.
	Essa tradução se faz definindo os dados “concretos” e os algoritmos (métodos) que farão com que esses dados concretos de comportem como os dados “reais”.
Reflexão sobre a solução de problemas
	As estruturas de dados e os algoritmos estão intimamente ligados: exemplo loop e vetor
	A arte de programar consiste em desenhar estruturas de dados e algoritmos que se harmonizem, que sejam adequados um ao outro.
	Quem sabe programar bem tem muito mais facilidade em solucionar problemas de mais alto nível em TI em geral (análise de sistemas, bancos de dados, etc).
	Aprender a programar bem só é possível com a prática e muito empenho.
Estudo de caso
	Problema:
		Precisamos escrever um programa que calcule uma série de medidas estatísticas sobre um conjunto de leituras provenientes de um sensor em um equipamento industrial
	O sensor nos transmite os seguintes dados a cada segundo:
	Timestamp (ano, mês, dia, hora, minuto e segundo)
	Temperatura
	Pressão
	O programa vai recalcular a cada segundo a média e o desvio padrão da temperatura e da pressão para um certo período de tempo
	O programa funciona em um dos 3 modos a seguir:
	Calculando as estatísticas para o último minuto, para a última hora ou para o último dia
	O usuário escolhe o modo de execução quando lança a aplicação
	Reflita sobre as estruturas de dados necessárias para construir esse programa
Estudo de caso
	Questões que devem ser colocadas
		Que dados vou precisar armazenar?
	Quais os tipos desses dados?
	Devo usar variáveis atômicas ou estruturas?
	Vou guardar repetições?
	Se sim, quantas instâncias vou precisar guardar?
	Como vou guardar essa repetições?
	Arquivo em disco, vetor em memória?
	Se for em memória como vou alocar espaço?
	Alocação estática ou alocação dinâmica 
Tipos abstratos/concretos
	Exemplo para discussão:
		Biblioteca 
	conjunto ou agrupamento de livros
	Livros possuem uma série de atributos
	‘Conjunto’ e ‘agrupamento’ são tipos de dados abstratos, com suas propriedades e requisitos (regras de negócio)
	Vetor permite implementar o tipo abstrato ‘conjunto’
	Vetor é um tipo de dados concreto
	Existem outros tipos concretos para implementar o mesmo tipo abstrato (ex: arquivo, lista)
Abstração/implementação
	Livros descritos com título, autor e número de páginas é uma abstração da realidade (tipo abstrato), livros têm outras propriedades não consideradas aqui
	Depois da etapa de abstração precisamos ainda implementar o tipo abstrato com um tipo concreto (aqui: registro)
Tipos abstratos/concretos
	Tipo de dados abstrato pode ser visto como:
		conjunto de valores
	série de funções a serem aplicadas sobre os valores (criação, modificação, acesso, etc.)
	Exemplo: ‘livro’
		Conjunto de valores=todos títulos, autores, números de páginas possíveis
	funções para criar um livro, verificar a existência de um livro,etc.
Tipos abstratos/concretos
	Em TI uma série de metodologias são usadas para modelar o mundo real através de tipos abstratos de dados.
	A mais conhecida atualmente é a UML – Universal Modeling Language, baseada em classes e objetos. 
	Outro método bastante popular é o Entidade-Relacionamento usado em bancos de dados.
	A própria matemática é uma ferramenta poderosa de modelagem 
		equações diferenciais são usadas para descrever sistemas físicos,
	A geometria é usada para descrever modelos em 3D
	A estatística e a probabilidade são usadas para criar modelos a partir de dados experimentais.
Objetivos da disciplina
Abstração:
	Conhecer tipos de dados abstratos (modelos) para representar o mundo real, sabendo que classes de problemas eles podem resolver.
Implementação:
	Conhecer implementações (tipos de dados concretos) possíveis dos tipos abstratos com as rotinas necessárias para atuar sobre eles.
Implementação versus Representação
	Muitos tipos de dados concretos já são nativos da própria linguagem de programação usada, outros podem ser obtidos em bibliotecas do tipo da STL (Standard Template Library).
	Obviamente, bibliotecas e tipos nativos devem ser usados na prática.
	Entretanto, dentro do contexto dessa disciplina, queremos ir mais a fundo para entender como esses tipos de dados concretos são implementados e também implementar os mais comuns.
	Esse mergulho no estudo dos tipos de dados concretos dará ao aluno uma compreensão mais sólida sobre programação e permitirá implementar suas próprias estruturas quando necessário. 
Implementação versus Representação
	Por isso é que vamos começar estudando como os dados são efetivamente armazenados e manipulados no computador.
	Para isso precisamos entender a diferença entre como um dado é visto (sua representação) e como ele é implementado no computador.
Representações dos dados
	A unidade básica de informação é o bit
	O bit representa dois estados. Se um dado pode assumir mais de dois valores significa que ele tem mais de um bit de informação.
	Uma cadeia de bits deve ser “interpretada” para que se possa extrair a informação que ela codifica.
	A interpretação se faz definindo o tipo do dado. O tipo do dado deve estar associado a um método de interpretação.
Representações dos dados
	Por exemplo: 
		números inteiros são normalmente representados usando o sistema de numeração binário (potência de 2) 
	uma notação especial é usada para representar os números negativos (complemento de um ou de dois onde o primeiro bit da cadeia indica se o número é positivo ou negativo).
	O método de interpretação define também todas as operações que serão executadas sobre os dados (tais como a soma de dois inteiros).
	As linguagens de programação permitem também que se definam estruturas de dados, onde um registro pode conter diversos dados de diversos tipos nativos.
Representações dos dados
	O conceito de implementação:
		Para o usuário o que importa é manipular o dado, sem se importar com a sua representação binária ou seus métodos de interpretação.
	As linguagens de programação oferecem um conjunto de tipos nativos de dados, que o usuário usa nas declarações e operações (inteiros, reais, strings de caracter,
etc).
	Outros tipos de dados podem ser definidos pelo usuário e devem então ser implementados de alguma forma.
	A definição de um tipo abstrato de dados deve ser feito sem se preocupar com a implementação.
	Essa definição é feita por meio de um conjunto de propriedades lógicas do tipo de dado.
Definição de alto nível e sua implementação
	Vamos analisar alguns casos envolvendo tipos de dados e operações sobre eles:
	z = x + y;
		Embora a operação de soma seja genérica, o compilador vai implementar essa operação em função de seu contexto. Se x, y e z forem inteiros uma soma de inteiros será feita, se forem reais o método de soma será específico para reais, pois suas representações diferem da dos inteiros
	O procedimento básico a seguir será:
	Extrair as sequências de bits localizadas nas variáveis x e y
	Produzir uma terceira sequência de bits que seja a soma dos valores de x e y considerando o seu tipo de representação.
	Armazenar a sequência de bits produzida na posição da variável z
Definição de alto nível e sua implementação
		Note que nesse comando o compilador interpreta x e y sabendo que deve obter o conteúdo da memória indicada por x e y mas interpreta z como sendo a posição onde deve colocar o resultado.
	a[4] = b + c;
		Nesse caso o que muda é que no terceiro passo (armazenamento do resultado) o compilador sabe que tem de usar a posição indicada por a e então avançar 4 posições inteiras (que depende da implementação dos inteiros naquela máquina) para alí colocar o resultado.
Definição de alto nível e sua implementação
	MOVE (origem, dest, compr)
		Considerando que esse comando move um conteúdo de memória de comprimento ‘compr’ da posição ‘origem’ para a posição ‘dest’.
	Os passos da implementação serão:
	Se compr é uma constante (um número), usa esse valor, se for uma varíável lê o seu conteúdo e interpreta como inteiro. 
	Lê o conteúdo da memória começando em origem para obter um número de bytes definido por compr
	Armazena o conteúdo lido no endereço indicado por dest. 
Visão geral sobre a linguagem C
	O uso da linguagem será progressivo e serão fornecidos exemplos e explicações durante todo o curso.
	http://www.portalc.acif.com.br/down.html
	Brian W. Kernighan and Dennis M. Ritchie, C: A linguagem de programação. Rio de Janeiro: Campus, 1986. 206p. 
Visão geral sobre a linguagem C
	Algumas das características do C que levaram a que se tornasse uma das mais populares linguagens de programação, são: 
		Pequeno tamanho da sua definição 
	Subdivisão do código e grande utilização de funções 
	Alguma conversão automática entre tipos de dados (ao contrário do Pascal) 
	Linguagem estruturada 
	Disponibilidade de operadores para programação de baixo nível 
	Utilização fácil e extensa de apontadores para aceder memória, vectores, estruturas e funções 
Visão geral sobre a linguagem C
	Algumas das razões que tornaram o C uma das linguagens predilectas dos programadores profissionais são: 
		A possibilidade de usar construções de alto nível 
	A possibilidade de utilizar operadores de baixo nível 
	A produção de código executável eficiente 
	A disponibilidade de compiladores em praticamente todos os sistemas de computação 
	Neste momento todos os compiladores seguem o standard internacional conhecido por ANSI C (American National Standards Institute). 
  
Visão geral sobre a linguagem C
	A estrutura genérica de um programa em C é a que se apresenta a seguir, podendo alguns dos elementos não existir: 
		Comandos do pré-processador 
	Definições de tipos 
	Protótipos de funções - declaração dos tipos de retorno e dos tipos dos parâmetros das funções 
	Variáveis globais 
	Funções 
	Deverá existir sempre uma função main(). 
Visão geral sobre a linguagem C
	As funções têm a seguinte estrutura: 
	tipo nome_da_funcao(parâmetros) 
{ 
  variáveis locais   
instruções em C 
}
	Assim, o programa: 
	void main(void) 
{ 
  printf("Eu gosto do C\n"); 
}
		contém apenas uma função (a função main(), que é obrigatória), que não retorna nada (void) e que não tem parâmetros (outra vez void). 
	Como instrução da função temos apenas a chamada a printf(), uma função da biblioteca standard que escreve no vídeo. 
Visão geral sobre a linguagem C
	Variáveis
		O C tem pré-definidos os seguintes tipos de dados simples: 
  
Visão geral sobre a linguagem C
	Definição de variáveis globais
		As variáveis globais,  visíveis em todas as funções de um programa, declaram-se fora e antes de todas as funções (só são visíveis a partir do  local da daclaração). 
	Por exemplo: 
	short number, sum; 
int bignumber, bigsum; 
char letter; 
void main(void) 
{ 
}
Visão geral sobre a linguagem C
	O C tem uma palavra chave que permite a definição de novos tipos - typedef. 
	Esses novos tipos declaram-se utilizando a regra: 
	typedef tipo_já_definido novo_tipo;
	Um exemplo muito sismples: 
	typedef float real; 
typedef char letter; 
real sum = 0.0;       /* o mesmo que float */ 
letter ch = 'A';      /* o mesmo que char */
Visão geral sobre a linguagem C
	As funções da biblioteca standard printf() e scanf() permitem escrever no vídeo e ler do teclado, respectivamente, o valor de variáveis. 
	Estas funções têm como primeiro parâmetro uma string especificando o formato e a ordem das variáveis a escrever ou a ler. 
	Seguem-se como parâmetros as próprias variáveis pela ordem especificada. 
	Na string de formatação indica-se o local e o tipo de um valor de variável através do carácter % seguido de uma letra indicadora do tipo. Alguns dos tipos suportados são: 
		%c - char 
	%d - int's 
	%f - float's 
	Um exemplo:     
	printf("Os valores das três variáveis são: %c, %d, %f \n", ch, i, x); 
Visão geral sobre a linguagem C
	A modificação de formatos, pode ocorrer para especificar largura e numero de casas decimais. 
	Assim o modificador é colocado entre o sinal % e o código do formato. 
	Se tivermos %10f informa que o campo terá 10 posições incluindo a parte inteira o ponto e a parte decimal. 
	Se tivermos %12.3f informa que terá 12 posições no total com 3 casas decimais. 
#include <stdio.h> 
void main(void) 
{ 
double item; 
item = 10.12304; 
printf("%f \n", item); 
printf("%5.2f \n", item); 
} 
Produz o resultado: 
10.123040 
10.12