Fundamentos Programação

Prévia do material em texto

FUNDAMENTOS DE PROGRAMAÇÃO
FUNÇÕES E PROCEDIMENTOS
MODULARIZAÇÃO
	É muito difícil manter um código quando ele tende a ser grande (com muitas linhas). É preciso organizar o programa em partes bem definidas (módulos)
	Com o avanço do estudo sobre algoritmos os problemas a serem solucionados aumentam em complexidades. Trata-se de um método utilizado para facilitar a construção de grandes programas, através de sua divisão em pequenas etapas (dividir para conquistar), que são os módulos ou subprogramas.
	Podemos desta forma construir um algoritmo composto por subalgoritmos denominados módulos. Modularizar um algoritmo significa que se está reduzindo o problema em um conjunto de tarefas. Sendo que, cada uma delas corresponde a um módulo.
DEFINIÇÃO DE MODULARIZAÇÃO
> Um módulo é uma unidade do software;
> É um grupo de comandos com uma funcionalidade ou um objetivo bem definido;
> Esse componente deve ser o mais independente possível das outras partes do algoritmo;
> Ele realiza uma tarefa específica dentro duma solução do problema.
POR QUE MODULARIZAR?
	Decompor um problema para:
> facilitar a implementação, isolando as funcionalidades, e especificando o foco delas;
> facilitar os testes das partes (cada módulo independentemente);
> facilitar a manutenção: releituras podem ser separadas aumentar o nível de abstração;
> parar de copiar/ colar funcionalidades já presentes estender a linguagem com novas funções.
MODULARIZAÇÃO ESTRUTURA DE UM PROGRAMA
	Geralmente, um algoritmo vai ter um módulo principal e ele vai chamar outros módulos principal e ele vai chamar outros módulos para compor uma solução algorítmica.
COMPONENTES – Módulos e parâmetros duma interface
Um módulo tem:
> uma interface: declaração das funcionalidades de ofertas, descrição dos dados de entradas e de saída. É tudo que vocês precisam para utilizar o módulo.
> um corpo: implementação das funcionalidades, comandos que compõe o trecho de algoritmo do módulo.
> Um parâmetro: é um tipo de variável utilizada pelo módulo para receber/ comunicar valores de dados das outras partes do algoritmo. Ele pode ser:
		* de entrada, para passar valores para um módulo;
		* de saída, para receber valores do módulo;
		* de entrada e saída, para permitir a passagem de valores tanto para o módulo quanto dele.
	As categorias dos parâmetros serão especificados na criação da interface.
	A grande maioria das linguagens de programação que são utilizadas, têm esta facilidade, seja com o nome de sub-rotinas, subprogramas, procedimentos, funções, módulos, blocos, etc… Sempre é possível subdividir-se um programa de modo a facilitar o entendimento, permitir a reutilização, evitando-se a repetição de blocos dos programas.
	Nosso pseudocódigo definiremos dois tipos de módulos:
		> procedimentos;
		> funções.
	A definição de um procedimento ou de uma função é feita através:
		> de sua declaração, a qual é constituída de um cabeçalho;
		> de declarações, se houver, e;
		> de um corpo (algoritmo).
	
	A comunicação entre programa principal, procedimento e funções ocorre através de chamadas. Os dados são transferidos através de parâmetros e/ou pela utilização e variáveis globais.
ESCOPO DE VARIÁVEIS
	> Global: variável que só pode ser utilizada em um módulo interno ao módulo onde foi declarada.
	> Local: variável que só pode ser utilizada no módulo interno onde foi declarada, e que não possui qualquer significado fora desse módulo.
DESCRIÇÃO
PROCEDIMENTO: módulo que não produz um valor de saída.
FUNÇÃO: módulo que produz um (único valor de saída), pode ser visto como uma função matemática que vai produzir um valor a partir dos argumentos.
TIPOS DE PARÂMETROS: os parâmetros declarados são chamados de parâmetros formais.
PROCEDIMENTOS
	Um procedimento é um módulo que possui ou não um conjunto de entradas, efetua a execução de um conjunto de instruções e não gera um valor como saída, ou seja, não apresenta retorno.
Exemplo
CORPO
> Declaração de variáveis, começada por var.
> Sequência de comandos, começando por inicio e terminando com fimprocedimento.
Exemplo
FUNÇÕES
	Uma função, embora seja bastante semelhante a um procedimento, tem a característica especial de retornar ao programa que a chamou um único valor.
Interface de uma função
CORPO DA FUNÇÃO
> Declaração de variáveis, começando com var.
> Sequência de comandos, começando por inicio e terminando com fimfuncao.
AS funções podem ter multiplos pontos de retorno.
Outro exemplo de função
PARÂMETRO
Podem ser formais ou reais.
AGRUPAMENTO DE PARÂMETROS
Parâmetros formais do mesmo tipo podem ser agrupados a fim de:
	> não repetir declarações de tipos;
	> facilitar a leitura.
Exemplo:
PARÂMETROS DE SAÍDA
	> Um parâmetro formal pode ser marcado como parâmetro de saída através da palavra-chave var.
	> O valor dele pode ser modificado pela rotina.
Exemplo:
PASSAGEM DE PARÂMETROS
	
	Parâmetro de entrada são passados por valor:
		> O valor do parâmetro real é atribuído ao parâmetro formal no lugar da chamada.
		> Esse valor é copiado.
		> Uma alteração do parâmetro formal não impactará o parâmetro real.
	
	Parâmetro de saída são passados por referência:
		> O parâmetro formal torna-se igual ao parâmetro real;
		> Eles compartilham a mesma zona de armazenamento;
		> todas as alterações de valor do formal no procedimento serão refletidas no parâmetro real.
RESUMINDO
Modularização é um método utilizado para facilitar a construção de grandes programas, através de sua divisão em pequenas etapas (dividir para conquistar), que são os módulos ou subprogramas;
	> Procedimento
		- Módulo que não produz um valor de saída.
	> Função
		- Módulo que produz um (único valor de saída), pode ser visto como uma função matemática que vai produzir um valor a partir dos algoritmos.
> A definição de um procedimento ou de uma função é feita através:
		- de sua declaração, a qual é constituída de um cabeçalho;
		- de declarações, se houver, e;
- de um corpo (algoritmo).
LISTAS
MOTIVAÇÃO ESTRUTURA DE DADOS
	O estudo das estruturas de dados é necessário para que possamos identificar e desenvolver modelos matemáticos que resolvam problemas abstratos, bem como a resolução de problemas praticos que envolvam estruturas de dados.
	Uma estrutura de dados armazena dados na memória do computador a fim de permitir o acesso eficiente dos mesmos. A maioria das estruturas de dados consideram a memória primária (a chamada RAM) como pilhas, filas, árvores binárias de busca, árvores AVL e árvores rubro-negras.
RESUMINDO
	Lista é uma estrutura de dados na qual cada elemento é precedido por um elemento e sucedido por outro (exceto o primeiro que não tem predecessor e o último que não tem sucessor).
* Operação com listas
-Inserção
-Remoção
* Implementação de listas lineares:
- Com alocação sequencial e estática;
Vantagens: economia de memória (os ponteiros são implícitos nesta estrutura)
Desvantagens:
> custo para inserir ou retirar itens da lista, que pode causar um deslocamento de todos os itens, no pior caso.
> aplicação em que não existe previsão sobre o crescimento da lista, a utilização de arranjos em linguagens como o Pascal e o C pode ser problemática, neste caso, o tamanho máximo da lista tm de ser definido em tempo de compilação.
- Com alocação não sequencial e dinâmica
Vantagens:
> extremamente eficiente no custo de memória e de processamento;
> nunca acarreta em movimentar todos os elementos;
> bom para aplicações em que não existe previsão sobre o crescimento da lista (o tamanho máximo da lista não precisa ser definido a priori)
Desvantagens:
> envolve conceitos mais avançados de programação: Ponteiro ou Referências;
> utilização de memória extra para armazenar os ponteiros.
PILHAS
Estrutura de dados correspondente
Pilha - sequência de elementos dispostos em ordem, mas com uma regra para entrada e saída dos elementos (o último que chega é o primeiro que sai da estrutura)
RESUMINDO
	É uma lista linear em que todas as inserções e remoçõessão feitas numa mesma extremidade da lista linear. Esta extremidade se denominada topo ( em inglês “top”) ou lado aberto da pilha.
* LIFO (ou FILO):
- Last in, First Out;
- Ultimo a entrar, primeiro a sair.
* As operações definidas para uma pilha incluem:
> Verificar se a pilha está vazia;
> Inserir um elemento na pilha (empilhar ou “push”), no lado do topo;
> Remover um elemento da pilha (desempilhar ou “pop”), do lado do topo.
FILAS
	Sequência de elementos dispostos em ordem com uma regra para a entrada e saída dos elementos (o primeiro que chega também é o primeiro que sai da estrutura). São casos especiais de listas.
	Uma fila é uma estrutura do tipo FIFO (“ First in first out”). Elementos novos são inseridos no lado In (fim da fila) e a retirada ocorre no lado Out (frente ou começo da fila).
	Não podemos remover os elementos que não estejam no início da fila.
FILAS – EXEMPLOS COM OPERAÇÕES
Inicialização: quando sua frente e seu fim for igual a zero, ou seja, não existe nenhuma posição da estrutura ocupada por algum elemento.
Frente: é a posição que indica o próximo elemento a ser acessado
Fim: é a posição que indica o próximo elemento a ser inserido.
Tamanho: é o número máximo de posições permitidas na fila.
EXEMPLOS de uso de filas na computação:
> Filas de impressão
> Filas de processos
> Filas de tarefas
RESUMINDO
	Uma fila é uma estrutura de dados cujas inserções são realizadas em um extremo da lista (que chamaremos fim) e cujas retiradas são realizadas no outro extremo da lisa ( que chamaremos frente).
Inicialização
Inserção
Remoção
ÁRVORES (estrutura de dados não lineares)
Listas ligadas
> São mais flexíveis do que matrizes;
> Mas, são estruturas lineares sendo difícil utilizá-las para organizar representações hierárquica de objetos.
Pilhas e Filas
> Refletem alguma hierarquia;
> Mas, são limitadas a somente uma dimensão.
Árvores
> Estrutura criada para superar limitações de listas ligadas, pilhas e filas.
> Consiste de nós e de arcos.
> São representadas com a raiz no topo e as folhas na base.
> São estruturas adequadas para representação de hierarquias.
REPRESENTAÇÃO
DEFINIÇÃO DE ÁRVORES
Raiz (pai)
Não possui ancestrais. Só pode ter filhos.
Folhas (terminais)
Não tem filhos (ou melhor, seus filhos são estruturas vazias)
ELEMENTOS DE UMA ÁRVORE
> Nó (vértice): elemento que contém a informação;
> Arco (aresta): liga dois nós;
> Pai: nó superior de um arco;
> Filho: nó inferior de um arco;
> Raiz: nó topo – não tem um nó pai
> Folhas: nós das extremidades inferiores – não têm nós filhos;
> Grau: representa o número de subárvores de um nó;
> Grau de uma árvore: é definido como sendo igual ao máximo dos graus de todos os seus nós.
> Cada nó tem que ser atingível a partir da raiz através de uma sequência única de arcos, chamados de caminho.
> Comprimento do caminho: o número de arcos do caminho. Exemplo: o caminho de A até H tem comprimento 2
> Nível de um nó: é a sua distância da raiz da árvore. Usando o exemplo de cima: A raiz tem nível 0, os nós B,C, D e E tem nível 1.
> Altura (ou profundidade) é o nível do nó folha que tem o mais longo caminho até a raiz, somando 1.
- A altura da árvore abaixo é igual a 3.
- A árvore vazia é uma árvore de altura -1, por definição.
- Uma árvore com um único nó tem altura 1.
ÁRVORES BINÁRIAS
Uma árvore binária é uma estrutura que é o vazia ou possui 3 componentes:
- Uma raiz
- Uma subárvore esquerda
- Uma subárvore direita
As subárvores devem ser árvores binárias.
REPRESENTAÇÃO DE ÁRVORES BINÁRIAS
	O equivalente de uma lista de adjacência é uma coleção de registros com três campos contendo o nó em questão, um ponteiro para o registro do nó filho esquerdo e um ponteiro para o registro do nó filho direito.
PERCURSOS EM ÁRVORES BINÁRIAS
	Os nós de uma árvore binária podem ser visitados de três formas (varredura da árvore):
> Pré- ordem (pre-order): raiz, subárvore esquerda (E), subárvore direita (D);
	- visitar a raiz antes das subárvores.
> Em - ordem (in-order): subárvore esquerda (E), raiz, subárvore direita (D);
> Pós - ordem (post-order): subárvore esquerda (E), subárvore direita (D), raiz.
	- visitar a raiz após visitar as subárvores.
Exemplo em pré-ordem
Exemplo em ordem
Exemplo Pós-ordem
RESUMINDO
> Estrutura criada para superar limitações de listas ligadas, pilhas e filas;
> Consiste de nós e de arcos;
> São representadas com a raiz no topo e as folhas na base;
> São estruturas adequadas para representação de hierarquias;
> Elementos de uma árvore: vértice, aresta, raiz, folhas, grau, caminho, comprimento e altura.
> Uma árvore binária é uma estrutura que é ou vazia ou possui 3 componentes:
- Uma raiz;
- Uma subárvore esquerda;
- Uma subárvore direita.
Percurso em árvores:
> Pré-ordem (pre-order): o percurso em pré-ordem segue os nós até chegar os mais “profundos”, em “ramos” de subárvores da esquerda para a direita.
> Em-ordem (in-order): a ordem simétrica visita a raiz entre as ações de percorrer as duas subárvores.
> Pós-ordem (post-order): percorremos a subárvore da esquerda mais longe, depois a subárvore da direita e por fim a raiz.