Algoritmos e Estruturas de Dados
Programa do Curso

1. Introdução/Revisão (4 aulas)

1.1 Estruturas de Dados

Tipos Abstratos de Dados

Tipos definidos pelo programador

Tipos Embutidos: sua Representacao e Operacoes: Inteiro, Real, Caracter

Arrays, Estruturas, Unions, Strings de Caracteres

Algoritmos e Estruturas de Dados
Programa do Curso

1.2 Algoritmos

Conceito de Algoritmo

Comandos Básicos do C	- sintaxe/semantica

Complexidade

Recursividade

Subprogramas

Variaveis Locais/Globais

Parâmetros e convenção de passagem de parametros

Alguns algoritmos básicos

Algoritmos e Estruturas de Dados
Programa do Curso

2. Listas/Pilhas/Filas (3 aulas)

Listas: operações

Listas Encadeadas

Pilhas: operações, implementacao usando array e listas encadeadas

Filas: operações, implementacao usando array e listas encadeadas

Filas de Prioridade

Listas Circulares e Duplamente Encadeadas

Algoritmos e Estruturas de Dados
Programa do Curso

3. Árvores (4 aulas)

Conceitos

Árvores Binárias

Atravessando Arvores

Árvore Binaria de Busca

4. Apectos Complementares (2 aulas)

Busca Hash

Algoritmos e Estruturas de Dados
Referências

Data Structures Using C and C++

Y. Langsam, M. J. Augestein, A. M. Tenenbaum

Prentice Hall

Estrutura de Dados e Algoritmos

J.L.Sawarcfiter, L. Markeson

Editora LTC

Introdução

Implementação de uma Aplicação

representa uma abstração da realidade

consiste de um conjunto selecionado de dados relacionados com o problema a ser resolvido

deste conjunto, é possível a obtenção dos resultados esperados

Introdução

Cadastro de Pessoal de uma Empresa

Modelo Abstrato  simplificação

Empregado  conjunto de dados

os que são relevantes para o empregador e para os procedimentos contábeis da empresa

identificação, salário, dependentes, .....

Abstraem-se dados irrelevantes:

cor do cabelo, estatura, peso

Introdução

Resolução de um problema

escolher uma abstração da realidade

o que é relevante para o problema

informação: um conjunto de dados

comportamento: um conjunto de operações

a forma como se representa informação e suas operações estão intimamente ligadas

Introdução

Dados Relevantes em um Problema

escolher um conjunto de dados  uma representação possível da situação real

orientada às características do problema

os dados precisam ser representados

a etapa seguinte é a escolha de uma forma de representação

Introdução

Como representar dados?

Depende da ferramenta usada na solução

É, geralmente, uma tarefa difícil

Não existe uma única solução

Não existe receita

a solução de um problema no computador é um modelo

a construção do modelo transcende diversos níveis de detalhe

Introdução

Problema: representar a posição de um objeto

  par de reais: representando as coordenadas cartesianas ou polares

  representação por ponto flutuante

x = f * 2 e

  notação binária para e e f

Introdução

A decisão  é influenciada pelo problema

As outras são dependentes da ferramenta e da tecnologia que se emprega

PROGRAMADOR  focaliza o problema

decisões de nível mais baixo - projetistas do equipamento computacional

ferramentas que permitam ao programador se concentrar nas características do problema

Algoritmo

Um processo sistemático para a resolução de problemas

dois aspectos básicos no estudo de algoritmos  correção e análise

correção: exatidão do método empregado

análise:obtenção de parâmetros que permitam verificar a eficiência do algoritmo
(execução e memória ocupada)

Algoritmo

Computa uma saída(o resultado do problema) a partir de uma entrada

durante o processo, manipula dados gerados a partir de sua entrada

dados dispostos e manipulados de forma homogênea  Tipo Abstrato de dados

um modelo matemático + um conjunto de operações definido sobre este modelo

Algoritmo

Um algoritmo é projetado em termos de de Tipos Abstratos de Dados

Para implementá-lo em uma Linguagem de Programação:

Como representá-lo nesta linguagem?

Tipos e Operações suportadas pelo computador.

Na sua representação emprega-se Estruturas de Dados

Programa

Algoritmo expresso em uma linguagem formal: Linguagem de Programação

Toda linguagem envolve dois aspectos:

sintaxe e semântica

Sintaxe: forma

Semântica: conteúdo

Algoritmos e
Estruturas de Dados

Resolução de um Problema

Algoritmo

representação do comportamento

Estrutura de Dados

representação da informação

Algoritmos e
Estruturas de Dados

No processo de construção de programas:

a formulação do algoritmo e

a definição de estruturas de dados a serem usadas

estão intimamente ligadas

Algoritmos e
Estruturas de Dados

Decisões sobre estruturas de dados não podem ser tomadas sem conhecimento dos algoritmos aplicados e vice-versa

Num algoritmo vamos distinguir dois aspectos complementares:

estático e dinâmico

Estrutura de Dados

Como a informação é organizada , como será manipulada e como será utilizada

Seu estudo envolve dois objetivos complementares:

Identificar e desenvolver entidades matemáticas e operações

Determinar que classes de problemas podem ser resolvidas usando essas entidades e operações

Algoritmo

Um texto contendo comandos (instruções)

devem ser executados na ordem prescrita

corresponde a representação concreta e tem caráter estático

esse texto nos interessa pelos efeitos que causa decorrentes de sua execução, dado um conjunto de valores iniciais

execução: evento dinâmico  evolui no tempo

Algoritmo

A grande dificuldade na concepção e no entendimento de algoritmos é o relacionamento dos aspectos estático e dinâmico

como entender as estruturas dinâmicas das possíveis execuções do algoritmo a partir da estrutura estática

Algoritmo

Deve utilizar Estruturas Básicas de controle

formas naturais de pensar e adequadas à construção de algoritmos inteligíveis

SE ......... ENTÃO ..........SENÃO ........

Algoritmo

Estado de um dado sistema é o conjunto de propriedades desse sistema que são relevantes na situação considerada

(ex. conjunto de valores de variáveis de um programa)

Algoritmo

Ação é um evento que ocorre num período de tempo finito estabelecendo um efeito desejado e bem definido

ação: o interesse é decorrente do efeito produzido

descrição de um evento: é feito sob a forma de relato do observado

Algoritmo

Exemplo:
dona de casa descasca batatas para o jantar

traz a cesta com batatas;

traz a panela do armário;

descasca batatas;

devolve a cesta;

“;” denota seqüência de execução de comandos

descascar batatas no dia seguinte é outro evento com o mesmo comportamento

algoritmos descrevem uma classe de eventos que obedecem um mesmo padrão de comportamento

Algoritmo

Em todo evento pode-se reconhecer um padrão de comportamento, fazendo-se abstração de diferentes estados iniciais e efeitos

cada vez que o padrão de comportamento é seguido, o evento ocorre

seu efeito é totalmente determinado pelo padrão de comportamento e pelo estado inicial

Algoritmo

É a descrição de um padrão de comportamento, em termos de um repertório bem definido e finito de ações primitivas”, que podem ser executadas

possui um caráter imperativo

uma ação no algoritmo: um comando

é uma norma executável para estabelecer um certo efeito desejado

Apresentação dos Algoritmos

Formato Livre com comandos das linguagens estruturadas

estrutura de blocos

identação

funções

Linguagem C

Blocos

Blocos: um conjunto de comandos com uma função bem definida

serve para definir os limites onde as variáveis declaradas em seu interior são conhecidas

Variáveis locais a blocos e globais a blocos

Blocos podem possuir um nome: sub-programas (funções no C) ou não

são delimitados por { }

Programa

If (a>b)

{

printf ( “A é maior”)

}

else

{

printf (“B é maior”)

}

Tradutor:

Compilador +

Linkeditor

programa.c

programa.exe

A é maior

Processamento de Linguagens

Linguagens de Programação: são projetadas em função da facilidade na construção e confiabilidade dos programas

Como executam em um computador cuja Linguagem de Máquina é bastante diferente?

Processamento de Linguagens

Existem basicamente duas alternativas para esta implementação :

1)	Interpretação

2)	Tradução

A interpretação de um programa é feita pela chamada dos subprogramas, escrito na linguagem de máquina do computador hospedeiro, em seqüência apropriada

Interpretação

1. Obter o próximo comando do programa

2. Determinar que ações devem ser executadas

3. Executar essas ações

simulação de um computador hospedeiro de uma máquina especial cuja linguagem de máquina é de nível mais alto

Interpretação

Esta seqüência é bastante semelhante àquela executada por computadores tradicionais:

1. Obter a próxima instrução (PC)
2. Incrementar o PC
3. Decodificar a instrução
4. Executar a instrução

TRADUÇÃO

Programas escritos em LP de alto nível são traduzidos para versões equivalentes em linguagem de máquina antes de serem executados

Essa tradução é feita em vários passos

Compilador

Linkeditor

Loader

COMPILAÇÃO

Logicamente a tradução pode ser dividida em 2 grandes partes:

análise do programa fonte (dados de entrada)

síntese do programa objeto executável

Síntese do programa objeto

A saída da fase anterior consiste basicamente de

programas quase executáveis (*.o)

podem fazer referências a dados externos ou outros programas

Linkedição: une diversos *.o em um programa executável pronto para rodar

Programa

If (a>b)

{

printf ( “A é maior”)

}

else

{

printf (“B é maior”)

}

Compilador

pgm3.c

programa.exe

A é maior

If (a>b)

{

printf ( “A é maior”)

}

else

{

printf (“B é maior”)

}

If (a>b)

{

printf ( “A é maior”)

}

else

{

printf (“B é maior”)

}

pgm1.c

pgm2.c

Linkeditor

pgm1.o

pgm2.o

pgm3.o

Síntese do programa objeto

Linkedição

um procedimento para finalizar a resolução de referências

programas podem ser traduzidos separadamente

ou utiliza-se uma biblioteca

Visão Geral de um Programa

O Problema

Imprimir uma mensagem mostrando o que está sendo somado

Calcular a soma de três números

Imprimir o resultado

Visão Geral de um Programa

Este programa não faz muita coisa

Como seleciona os números a somar?

Não imprime nenhuma mensagem explicativa?

Que tipos de números soma?

Visão Geral de um Programa

Definindo melhor o problema

Exibir para o usuário o que faz o programa

Exibir o que espera como entrada

Pedir os três valores (A, B,C) e armazenar

Somar A + B + C e guardar em SOMA

Exibir o valor SOMA ao usuário

Modelo de um Programa

Este é um modelo seguido pelos programas

Um programa tem que ser capaz de armazenar sua entrada em algum lugar

Entrada

Processa a Entrada

Produz a Saída

Modelo de um Programa

Entradas são armazenadas para serem processadas e gerar uma saída útil

Dados são armazenados em variáveis

posições de memória com um nome que podem conter dados

as variáveis podem conter tipos diferentes de dados

Variáveis e Tipos de Dados

Variáveis podem conter valores diferentes durante a execução do programa

os valores são consistentes com o tipo da variável

Alguns valores não devem ser alterados durante a execução

Constantes

Variáveis e Tipos de Dados

Dados - em variáveis ou constantes -podem ser de diferentes tipos

inteiros ( curtos / longos)

reais - ponto flutuante

precisão simples ou dupla

caracteres isolados

string de caracteres

Variáveis

Variável é algo que se altera

Dados armazenados em uma variável podem se modificar

Em um programa

definir uma variável significa reservar uma memória para armazenar seus valores

Variáveis

As linguagens de Programação permitem definir identificadores para as variáveis

Imprima(“Programa de Soma de Valores”)

Imprima (“Entre com 3 valores inteiros separados por espaço em branco”)

Leia (A,B,C)

Soma = A + B + C

Imprima (Soma)

Variáveis

Deve-se atribuir às variáveis nomes que o ajudem a lembrar a finalidade de cada uma delas

Nomes mais longos tornam seu programa mais claro

outros podem ter que revisar seu código

pode ser necessário revisar o programa daqui a 6 meses

Identificadores

Identificador: Um elemento básico da Linguagem

identificadores válidos: A, AB, A1B12C

identificador inválido: 1AB

Identificadores dão nomes a:

Variáveis

Trechos de Programa

Identificadores

C- Padrão ANSI: nomes de variáveis, funções, rótulos == identificadores

Tamanho: 1 a diversos caracteres: pelo menos os 61ºs são válidos

1o. caracter - letra ou sublinhado

letras maiúsculas e minúsculas são tratadas diferentemente

Tipo de Dados

Na matemática, variáveis são classificadas de acordo com algumas características importantes

Existe distinção clara entre

variáveis reais, complexas e lógicas

valores individuais e conjunto de valores

funções

Tipo de Dados

Esta noção de classificação é muito importante

Cada constante, variável, expressão ou função é de um certo tipo

refere-se ao conjunto de valores que pode assumir

Tipo de Dados

Em programas, não é possível deduzir o tipo da variável a partir do seu contexto

é necessário explicitar o tipo de cada variável

a cada tipo de dados está associada uma representação no computador

é necessário conhecer o tipo de dados para saber qual a sua representação

Tipo de Dados

A um tipo de dados está associado:

uma representação

o tamanho – o número de células de memória para armazenar esta representação

a área de memória onde ficará o valor da variável tem que ter dimensões compatíveis com a sua representação

Determina o conjunto de valores que variáveis de um dado tipo podem assumir

Tipo de Dados

As operações exigem argumentos de um dado tipo e produzem resultados do mesmo tipo

É importante para o compilador saber o tipo de cada variável antes de empregá-la em uma operação

Definição de Variáveis

Variável

o nome do local onde se pode colocar qualquer conjunto de valores possíveis do tipo básico associado.

nome da variável é um identificador

toda a variável deve ser declarada da seguinte forma:

tipo identificador [,identificador, ...] ;

Tipos Básicos do C

São cinco os tipos de dados básicos do C

char

int

float

double

void

Tipos Básicos do C

O tamanho e a faixa destes dados dependem do processador e da implementação do compilador

char - 1 byte - ASCII - byte (signed/unsigned : depende da implementação)

inteiro - 2 bytes - tamanho natural de uma palavra do processador

float - dependem da representação do ponto flutuante - padrão ANSI: 1 x 10-37 a 1 x 10+37

void declara explicitamente que uma função não retorna valor algum ou cria ponteiros genéricos

Definição de Variáveis

int X1;

float A, B;

char Nome;

Definição de Variáveis

A semântica da declaração de uma variável corresponde a

criação de locais na memória rotulados com o nome da variável (identificador)

marcada com o tipo de valores que ela pode conter (equivale a um tamanho e forma de representação)

X1: é o nome do local de memória que só pode conter valores variáveis do tipo inteiro

A e B só podem conter valores variáveis do tipo real

Compatibilidade de Tipos

É importante observar que:

o resultado da expressão do lado direito de um comando de atribuição deve ser coerente com o tipo declarado para a variável do lado esquerdo

a = b+c;
como b e c são do tipo float, então a deve ser float.

Compatibilidade de Tipos

a = 3;

a inteiro

i = i + 1;

i inteiro

delta = b^2 – 4 * a * c;

Expressões

Uma forma linearizada da usada na matemática

Operadores Aritméticos

+, -, *, /

3/2 = 1 (divisão de inteiros)

Precedência: da matemática

uso de parênteses

a = b+c * (x*y-5);

a = a+2;

mod : resto da divisão inteira

Expressões

Operadores Lógicos

dentro das relações lógicas, usaremos conectivos lógicos usuais

E (&&)

OU (||)

NEGAÇÃO (!)

Conectivos relacionais

>, <, >=, <=, ==, !=

Expressões

Prioridades para operações mistas

1o. : parênteses e funções

2o. : expressões aritméticas
* , /
+ , - (binários)

3o. : comparações
>, >=, <, <=, ==, !=

4o. : !

5o. : &&

6o. : ||

Comentários

Uma anotacão

Servem para ajudar a explicar a codificação

Seu programa deve ser compreendido por qualquer outro programador

/* ………COMENTÁRIO ………..*/

// …… comentário até o fim da linha

Comentários

Devem ser utilizados com liberalidade em todo o programa

Devem explicar seu algoritmo

Estão relacionados com a solução do problema

Não devem ser óbvios

Atribuição

Atribuição

designam valores a uma variável

A = B; /* Faz A = B */

/* Este é um comentário óbvio - desnecessário */

os valores atribuídos a uma variável devem ser compatíveis com seu tipo

Sintaxe: identificador = valor ;

Entrada / Saída

Entrada:informações para o programa

ítens sendo adquiridos em uma compra de supermercado

Saída: informações para o usuário

a nota fiscal de compra

Entrada / Saída

A instrução de entrada lê de um dispositivo de I/O uma informação

teclado

leitora ótica

ao digitar o número 10

2 caracteres

a operação de entrada converte para a representação interna

Entrada / Saída

Origem da Entrada

teclado

disco - arquivo

Destino da Saída

vídeo

impressora

disco - arquivo

Entrada / Saída

Entrada

scanf (“%d”, &a);

c = getchar();

Saída

printf(“O número é %d”, a);

Comandos de Entrada/Saída

c = getchar();

le um caracter do teclado

scanf (“%d”, &num);

le um dado do teclado com o formato especificado

printf (“%d”, num);

escreve na tela o conteúdo da variável com o formato especificado

Formato

%d - inteiro

%f - real

%c - caracter

%s - string

\n - próxima linha

scanf(“%s %d, %f”, nome, &freq, &nota)

le uma linha no seguinte formato
Maria 12, 7.5

Operações Especiais do “C”

Incrementando 1:

i++;

++i;

Decrementando 1:

i--;

--i;

Comando para o Compilador

#include <Nome_arquivo>

expande o arquivo de Nome_arquivo dentro do arquivo fonte

#define MAX 10

define MAX como uma constante 10

substitui o texto MAX por 10

funciona como uma macro

Um Programa em “C”

# include <……>

# include <……>

#define ……

#define ……

/* definições de tipos */

typedef int tipo_a;

/* protótipos de funções */

float calc_media (int, int, int);

/* função principal */

main ()

{

………….

}

/* as outras funções */

float calc_media (int x, int y, int z)

{

………………

}

Fluxo de Controle

Um algoritmo é um texto estático: está escrito

Deve ser executado: processo dinâmico

O que relaciona esse dois aspectos é o fluxo de controle

Fluxo de Controle

Esse fluxo determina em cada passo da execução, qual o próximo comando a ser executado

A ordem de execução é bem diferente da que consta no texto estático

No entanto, olhando-se para o algoritmo deseja-se prever o resultado da execução

Fluxo de Controle

A ordem de execução das ações é a chave para entender o funcionamento do algoritmo

Essa ordem muda de uma execução para outra

depende dos dados de entrada

deve-se considerar toda a classe de diferentes processos possíveis que o algoritmo pode evocar

Estruturas Básicas de Controle

Seqüenciamento:

Separa um comando do outro e determina a execução em seqüência dos comandos

Representa a estrutura de controle mais simples: seqüência simples

Estruturas Básicas de Controle

Imaginemos que a dona de casa, ao descascar batatas usa avental caso esteja usando roupa clara, então nesse dia deve executar:

traz a cesta com batatas;

traz a panela do armário;

coloca o avental;

descasca batatas;

devolve a cesta;

Estruturas Básicas de Controle

Como ela usa um critério racional para colocar o avental, podemos uní-lo ao primeiro algoritmo empregando um conectivo condicional se .... então

traz a cesta com batatas;

traz a panela do armário;

se roupa é clara então coloca avental;

descasca batatas;

devolve a cesta;

if (condição) comando else comando

if (condição) {....} else {....}

Estruturas Básicas de Controle

A execução ou não da ação “coloca avental” depende, em cada vez que o algoritmo é executado, do valor (verdadeiro ou falso) da condição “roupa é clara”

O conectivo condicional representa a segunda das estruturas de controle: a alternativa

Estruturas Básicas de Controle

A dona de casa pode em um dia querer descascar 13 batatas e em outro 30 batatas

reconhece-se que a ação descascar uma batata tem sempre o mesmo padrão de comportamento

ela pode selecionar o número de batatas suficientes em função de algum outro critério, por exemplo: número de pessoas para jantar

Estruturas Básicas de Controle

traz a cesta com batatas;

traz a panela do armário;

se roupa é clara então coloca avental;

se “número insuficiente” descasca uma batata

se “número insuficiente” descasca uma batata

se “número insuficiente” descasca uma batata

se “número insuficiente” descasca uma batata

.....

devolve a cesta;

Estruturas Básicas de Controle

A alternativa foi utilizada por exemplo 50 vezes

Essa não é uma construção muito boa

caso 5 batatas fossem o suficiente, a dona de casa ia se perguntar mais 45 vezes para se certificar

foi introduzida uma restrição arbitrária: no máximo 50 batatas

Para esse tipo de construção utiliza-se o conectivo repetitivo: enquanto ....faça

Estruturas Básicas de Controle

traz a cesta com batatas;

traz a panela do armário;

se roupa é clara então coloca avental;

enquanto número de batatas insuficiente faça

descasca uma batata;

devolve a cesta;

Corresponde à execução repetida do comando se “inspeção” então “ação”

é executado até que a inspeção seja falsa

Estruturas Básicas de Controle

Algoritmo: é um texto estático capaz de cobrir uma grande gama de acontecimentos

é fácil construir um texto que não seja executável em tempo finito tal como:

enquanto saia é clara
descasque uma batata

Estruturas Básicas de Controle

Um algoritmo deve ser determinístico:

dadas as mesmas condições iniciais deve produzir ao final da execução os mesmos resultados

só estamos interessados em algoritmos que terminam em um tempo finito

Programas:

uma certa espécie de algoritmos

Comandos Básicos do C

Seqüência simples

Comando1;
Comando2;
Comando3;
Comando4;

Instruções Condicionais

Se não pode agüentar o calor, fique fora da cozinha

avalia uma condição

executa uma ação com base no resultado positivo

if (calor > maximo)

{………}

Instruções Condicionais

if (NaoAguentaCalor()) {

if (JanelaNaoAbre()) {

FiqueForaDaCozinha;

}

}

else

LavePratos;

Instruções Condicionais

if (NaoAguentaCalor())

if (JanelaNaoAbre())

FiqueForaDaCozinha;

else

LavePratos;

Comandos Básicos do C

Alternativa

Quando a ação a ser executada depender de uma inspeção ou teste, teremos uma alternativa simples ou composta

Alternativa simples

se <condição> então

C1;

C2;

C3;

C4;

fim se;

Comandos Básicos do C

Alternativa simples

“C”

if (<condição>) {

C1;

C2;

C3;

C4;

}

Comandos Básicos do C

Alternativa composta

se <condição> então

C1;

C2;

C3;

C4;

senão

C5;

C6;

C7;

C8;

fim se;

Comandos Básicos do C

Alternativa composta

“C”

if (<condição>)

{ C1;

C2;

C3;

C4; }

else

{ C5;

C6;

C7;

C8; }

Comandos Básicos do C

Nos comandos acima <condição> é qualquer expressão cujo resultado é um valor booleano ou seja true ou false

Exemplos

onde está relacionado um bloco de comandos (limitados por { }) pode ser usado um único comando

bloco: como um novo comando / extensão da linguagem

Instruções Case

Forma abreviada de escrever instruções condicionais

quando se compara uma mesma variável com diversos valores

um conjunto de if’s aninhados podem ser substituídos por uma instrução case

Instruções Case

switch (idade)

{ case 20:

printf (“Ola!”); break;

case 30:

printf (“Tudo bem?”); break;

case 40:

printf (“Como vai?”); break;

default:

printf(“não sei sua idade...”);

}

Comandos Básicos do C

Repetição

quando um conjunto de ações é executado repetidamente enquanto uma determinada condição permanece válida

condição é uma expressão cujo resultado é um valor lógico

Comandos Básicos do C

Repetição

enquanto <condição> faça

C1;

C2;

C3;

C4;

fim enquanto;

Comandos Básicos do C

Repetição - “C”

while ( <condição> )

{ C1;

C2;

C3;

C4; }

Comandos Básicos do C

Repetição

faça

C1;

C2;

C3;

C4;

enquanto <condição>;

Comandos Básicos do C

Repetição “C “

do {

C1;

C2;

C3;

C4;

} while (<condição>);

Comandos Básicos do C

Repetição

for (i=0; i<N; i++)

{ C1;

C2;

C3;

C4;

}

Comandos Básicos do C

Repetição

while<condição> ……...

se já da primeira vez a condição for falsa, os comandos não são executados nenhuma vez

do {……} while < condição>

se da primeira vez a condição for falsa, os comandos são executados uma vez

Enquanto a condição for verdadeira os comandos são executados, quando for falsa, o comando é abandonado

Loops

Repete uma instrução ou um conjunto de instruções até que uma condição seja satisfeita

while (condição) { ……… }

do { ………… } while (condição);

for (i=0; i<N; i++) { …………………… }

Break / Bloco

Go To com destino específico

1a. Instrução após o final do switch

1a. Instrução após o final de um loop

Bloco

conjunto de comandos que substituem um comando na sintaxe da linguagem

{ ……………………}

Inteiros

Qualquer valor do conjunto dos números inteiros

inteiros curtos - int - 4 bytes

inteiros longos - long - 8 bytes

operações

=

+, -, *, /(divisão de inteiros)

Resto: %

Reais

Também chamados de ponto flutuante

Qualquer valor do conjunto dos números reais

estão limitados no número de dígitos decimais - float ou double

sua representação: mantissa e expoente

Operações :

=, +, -, *, /

Usando Tipos

Se tenho que definir uma variável para conter idades, que tipo usar?

inteiros, e curtos são suficientes

É função do:

conjunto de valores que a variável pode assumir

da precisão que se deseja no resultado de operações

Caracteres

É qualquer caracter isolado representado no computador

letras e números são caracteres

caracteres especiais - &, %, *

caracteres especiais e não visíveis - ESC, CR, LF,…

ocupam 1 byte - ASCII

char a = ‘A’;

Strings de Caracteres

Um número arbitrário de ocorrências de caracteres

deixa em aberto o número de ocorrências

não possui uma representação direta no C

char a[50];

#define NOME ”Maria”

Constantes

Não tem seu valor alterado durante a execução

Um programa que verifica idade mínima para dirigir = 18  18 será uma constante

dê nomes simbólicos às constantes

facilita a alteração da idade mínima para 16

numéricas- o próprio número

caracteres ou strings: ‘A’ “Maria”

Nomes das Variáveis

As variáveis devem ser criadas explicitamente antes de serem usadas

listar variáveis e seus tipos

duas variáveis em uma mesma área de programa não podem ter o mesmo nome

use nomes que possuam significado em relação ao problema

Salario 	A1, a2 	index, indexx 

Atribuindo Valor

int idade;

idade = 30;

vendas = vendas_antigas + vendas_novas;

num = num + 1;

Tipos Embutidos

Identifica o comportamento abstrato de um conjunto de objetos com um conjunto comum de operações

inteiros = ...-2,-1,0,1,2,...

Operadores: *,-,+,e /

o tradutor da LP mapeia 25 em 00011001 em representação de complemento a dois.

Tipos Embutidos

propriedades úteis:

invisibilidade da representação subjacente

o programador não tem acesso a seqüência de bits que o representa

só pode ser alterada apenas como resultado de operações

alteração visível com novo valor do tipo embutido

estilo de programação

protege contra manipulação indisciplinada

a máquina convencional subjacente não possui proteção

Tipos Embutidos

Modificabilidade

a implementação das abstrações podem ser mudadas sem afetar os programas que as usam

aumenta a portatibilidade

Identificação de operadores ambíguos

os mesmos símbolos de operações podem ser usados para representar um grande número de operações

por exemplo: soma de inteiros e soma de reais utilizam o mesmo símbolo mas implementam operações diferentes

Arrays

Imagine que é necessário controlar uma centena de valores de pontos em um torneio

ponto_1, ponto_2, ……., ponto_100

Array é um agregado de variáveis do mesmo tipo e de mesmo nome

cada variável é distinguida pelo seu índice no array

Arrays

int ponto[100],i;

for (i=0; i<100; i++)

ponto[i] = 0;

/* são alocadas em posições consecutivas de memória */

ponto[0]

ponto[1]

ponto[99]

……………………….

Estruturas

Agrupa de maneira independente um conjunto de variáveis de tipos diferentes

pode-se incluir variáveis simples, arrays, outras estruturas

struct {
char nome[20];
float salario;
int dependentes;
char sexo; } Empregado ;

Ponteiros

Endereço de memória

uma variável ponteiro é uma variável especialmente declarada para guardar um ponteiro para seu tipo especificado

guarda o endereço de uma variável deste tipo

Operadores de Ponteiro: & e *

&a = endereço da variável a

*ptr = conteúdo da memória cujo endereço que está em ptr

Ponteiros

ponteiros em C

retorno de valores em argumentos de função

tipos de dados recursivos
estruturas de dados dinâmicas: listas encadeadas ...

Ponteiros

&: devolve o endereço de memória do seu operando ( m = &count)

*: devolve o conteúdo de memória apontado por um ponteiro (q = *m)

variáveis que guardam ponteiros devem ser declaradas como tal

declaração: tipo * nome_ponteiro

tipo: tipo base do ponteiro

aloca memória para um endereço
não aloca memória para variável

Ponteiros

Alargam o contexto a partir do qual se pode ter acesso a um dado

Ponteiros

Podem ser usados para outros propósitos, tornando programas menos compreensíveis e inseguros

pode levar a sérias violações de tipos

em tempo de tradução é possível garantir que o ponteiro aponta para o tipo correspondente, no entanto isto não é feito em tempo de execução (caro)

Ponteiros

Código

Dados

Pilha

Heap

Ponteiros

Alocação Dinâmica

int * x;
x = malloc(sizeof(int));

um ponteiro pode ficar pendurado, isto é, pode se referir a uma posição que não está mais alocada
free(x);

uma posição de memória alocada pode ficar inacessível (x local a uma função)

Ponteiros

Alocação pode causar estouro do heap ou da pilha

deve-se sempre utilizar o free quando a memória é desnecessária

Ponteiros não inicializados

podem provocar acesso não controlado à memória

Ponteiros

Uma variável ponteiro contém como valor o endereço absoluto de um objeto do tipo ao qual o ponteiro está amarrado.

NULL: não aponta para nada

São variáveis:

locais ou globais (a ser definido)

Tipos definidos

O programador pode definir seus próprios tipos de dados

tipos complexos usados da mesma forma que tipos simples

declaram-se variáveis utilizando-se esses novos tipos

typedef char tipo_nome [30];
tipo_nome nome;

Tipos definidos

Estrutura de dados X implementação

ao criar sua própria estrutura de dados, pode-se criar um novo tipo para as finalidades do seu programa

terá que usá-lo na criação de algumas de suas variáveis

Tipos definidos pelo usuário

Meios de fornecer nomes aos tipos

Novos tipos são definidos a partir de:

mecanismos construtores de tipos;

tipos embutidos

tipos já definidos pelo usuário

Tipos definidos pelo usuário

Definição de tipo

equivale a um padrão instanciado pela definição de variáveis

não incorpora novas operações de acesso ao tipo

operações: as mesmas dos elementos básicos usados na construção do tipo

Tipos definidos pelo usuário

Vantagens

Legibilidade

Modificabilidade

Fatoração

reduz quantidade de codificação e erros por distração

Teste de Consistência

padrão de compatibilidade ou equivalência de tipos permite validação

Tipos definidos pelo usuário

Tipos embutidos :

não estruturados: int, float, char

Tipos não estruturados são construídos a partir de tipos primitivos não estruturados

Tipos de Dados

Agregados de Dados

Homogêneos

Heterogêneos

Seqüência

Recursão

União Discriminada

Conjunto Potência

Agregados de Dados

Agregado de objetos elementares ou de outros agregados

de elementos homogêneos: array

de elementos heterogêneos: struct

Um objeto agregado tem um único nome

a manipulação pode ser feita em um único componente elementar de cada vez

operação de seleção

algumas linguagens permitem atribuir valores ou comparar agregados inteiros

Agregados de Dados

Heterogêneos: produtos cartesianos

struct

é um conjuntos cujos elementos são n-tuplas ordenadas (a1,...,an)

As linguagens encaram os objetos de um produto cartesiano como compostos de nomes simbólicos

Agregados Heterogêneos

Notação em linguagem C

typedef struct {

int registro;

char nome[50];

int idade;

float salario;

} tipo_funcionario;

Seu emprego

tipo_funcionario funcionario;

tipo_funcionario *end_func;

funcionario.idade = 35;

end_func = &funcionario;

end_func->salario = 1000;

(*end_func).salario = 1000;

Agregados Heterogêneos

Struct: arranjo seqüencial de componentes

cada componente ocupa um número inteiro de unidades endereçáveis de memória, podendo ser referenciado pelo nome de seu campo

variáveis não podem conter nomes de campos

Agregados Heterogêneos

typedef struct {

int a;

float b;

int c[5];

} tipo_T;

“C” permite que o programador tenha acesso a todos os campos da estrutura

Agregados Homogêneos

Homogêneos: mapeamentos finitos

array

Agregados Homogêneos

Declaração: float a [5]

pode ser encarada como o mapeamento dos inteiros de 0 a 4 no conjuntos dos reais

um objeto do conjunto imagem pode ser selecionado por indexação: índice do domínio

a[k]: aplicação da função ao argumento k

k fora do domínio implica em erro

só pode ser detectado em tempo de execução

algumas linguagens guardam descritores capazes de identificar este erro

“C” não detecta

Agregados Homogêneos

Vetor com várias dimensões

typedef int tipo_linha[10]

typedef tipo_linha tipo_matriz2[5]

define uma matrix 10 x 5

typedef int tipo_matriz [10][5]

“C”: fixado em tempo de compilação

SUBCONJUNTO FIXADO QUANDO O PROGRAMA É ESCRITO

Agregados Homogêneos

Agregados Homogêneos

tipo_T ae[N];

tipo dos índices: sempre inteiros de 0 a N-1

tipo_T: tipo de cada elemento do array

Os tipos int a1[50] e int a2[70] são diferentes

A alocação de memória é estática e contígua.

Agregados Homogêneos

Array “C”

aloca um número inteiro de unidades endereçáveis de memória para cada componente.

o nome do array indica a posição de memória onde se encontra o 1o. elemento

uma referência a primeira posição da área onde o objeto de informação está armazenado

um ponteiro

Agregados Homogêneos

Array “C”

a declaração de um array aloca memória para os elementos do array em área contígua

o nome do array equivale ao ponteiro para o 1o. elemento do array

não guarda informação de limites em tempo de execução o que implica em não efetuar testes

Seqüências

Consiste em um número arbitrário de ocorrências de ítens de dado de um determinado tipo componente.

deixa em aberto o número de ocorrências

Cadeias de Caracteres (STRINGS)

exemplo onde o tipo de componente é o caracter

mesmo conceito de um arquivo seqüencial

Seqüências

operações sobre cadeia:

concatenação

seleção do primeiro ou último componente

fatia: uma subcadeia pode ser extraída especificando-se as posições do primeiro e do último caracteres desejados

pattern matching

Seqüências

operações sobre arquivo seqüencial

leitura: varredura do arquivo em seqüência

adição: ao final do arquivo

União Discriminada

Especifica uma escolha que será feita dentre as diferentes estruturas alternativas

cada estrutura alternativa é chamada de variante

o tamanho da variável é o da maior variante

“C” - UNION

union {

tipo_a A;

tipo_b B;

tipo_c C;

}

as 3 estruturas ficam sobre a mesma região da memória

União Discriminada

typedef struct {

float dist;

float rad;

} polar;

typedef struct {

float x;

float y;

} cart;

typedef struct{

char id [5];

union {

polar coord_polar;

cart coord_cartesiana;

} pos;

float modulo_veloc;

} t_dados;

Conjunto Potência

Variáveis cujo valor pode ser qualquer subconjunto de um conjunto de elementos do tipo T

o tipo de tais variáveis é o conjunto potência T

equivale ao conjunto de todos os subconjuntos de elementos do tipo T: tipo base

Operações permitidas união e interseção, pertence

Existe em PASCAL, não existe em “C”

Tipos do “C”

Não possui o tipo boolean

TRUE e FALSE

manipulados pelos operadores lógicos OR, AND, NOT

implementa-se normalmente da seguinte forma em “C”

enum { true = -1;

false = 0 }

false 0 já que o if (condição) no C executa o então quando condição diferente de 0

Tipos do “C”

Enumeração

typedef enum dia = {domingo, segunda, …}

define um conjunto e relações de ordem

domingo equivale a uma constante deste novo tipo

implementação: em um byte, limitado a 255, com valores associados de 0 em diante as constantes na ordem em que aparecem

é possível também atribuir valor às constantes

Tipos do “C”

Seu emprego aumenta legibilidade do código

Operações

atribuições e comparações

não podem ser usados em operações de entrada e saída

Os valores são mapeados em inteiros de 0 a n-1 sendo n a cardinalidade do tipo

Tipos do “C”

Ponteiros

Tipo_T * ponteiro

um ponteiro armazena um endereço

ponteiro = malloc (sizeof(Tipo_T))

aloco memória para uma estrutura do Tipo_T e coloco seu endereço no ponteiro

Tipos do “C”

Strings de Caracteres

trata cadeias de caracteres como vetores

char a[50], b[30]

utiliza funções para manipular strings

strcpy (a, “texto”)

strcmp(a,b)

strcat(a,b)

como em um string posso ter um número arbitrário de caracteres, o “C”utiliza um ‘\0’ como uma marca de fim de string

Tipos do “C”

Strings de Caracteres

CUIDADOS ESPECIAIS

char nome[5];

strcpy(nome, “Maria”)

M

A

R

I

A

\0

0

1

2

3

4

5

Compatibilidade de Tipos

typedef int intip[20] ;

int a [20], b[20];

int c[1..20]; // só em pascal.

intip d;

intip f;

Equivalência por nome (“C”)

mesmo nome de tipo, definido pelo usuário ou primitivo ou se aparecem na mesma declaração

são equivalentes: a e b ; d e f

Compatibilidade de Tipos

Equivalência estrutural

duas variáveis têm tipos compatíveis se possuem a mesma estrutura

segundo esta definição, nomes de tipos definidos pelo usuário são usados só como uma abreviatura (ou como comentário) da estrutura que representam

não introduzem uma nova característica semântica.

os nomes dos tipos devem ser substituídos pelas suas definições, repetindo-se o processo até não sobrarem mais nomes de tipos definidos pelo usuário

Controle a Nível de Instrução

Seqüência

Seleção

if (condição) comando else comando

switch ... case

Repetição

while (condição) comando

do comando while(condição)

for (i=0; i<N; i++) comando

Break

Subprogramas e Blocos

Controle a nível de unidades

Blocos:uma unidade de programa

substitui um comando da linguagem de programação

o bloco é iniciado em seqüência ao ser executada sua primeira instrução

define um ambiente local

Subprogramas e Blocos

Subprogramas:

também definem um ambiente local

definem um nível superior para a linguagem- um novo “comando”

dá o nome a uma determinada unidade de programa

sua chamada faz com que o controle seja transferido para a unidade chamada (primeira instrução) e executa até encontrar o fim da unidade (última instrução)

Subprogramas e Blocos

Main()

{

.......

A = Calculo()

A= A+1;

.......

}

Calculo()

{

1a. instrução

2a. instrução

.......

última instrução

}

1

última

Subprogramas e Blocos

Ao terminar devolve o controle para instrução seguinte à chamada

Fim do subprograma - devolve controle ao ponto de chamada

Parâmetros Formais

convenções para passagem de parâmetros. Permitem troca de informação explícita entre unidades

Subprogramas e Blocos

Onde as variáveis são declaradas?

dentro de funções: locais a função

variáveis locais

na lista de parâmetros das funções

parâmetros

fora de todas as funções

variáveis globais

Variáveis Locais

são variáveis automáticas

sua memória é alocada na entrada da execução da função e liberada na saída

normalmente são declaradas logo no início da função (após { ) e antes dos comandos

podem ser declaradas dentro de qualquer bloco de código (variáveis locais ao bloco)

Variáveis Globais

declaradas fora de qualquer função

podem ser usadas indiscriminadamente em qualquer função

a declaração pode ser colocada em qualquer lugar no programa fonte: deve ficar no início do arquivo, antes da declaração da main, mais fácil localizar

não é uma boa prática

Variáveis Globais

são globais àquela unidade de programa

para outro programa fonte devem ser declaradas com qualificador extern

Variáveis Locais X Globais

Variáveis locais com o mesmo nome de uma global: a referência prevalece a local

A

B

C

D

E

F

Variáveis Locais x Globais

Locais

são declaradas dentro de blocos e existem apenas enquanto o bloco está sendo executado

C: não existem enquanto o bloco não estiver executando, e desaparecem quando o bloco terminar sua execução

não é verdade para todas as linguagens

Variáveis Locais x Globais

Static

locais: memória da variável local alocada estaticamente

global: limita o escopo da variável a unidade de implementação

Código

Globais e Estáticas

HEAP

Pilha

Variáveis Locais x Globais

Globais: não são declaradas no bloco

são declaradas e existem para todo o programa

seu uso é perigoso, sua alteração pode causar efeitos colaterais em trechos completamente separados do programa

Variáveis Locais x Globais

Bloco

início de bloco: {

fim de bloco : }

{
<declaração de variáveis locais>
<comandos>
}

Parâmetros Formais

Subprograma é um segmento de programa com propriedades de comunicação com o mundo exterior

interface bem definida - parâmetros formais.

sua integração é realizada sem conhecimento de seus mecanismos internos

sua corretude é determinada sem considerações sobre onde está embutido

Parâmetros Formais

Função:

chamada com argumentos

parâmetros: variáveis que receberão os valores dos argumentos

se comportam como qualquer variável local dentro da função

is_in (nome, ‘M’)

Parâmetros Formais

int is_in (char *s, char c)

{ /* retorna 1 se c é parte da string s; 0 se não é o caso */

while ( *s )

if (*s == c) return 1;

else s++;

return 0;

}

Parâmetros Formais

Parâmetros formais  função (tipo nome, ...)

relação com argumentos: posicional

são usadas dentro da função como variáveis locais normais

também são dinâmicas: criadas na entrada, destruídas na saída

argumentos usados na chamada tem que ser do mesmo tipo dos parâmetros formais declarados

Parâmetros Formais

Parâmetros se comportam como variáveis locais

na ativação do subprograma sua área de memória é alocada

Passagem de parâmetros:

cópia:

referência

nome (quase não é usado)

Parâmetros Formais

Por Cópia:

de valor

o valor do argumento é copiado para a posição do parâmetros

não retorna a função chamadora

de resultado

como nome de função no PASCAL

não vem nada, só retorna para a chamadora

de valor resultado

cópia do valor do argumento na entrada e cópia do valor do parâmetros para o argumento no retorno

Parâmetros Formais

Por referência:

passa o endereço do argumento

seu valor se reflete no resultado

no parâmetro é colocado o endereço do argumento

endereçamento indireto

no C é implementado pelo programador

Alocação Dinâmica

Muitas linguagens também permitem lidar com objetos cujo tamanho pode variar dinamicamente.

nesse caso essas variáveis locais não podem ter sua memória alocada na ativação do subprograma.

Alocação Dinâmica

Estruturas de Dados Dinâmicas

podem ser modeladas por um conjunto de nós; que podem ser dinamicamente adicionados e removidos da estrutura

exemplo: listas encadeadas e árvores

os nós são ligados por ponteiros

Alocação Dinâmica

Variáveis criadas dessa forma:

em geral seu tempo de vida não termina quando o bloco acaba a execução (em geral)

as linguagens possuem comandos para alocação explícita desses blocos (malloc)

algumas linguagens possuem comandos para liberação explícita desses blocos(free)

outras (PASCAL) estabelecem que eles vivem enquanto existir uma referência para ele.

Alocação Dinâmica

Isso implica:

na possibilidade de criar vários desses objetos sem liberar nenhum deles

não podem ser criados na pilha.

Heap ou Zona de Acesso Indireto

nesta área as variáveis dinâmicas são alocadas

compartilha o crescimento da pilha

pilha

heap

dados

código

Alocação Dinâmica

O tamanho e número das variáveis dinâmicas podem variar dinamicamente durante seu ciclo de vida

Zona de acesso indireto

deve possuir uma lista de posições livres/ocupadas

o tamanho desta memória é limitado

Alocação Dinâmica

São variáveis anônimas

só são acessíveis através de seus endereços

variáveis do tipo ponteiro

cuidados especiais na programação

áreas de memória inacessíveis - perda de endereços

stack overflow

Ativação de um Subprograma

Linguagens de Programação permitem que programas sejam compostos de unidades de programas desenvolvidas, até certo ponto, independentes umas das outras

podem (normalmente) ser traduzidas em separado e combinadas após a tradução

variáveis declaradas dentro de uma unidade são locais a unidade

um subprograma pode ser ativado durante a execução de um programa

Ativação de um Subprograma

Ativação

sua representação durante sua execução

consiste de um segmento de código e registro de ativação

segmento de código

seu conteúdo é fixo durante a execução

contém as instruções da unidade

registro de ativação

seu conteúdo pode variar

contém toda informação necessária à execução da unidade

registro de ativação: endereço de retorno + parâmetros + variáveis locais

Ativação de um Subprograma

Conteúdo do Registro de Ativação

endereço de retorno

objetos associados às variáveis locais de uma ativação da unidade

argumentos associados aos parâmetros formais

A posição relativa de um objeto no registro de ativação é chamada deslocamento (offset)

para acessar um objeto, o processador pode usar o endereço inicial do registro de ativação que contém o objeto e o deslocamento do objeto

Programa

1 …..

2 …..

3 CALL A

4 …..

Subprograma A

1….

2….

3….

N …..

Ativação de um Subprograma

não são auto-contidas nem independentes do resto do programa

subprograma possui um nome: ativado por chamada

endereço de retorno diferente por chamada

Ativação de um Subprograma

Podem fazer referência a variáveis não declaradas localmente

essas variáveis são locais à unidade

Podem fazer referência a variáveis declaradas globais a unidades

forma depende da Linguagem de Programação

aninhamento de blocos

external

Ativação de um Subprograma

Seja U um subprograma, o Ambiente de Referência de uma ativação de U consiste de:

ambiente local: variáveis locais de U, amarradas a objetos guardados no registro de ativação de U ()

ambiente global: variáveis globais de U

podem estar amarradas a objetos guardados em registros de ativação de outras unidades ( como Pascal)

podem estar em uma área de acesso comum (área de globais) (linguagem C)

Ativação de um Subprograma

Conjunto de

Registros de Ativação

Variáveis Globais

Código das

Unidades de Programa

Registro de Ativação

Unidade U

Registro de Ativação

Unidade U’

Ativação de um Subprograma

Se U’ engloba U então:

ambiente de U’ global para U

no registro de ativação de U existe uma referência ao registro de ativação de U’

não existe na linguagem “C”

Ativação de um Subprograma

Unidades podem ser ativadas recursivamente (chamada da unidade pela própria unidade ou por outra chamada por ela)

Todas as ativações da mesma unidade são compostas pelo mesmo código e por registros de ativações diferentes

Quando existe recursão a amarração entre um segmento de código e seu registro de ativação é obrigatoriamente dinâmica

Registro de Ativação Estáticos

As variáveis locais são automaticamente criadas quando a unidade é ativada

a quantidade de memória necessária a cada uma delas é conhecida em tempo de tradução - PASCAL E C

O tamanho do registro de ativação e o deslocamento de cada variável são conhecidos em tempo de tradução

Registro de Ativação Estáticos

O tamanho do registro de ativação é estático, mas ele não pode ser amarrado estaticamente ao segmento de código da unidade

permitir ativações recursivas

precisa ser alocado e amarrado dinamicamente a cada ativação

em tempo de tradução uma variável pode ser amarrada somente a seu deslocamento dentro do registro de ativação da unidade

amarração a memória em tempo de execução

variáveis desta classe serão chamadas de semi-estáticas

Registro de Ativação Estáticos

Seja int A, uma variável local

Na tradução:

o endereço de A é conhecido em relação ao primeira posição do registro de ativação;

este endereço só será conhecido em tempo de execução;

referência a A é traduzida pela referência à posição inicial do registro de ativação + o deslocamento de A.

Registro de ativação

São alocados dinâmicamente

Permite:

recursividade

utilização mais eficiente da memória

Ao terminar a execução da unidade o Registro de Ativação é liberado

Pilha de Registros de Ativação

Registro de ativação

PROC(){

c = PROC1(…)

}

PROC1{

d = PROC2(…)

}

PROC

PROC1

PROC2

Registro de ativação

São alocados dinâmicamente

Permite:

recursividade

utilização mais eficiente da memória

O retorno de uma ativação de uma unidade de programa deve:

saber qual o endereço da próxima instrução a ser executada na unidade chamadora: endereço de retorno

qual o endereço de base do registro de ativação da unidade chamadora

Retorno a Unidade Chamadora

Endereço de retorno:

par (segmento da unidade de código que chamou, e deslocamento dentro desse segmento)

Registro de ativação corrente

endereço de base do registro de ativação da unidade em execução

após o término de execução o registro de ativação da unidade é desnecessário - memória liberada, disponível para outras unidades

a nova unidade corrente precisa ter o mesmo ambiente de trabalho anterior a chamada

Cadeia Dinâmica

Representa o aninhamento dinâmico de ativações de unidades

Durante a ativação de uma unidade

seu registro de ativação é alocado

neste registro é armazenada a referência a:

valor do “program counter”no instante da ativação da unidade

endereço do registro de ativação da unidade chamadora

este último é chamado de elo dinâmico

o conjunto de elos estáticos: cadeia dinâmica

Cadeia Dinâmica

Programa

1 …..

2 …..

3 CALL A

4 …..

Subprograma A

1….

2 CALL B

3….

N …..

Subprograma B

1….

2….

3….

M …..

RA

principal

RA

de B

RA

de A

Cadeia Dinâmica

Cadeia Dinâmica

O Registro de Ativação corrente é sempre o da última unidade chamada

Após seu término, este registro é desalocado

Estrutura de Dados apropriada a Registros de ativação:

pilha

na ativação: empilha o novo registro

ao final: desempilha o registro e passa a corrente o registro anterior da pilha

Pilha de Registros de Ativação

RA de

Principal

RA de

Principal

RA de A

RA de

Principal

RA de A

RA de B

RA de

Principal

RA de A

5

Registros de Ativação
Parâmetros Formais

int c,d;

void PROC(){

int b=5;

c = PROC1(b);

printf(“B=%d”, b);

}

int PROC1 (int a){

d = PROC2();

a = 6;

return (89); }

PROC2

PROC1

a

PROC

b

6

5

End. de b

Parâmetros Formais

int c,d;

void PROC(){

int b=5;

c = PROC1(&b);

printf(“B=%d”, b);

}

int PROC1 (int * a){

d = PROC2(…);

*a = 6;

return (9); }

PROC2

PROC1

a

PROC

b

5

6

Tratamento de Exceções

Eventos que ocorrem durante a execução podem ser classificados como usuais ou excepcionais

parâmetro inválido

erro em protocolo

overflow

estouro de capacidade de memória

Tratamento de Exceções

A ocorrência de uma exceção transfere o controle implicitamente para o tratador de exceção

o programa deve isolar o tratamento de eventos esperados e inesperados

unidades de programa tratam os eventos usuais e podem detectar a ocorrência de exceções

Recursividade

Um procedimento recursivo é aquele que contém uma ou mais chamadas a si mesmo

direta: o procedimento chama a si mesmo

indireta: A chama B que chama A

naturalmente existe pelo menos uma chamada externa: fora do próprio procedimento

Recursividade

Um procedimento não recursivo é aquele que só possui chamadas externas

A todo procedimento recursivo corresponde um outro, não recursivo, que executa exatamente a mesma computação

Recursividade

Freqüentemente, os programas recursivos são mais concisos

muitas vezes é aparente a relação direta com a prova por indução matemática

mas muitas vezes existem desvantagens no emprego prático da recursividade

o não recursivo é mais eficaz - tempo de execução e memória

Recursividade

Cálculo de fatorial

x! = se x <=0 1 senão x * (x-1)!

Implementação não recursiva

int fatorial (int N)

{	int i,result = 1;

for (i=1; i<=N; i++)

result = result * i;

return (result);}

Recursividade

Implementação recursiva

int fatorial (int N)

{

if (N<= 1)

return(1);

else

return( N * fatorial(N-1));

}

Recursividade

X= fatorial (4)

return( 4* fatorial(3) )

return( 3* fatorial(2) )

return( 2* fatorial(1) )

return( 1 )

Recursividade

Problema da Torre de Hanói

3 pinos: A - origem , B- destino , C - trabalho

Situação inicial: todos os discos no pino de origem em ordem decrescente de tamanho de baixo para cima

Objetivo: empilhar todos os pinos no destino

Restrições:
a) apenas um disco é movido por vez
b)nenhum disco pode ser colocado sobre outro de tamanho menor

Recursividade

Solução:

Para n>1, o pino de trabalho é usado como armazenamento temporário

Se sei resolver o problema para n então sei resolver para n+1

resolver o problema para n-1 do topo da origem colocando destino como C e trabalho como B

mover o n-ésimo pino para B.

Resolver o problema de C (como origem) para B(destino), usando A como trabalho.

Recursividade

Void hanoi (int n, char origem,
char destino, char trabalho)

{ if (n>0)

{	hanoi (n-1, origem, trabalho, destino);

mover(origem, destino);

hanoi (n-1, trabalho, destino, origem);

}

}

Complexidade de Algoritmos

Uma característica muito importante de qualquer algorítmo é seu tempo de execução

é possível determiná-lo através de métodos empíricos, considerando-se entradas diversas

é também possível obter este tempo a partir de métodos analíticos

Complexidade de Algoritmos

Métodos analíticos

objetivo: determinar uma expressão matemática que traduza o comportamento de tempo de um algoritmo.

Aferir o tempo de execução independente:

do método utilizado

da linguagem e compiladores empregados

e das condições locais de processamento

Complexidade de Algoritmos

A tarefa de obter uma expressão matemática não é simples, mesmo considerando-se uma expressão aproximada

Várias simplificações são introduzidas

Complexidade de Algoritmos

Simplificações:

suponha que a quantidade de dados a serem manipulados pelo algoritmo seja suficientemente grande

algoritmos cujas entradas consistam em uma quantidade reduzida de dados nao serão considerados

Complexidade de Algoritmos

Simplificações:

somente o comportamento assintótico será avaliado

a expressão matemática fornecerá valores de tempo que são válidos apenas quando a quantidade de dados crescer o suficiente

não serão consideradas constantes aditivas ou multiplicativas na expressão considerada

a expressão matemática obtida será válida a menos de constantes

Complexidade de Algoritmos

Qual a variável em relação à qual a expressão matemática avaliará o tempo de execução?

Um algoritmo funciona a partir de uma entrada para produzir uma saída dentro de um tempo  o que se deseja avaliar

 a idéia é fornecer o tempo de execução em função da entrada

Complexidade de Algoritmos

O processo de execução de um algoritmo pode ser dividido em etapas elementares  passos

um número fixo de operações básicas cujo tempo de execução é considerado constante

a operação básica de maior freqüência de execução do algoritmo é denominada operação dominante

Complexidade de Algoritmos

Como a expressão de tempo de execução será obtida a menos de constantes aditivas e multiplicativas:

o número de passos de um algoritmo pode ser interpretado como sendo o número de execuções da operação dominante

Complexidade de Algoritmos

Por exemplo:

algoritmos para ordenar os elementos de uma seqüência dada

cada passo corresponde a comparação entre dois elementos da seqüência

O número de passos de um algoritmo constitui a informação de que se necessita para avaliar seu comportamento no tempo

um algoritmo de um único passo possui tempo de informaçao constante

Complexidade de Algoritmos

A expressão matemática de avaliação do tempo de execução de um algoritmo é:

a função que fornece o número de passos efetuados no algoritmo a partir de uma certa entrada

Exemplo:

um algoritmo onde cada entrada é uma seqüência que se deseja inverter

Complexidade de Algoritmos

Inversão de uma seqüência

fim = n/2;

for (i=0; i<fim; i++)

{	temp = S[i];

S[i] = S[n-1-i];

S[n-1-i] = temp;}

Complexidade de Algoritmos

n = 5  troco S[i] por S[n-1-i]

fim = 2

i = 0  troco S[0] por S[5-1-0] - S[4]

i = 1  troco S[1] por S[5-1-1] - S[3]

inicial final

M

A

A

R

I

0

4

1

2

3

A

M

I

R

A

0

4

1

2

3

Complexidade de Algoritmos

n = 6  troco S[i] por S[n-1-i]

fim = 3

i = 0  troco S[0] por S[6-1-0] - S[5]

i = 1  troco S[1] por S[6-1-1] - S[4]

i = 2  troco S[2] por S[6-1-2] - S[3]

inicial final

E

D

S

T

A

0

4

1

2

3

O

S

D

A

T

0

4

1

2

3

O

5

E

5

Complexidade de Algoritmos

n = 50  troco S[i] por S[n-1-i]

fim = 25

i = 0  troco S[0] por S[50-1-0] - S[49]

i = 1  troco S[1] por S[50-1-1] - S[48]

i = 2  troco S[2] por S[50-1-2] - S[47]

.........

i = 23  troco S[23] por S[50-1-23] - S[26]

i = 24  troco S[24] por S[50-1-24] - S[25]

Complexidade de Algoritmos

Este algoritmo executa extamente as mesmas operações para seqüências de tamanho n

cada passo corresponde à troca de posição entre dois elementos da seqüência

isto é: a execução das três atribuições

o número de passos é igual ao número de vezes que executa o bloco for  n/2, n>1

Complexidade de Algoritmos

Considere o problema de determinar a soma C e o produto D de duas matrizes dadas - A e B.

A = (aij) e B = (bij) ambas n x n

C e D também serão matrizes n x n

seus elementos podem ser calculados como:  cij = aij + bij e
 dij = aik * bkj
1k  n

Complexidade de Algoritmos

typedef int tmatriz[n][n];

tmatriz a,b,c,d;

Soma

for(i=0; i<n; i++)

for(j=0; j<n; j++)

c[i][j] = a[i][j] + b[i][j];

Complexidade de Algoritmos

Produto

for(i=0; i<n; i++)

for(j=0; j<n; j++) {

c[i][j] = 0;

for(k=0; k<n; k++)

c[i][j] = c[i][j] + a[i][k] * b[k][j];

}

Complexidade de Algoritmos

Como no 1o.caso, ambos os algoritmos efetuam as mesmas operações sempre que A e B forem matrizes n x n

A variável independente é o parâmetro n

Cada passo do algoritmo de soma equivale à execução de aij + bij

Cada passo do algoritmo de produto equivale à execução de aij * bij

Complexidade de Algoritmos

Soma: o número total de passos é igual ao número total de somas

Produto: o número total de passos é igual ao número total de produtos

Soma: efetua n2 passos

Produto: efetua n3 passos

Complexidade de Algoritmos

A noção de complexidade de tempo é:

Seja A um algoritmo, {E1, ....Em} o conjunto de todas as entradas possíveis de A

Denote por ti o número de passos efetuados por A, quando entrada for Ei

Complexidade do pior caso: max Ei  E {ti }

Complexidade do melhor caso: min Ei  E {ti }

Complexidade de Algoritmos

Complexidade do caso médio:  1i  m piti

pi é a probabilidade de ocorrência da entrada Ei

De forma análoga podem ser definidas complexidades de espaço de um algoritmo

complexidade tem por objetivo avaliar a eficiência de tempo ou espaço

Complexidade de Algoritmos

Complexidade de tempo do pior caso corresponde ao número de passos que o algoritmo efetua no seu pior caso de execução

para a entrada mais desfavorável

é a mais importante das três mencionadas

fornece um limite superior para o número de passos

Complexidade de Algoritmos

Complexidade de tempo do pior caso

é a mais utilizada

o termo complexidade será empregado com o significado de complexidade de pior caso.

Complexidade de melhor caso é de uso bem menos freqüente- apenas algumas situações específicas

Complexidade de Algoritmos

Complexidade de caso médio é menos utilizada apesar de importante

normalmente, não se conhece a distribuição de probabilidades das diferentes entradas

seu cálculo é de tratamento matemático complexo

A notação 

Complexidade

desprezar constantes aditivas ou multiplicativas

número de passos 3n será aproximado para n

interesse assintótico - termos de menor grau podem ser desprezados: n2 + n será aproximado para n2

6n3 + 4n - 9 será aproximado para n3

usaremos operadores matemáticos para representar estas situações

A notação 

Complexidade

os operadores ,  e  serão utilizados

Sejam f e h funções reais positivas da variável inteira n

f =  (h), quando existir uma constante c> 0 e um valor inteiro no tal que

n > no  f(n)  c.h(n)

A notação 

A função atua como um limite superior assintótico da função f

f = n2 -1		f = (n2)

f = n3 -1		f = (n3)

f = 403		f = (1)

f = 5+2logn +3log2n		f = (log2n)

f = 5*2n +5*n10		f = (2n)

A notação 

As seguintes notações são úteis para manipular expressões em notação 

decorrem diretamente da definição

Sejam g e h funções reais positiva e k uma constante

(g+h) = (g) + (h)

(k*g) = k (g) = (g)

A notação 

A notação  será utilizada para exprimir complexidades

O algoritmo de inversão:

o número de passos se mantém o mesmo para o mesmo valor de n

variável independente é n

as complexidades de médio, melhor e pior casos são iguais

A notação 

Para a inversão

efetua sempre n/2 passos então sua complexidade é (n)

Para a soma e o produto de matrizes n x n verifica-se complexidades

(n2) e (n3) respectivamente

A notação 

Para procedimentos recursivos pode-se aplicar a seguinte técnica

determina-se o número total de chamadas ao procedimento recursivo

calcula-se a complexidade de execução de uma única chamada

não se considera as chamadas recursivas encontradas

complexidade total = produto do número de chamadas pela complexidade da computação isolada

A notação 

Torre de Hanoi - (2n)

A notação 

Algoritmos que não efetuam o mesmo número de passos para entradas diferentes do mesmo tamanho

Exemplo:

duas matrizes A e B de dimensões n x n e um parâmetro x, com valores possíveis 0 e 1

dependendo do valor de x deve-se calcular a soma ou o produto das matrizes

A notação 

x = 0, calcular A + B

x = 1, calcular A . B

entrada: n2+1 informações - tamanho (n2)

se x = 0 então soma de complexidade (n2)

se x = 1 então produto de complexidade (n3)

(n2) fornece complexidade do melhor caso e

(n3) fornece complexidade do pior caso

A notação 

A complexidade do caso médio, seja q a probabilidade de que x = 0 então:

q*n2 +(1-q)*n3

Embora seja teoricamente possivel a construção de computadores especiais capazes de executar programas em uma linguagem de programação qualquer, hoje em dia os computadores existentes executam apenas em linguagem de baixo nível - LINGUAGEM DE MÁQUINA
(Máquinas Multinível)

Linguagens de Máquina: são projetada em função da rapidez de execução dos programas, do custo da sua implementação e da flexibilidade com que permitem a construção de programas de nível mais alto

Embora seja teoricamente possivel a construção de computadores especiais capazes de executar programas em uma linguagem de programação qualquer, hoje em dia os computadores existentes executam apenas em linguagem de baixo nível - LINGUAGEM DE MÁQUINA
(Máquinas Multinível)

Linguagens de Máquina: são projetada em função da rapidez de execução dos programas, do custo da sua implementação e da flexibilidade com que permitem a construção de programas de nível mais alto

As ações indicadas pelos comandos da linguagem são diretamente executadas

Para executar cada ação existe um subprograma - escrito na linguagem de máquina do computador hospedeiro

A interpretação de um programa é feita pela chamada daqueles subprogramas em seqüência apropriada

INTERPRETADOR:

1. Obter o próximo comando do programa

2. Determinar que ações devem ser executadas

3. Executar essas ações

Esta seqüência é bastante semelhante àquela executada por computadores tradicionais:

1. Obter a próxima instrução (PC)
2. Incrementar o PC
3. Decodificar a instrução

4. Executar a instrução

A interpretação pode ser encarada como a simulação de um computador hospedeiro de uma máquina especial cuja lingugem de máquina é de nível mais alto

Por exemplo:

subprogramas podem ser inicialmente traduzidos para Assembly	- compilador

depois este é traduzido para código relocável, em linguagem de máquina	- montador

unidades de código relocável podem ser ligadas em uma única unidade relocável	- linkeditor

o programa inteiro é carregado na memória principal como um código executável	- loader

Em alguns casos, a máquina hospedeira geradora de código é diferente daquela onde o código é executado (máquina objetivo ou máquina alvo) - TRADUÇÃO CRUZADA

A interpretação pura e a tradução pura são dois extremos. Na prática muitas linguagens são implementadas por combinações dessa técnicas

Um programa pode ser traduzido para um código intermediário que é então interpretado

Esse código intermediário pode ser simplesmente: representação formatada de onde foi removida informação irrelevante

suprimir comentários

armazenar o comando em tamanhos fixos para facilitar a busca de instruções

Esta opção seria basicamente interpretativa. No entanto, o código intermediário poderia ser código de máquina (de baixo nível) de uma máquina virtual que seria depois interpretada por programas ( mais facilmente transferível para outras máquinas)

Em solução puramente interpretativa

a execução de um comando pode requer um processo de decodificação bastante complicado (determinar operações a serem executadas e seus operandos);

na maioria dos casos, a decocificação é executada cada vez que o comando é encontrado;

lento;

comados aparecem em loops; (decodificação idêntica => afeta desempenho)

Na tradução pura:

o código de máquina é gerado para cada comando de alto nível

o tradutor decodifica cada comando apenas uma vez

os componenetes usados com freqência são decodificados na sua representação em linguagem de máquina, várias vezes

economiza muito tempo de execução em relação a interpretação

gasta mais memória ( cada comando vira dezenas/centenas de instruções de máquina - na tradução ficam na forma original e chama subprograma que o interpreta).

Por outro lado, se todos os subprogramas do interpretador são mantidos na memória => programas pequenos desperdiçam memória

Esta opção seria basicamente interpretativa. No entanto, o código intermediário poderia ser código de máquina (de baixo nível) de uma máquina virtual que seria depois interpretada por programas ( mais facilmente transferível para outras máquinas)

Em solução puramente interpretativa

a execução de um comando pode requer um processo de decodificação bastante complicado (determinar operações a serem executadas e seus operandos);

na maioria dos casos, a decocificação é executada cada vez que o comando é encontrado;

lento;

comados aparecem em loops; (decodificação idêntica => afeta desempenho)

Na tradução pura:

o código de máquina é gerado para cada comando de alto nível

o tradutor decodifica cada comando apenas uma vez

os componenetes usados com freqência são decodificados na sua representação em linguagem de máquina, várias vezes

economiza muito tempo de execução em relação a interpretação

gasta mais memória ( cada comando vira dezenas/centenas de instruções de máquina - na tradução ficam na forma original e chama subprograma que o interpreta).

Por outro lado, se todos os subprogramas do interpretador são mantidos na memória => programas pequenos desperdiçam memória

Compilados separadamente, geram objetos e são linkeditados

Apenas 1 possui main ()

Um pode referenciar funções e variáveis globais de outro

Referências externas resolvidas pelo LINK

GOTO: obriga ao leitor do algoritmo a ir pulando para trás e para frente : aumenta a distância

a máquina convencional subjacente não possui proteção; por exemplo uma instrução, tb representada pro uma seqüência de bits pode ser somada c/ uma seqüência de caracteres - indesejável

Instruções para ler, escrever formatar saídas(interação dispositivos periféricos)

uso correto pode ser testado em tempo de tradução

testes estáticos não esgotam testes que podem ser feitos no pgm (divisão por zero por ex.)

detetar operadores ambíguos

LPs onde símbolos de operações podem ser usados para representar um grande número de operações

soma de reais ou soma de inteiros => torna a implementação mais eficiente

controle de precisão (long real, ..)

pode levar a sérias violações de tipos pq os ponteiros não sao qualificados pelo tipo de objeto que apontam

Em tempo de tradução é possível garantir que o ponteiro aponta p/ o tipo certo => não é feito em tempo de execução - caro.

=> supor que acesss feitos são corretos pelo compilador => em erros difíces de descobrir

2. ponteiro pode ficar pendurado => pode se referir a uma posição que nào está mais alocada

=> estouro do heap

=> para libera memória não usada no heap muitas implementações Pascal tem - dispose- que desaloca memória explicitamente.

=> pode-se requistar para liberar memória que ainda possuam apontadores para ela.

em linguagens fortemente tipadas (tipo resolvido estáticamente), não é necessário guardar os descritores em tempo de execução a referência a cada campo de um record é avaliada pelo tradutor

testes de tipo para registro com variantes só podem ser feitos em tempo de execução.

i.qtde é uma seleção correta se tiver true em seu campo de marca - disponível - Teste dinâmica requer que se tenha info. sobrea a variante atual em um descritor em tempo de execuçãopara cada reg. com variantes

infelizmente a possibilidade de alterar o campo de marca e os componentes variantes independentemente e de maneira inconsistente torna o teste em tempo de exeução difícil de implementar.

por exemplo, se o campo de marca é passado como parâmetro a um procedimento, oeste deveria atualizar o descritor a cada atribuição feita ao campo.porém o procedimento não sabae se est;a alterando um campo de marca a mesnos que um sinal seja passado para o procedimento

=> a implementação de registros com variantes equivale a sobrepor todas as variantes em uma mesma área de memória=> permite que o programador interprete a seqüência de bits armazenada nessa área segundo vários enfoques

=> é um uso inseguro

=> é útil para modelar algumas situações práticas(mensagens)

=> o campo de marca do registro é opcional

algumas ling (algol 68, ada e apl) => a[3.:5,5:12] => subvetor bidimensional c/ 24 elementos

1.	amarração em tempo de compilação: SUBCONJUNTO FIXADO QUANDO O PGM É ESCRITO -FORTRAN, C, PASCAL - variaveis estáticas e semi-estáticas

2.	amarração em tempo de criação:subconjunto fixado em tempo de execucão de criação de uma instância de variável -variáveis semidinamicas

3.	amarraçào em tempo de manipulação do objeto: vetores flexíveis - maior custo

=> típico de lps interpretativas: o tam. pode ser alterado em qq instante de seu tempo de vida

=> lps compiladas = ALGOL 68 e CLU => dinâmicas

EM PASCAL

array[tl]of t

tl -tipo dos índices: é um tipo ordinal / t - tipo das componentes(codomínio) - tripo de cada componenete do vetor

ex. pag 94=> PASCAL encara como sendo de tipos diferentes arrays com tipos de índices diferentes

a1 array [1..50] of integer

a2 array[1..70] of integer

=> procedures tem que possuir parâmetros formais de um tipo específico (compatível c/ o usado na chamada) => não é possível escrever procedimento para ordenar vetores c/ índices de tamanhos diferentes

em Pascal sào definidos por vetores cujos seus elementos são vetores

type linha : array [1..5 ]of integer

matriz array[1..10] of linha

=> tb permitido array[1..10, 1..5] of integer

·	type a = array [0..10] of real

·	fig 4.11 pag 126

·	como se pode indexar um vetor por meio de uma variável indexada, os limites devem ser guardados em um descritor de tempo de execução para efetur testes de limites

·	uma referência a(i) ér computada como um offset em relação ao endereço de a(1º componente) (no registro de ativação da unidade a qual o vetor é local)

·	linguagens que suportam vetores dinâmicos: descritor em uma parte estática e outra dinâmica. A parte estática contém informação que é usada em tempo de compilação (tipo dos componentes) e uma referência à parte dinâmica=> alocada em tempo de execução no reg. de ativação da unidade que declara o vetorc/ o offset conhecido em tempo de tradução. Contém referência ao objeto de informação do vetor (conhecido em tempo de execução) e os valores limites. seu acesso => acesso indireto através do descritor dinâmico.

Seqüencias

·	em PASCAl => cadeis são vetores compactados, seus comprimentos são estaticamente determináveis e não podem ser alterados (tem tamanho máximo)

·	em ADA => vetores dinâmicos, comprimento desconhecido em tempo de tradução, conhecido na unidade onde a cadeia é declarada

SONOBOL 4, ALGOL68 => são totalmente dinâmicas=> zona de acesso indireto

ver fig 4.12 pag 127 - representação de cadeia de comprimento variável.

=> descritor dividido em parte estática e parte dinâmica

·	parte dinâmica colocada na pilha de execução e contém comprimento atual da cadeia e refrência ao início

·	cadeia alocada no heap como uma lista encadeada de palavras cada palavra contendo um ou mais caracteres

valores de tipo enumerados não podem ser lidos ou escritos por um programa

para ler o valor de dia é necessário codificá-lo- inteiro e explicitamente transformá-lo

EM PASCAL:
definir subconjunto-intervalo de um tipo ordinal

type dia_útil = segunda..sexta

idade = 0..120

(esses tipos podem ser usados mesmo sem receber nome explícito)

varáveis de um tipo intervalo têm o mesmo comportamento de seu tipo_base, exceto quanto aos valores que pode assumir, subconjunto do tipo ordinal associado

=> verificação , teste em tempo de execução (ex. pag 94)

valores de tipo enumerados não podem ser lidos ou escritos por um programa

para ler o valor de dia é necessário codificá-lo- inteiro e explicitamente transformá-lo

EM PASCAL:
definir subconjunto-intervalo de um tipo ordinal

type dia_útil = segunda..sexta

idade = 0..120

(esses tipos podem ser usados mesmo sem receber nome explícito)

varáveis de um tipo intervalo têm o mesmo comportamento de seu tipo_base, exceto quanto aos valores que pode assumir, subconjunto do tipo ordinal associado

=> verificação , teste em tempo de execução (ex. pag 94)

Subprogramas e Blocos

As linguagens de programação fornecem meios para agrupar instruções implementando uma abstração de ação em uma unidade de programa apropriada

EXPLICAR

passagem de parâmetros formais

são ferramentas úteis para estruturar programas

ALGOL60 => fornece mecanismo de definir bloco sem nome= > portanto não pode ser invocado explicitamente sendo executado qdo encontrado

Subprogramas suportam a distinção entre a definição de uma ação abstrata ( o corpo) e seu uso (a chamada)

Comando static: ordena ao compilador que a área de memória associada a variável local static deva permanecer alocada durante toda a execução

C se caracteriza por ter variáveis locais automaticamente criadas quando suas unidades são ativadas

- o tamanho do registro de ativação ou é conhecido estaticamente ou qdo as unidades são ativadas

C se caracteriza por ter variáveis locais automaticamente criadas quando suas unidades são ativadas

- o tamanho do registro de ativação ou é conhecido estaticamente ou qdo as unidades são ativadas

C se caracteriza por ter variáveis locais automaticamente criadas quando suas unidades são ativadas

- o tamanho do registro de ativação ou é conhecido estaticamente ou qdo as unidades são ativadas

podem ser ligadas várias unidades em LPs diferentes (cuidados na forma de passagem de parâmetros)

Vamos estudar => mecanismos de elementares para controle de fluxo de execução entre unidades de programa e as amarrações que ocorrem quando uma unidade é ativada.

o registro de ativação deve possuir a próxima instrução a ser executada (ponto de retorno - end. de retorno) e o registro de ativação que deverá ser ativado após o retorno

ponto de retorno: par (segmento da unidade de código que chamou, e deslocamento dentro desse segmento)

o registro a ser ativado é representado por um ponteiro p/ o registro de ativação da unidade que chamou => elo dinâmico

a cadeia de elos que se origina no regsitro corrente ativo é chamada de cadeia dinâmica.

o registro de ativação deve possuir a próxima instrução a ser executada (ponto de retorno - end. de retorno) e o registro de ativação que deverá ser ativado após o retorno

ponto de retorno: par (segmento da unidade de código que chamou, e deslocamento dentro desse segmento)

o registro a ser ativado é representado por um ponteiro p/ o registro de ativação da unidade que chamou => elo dinâmico

a cadeia de elos que se origina no regsitro corrente ativo é chamada de cadeia dinâmica.

O pgm deve ser separado = tratamento de eventos esperados e inesperados => unidades de programa tratam os eventos usuais e podem detectar a ocorrência de exceções

A ocorrência de uma exceção transfere o controle implicitamente para o tratador de exceção

As Lps tradicionais proveem pouco no tocante às exceções

Um subprograma que pode causar uma exceção pode ter um código adicional de retorno que indica condição normal/anormal de fim de execução. A unidade que o chama deve testar explicitamente a condição de retorno e então transferir o controle para o subprograma que trata exceção=> obscurece a lógica do programa

O pgm deve ser separado = tratamento de eventos esperados e inesperados => unidades de programa tratam os eventos usuais e podem detectar a ocorrência de exceções

A ocorrência de uma exceção transfere o controle implicitamente para o tratador de exceção

As Lps tradicionais proveem pouco no tocante às exceções

Um subprograma que pode causar uma exceção pode ter um código adicional de retorno que indica condição normal/anormal de fim de execução. A unidade que o chama deve testar explicitamente a condição de retorno e então transferir o controle para o subprograma que trata exceção=> obscurece a lógica do programa

Algoritmos e Estruturas de Dados Programa do Curso

uso geral

2000-03-20T14:42:54