terça-feira, 26 de fevereiro de 2008

PDA - Aula 05: Operadores e Expressões 1

* Esta obra é uma adptação do autor desse blog da disciplina de Fundamento de Algoritmo para Computação do curso de Tecnologia em Sistemas de Computacão/Cederj UFF das aulas originais cujo os autores são: Adriano Cruz e Jonas Knopman.

Índice


1. Objetivos
2. O que são Expressões?
3. Constantes
4. Tipos de Operadores
5. Operadores Aritméticos
6. Expressões Aritméticas
7. Bibliografia

1. Objetivos
  • Apresentar os diversos tipos de operadores e expressões.
  • Mostrar como as expressões devem ser escritas em pseudo-código.
  • Mostrar as regras de avaliação de expressões.
  • Apresentar o conceito de atribuição de resultados.
2. O que são Expressões?
  • Expressões combinam variáveis, operadores e constantes para produzir um resultado.
  • Variáveis são nomes usados para representar posições na memória onde estão dados que serão processados.
  • Constantes são símbolos usados para representar dados.
  • Operadores são usados para combinar as variáveis e constantes fornecendo um valor como resposta.
  • Notar que as regras variam de linguagem para linguagem de programação.
  • O conjunto de regras definido para este pseudo-código permite que o programador mude facilmente para outra linguagem de programação.
Exemplos de Expressões
  • 0.5 * base * altura
  • (nota1 + nota2) / 2.0
  • (temperatura > 0) e (quantidade <>
  • 4 mod 3 + 5
  • A > B
Observações nas Expressões
  • Observar que as expressões são escritas sempre em uma mesma linha.
  • Observar os símbolos usados para multiplicação (*) e divisão (/).
  • Avaliar primeiro as operações de maior prioridade, por exemplo (multiplicação e divisão).
  • Se temos de escolher entre operadores de mesma prioridade então escolher o que está mais à esquerda.
  • Ex. 4/2*3 -- primeiro divide-se 4 por 2 e em seguida multiplica-se o resultado por 3, dando como resultado 6
  • Caso queira trocar a prioridade use parênteses.
  • Não são permitidos outros símbolos para esta função tais como { } e [ ].
3. Constantes
  • Constantes aparecem em expressões do tipo
  • (lado1 + lado2) / 2
  • Nesta expressão temos a variável lado1 somada à variável lado2 e o resultado dividido pela constante 2.
  • Cada variável representa uma posição de memória.
  • As constantes são armazenadas junto com o código do programa, não ocupando espaço da área onde estão os dados.
  • Constantes podem ser do mesmo tipo que os dados que já estudamos e devem ser representados do mesmo modo.
  • Constantes podem ser dos seguintes tipos:
.: Inteiras
.: Reais
.: Caracteres
.: Cadeias de caracteres
  • Constantes inteiras como já visto para os dados inteiros têm o seguinte formato:
.: Inteiro = [‘+’ | ‘-’]algarismo{algarismo}
  • Exemplos de constantes inteiras:
+256
128
-32768
555
-12345
  • Constantes reais, também como já visto para os dados reais têm o seguinte formato:
Real =
[‘+’ | ‘-’]algarismo{algarismo}.algarismo{algarismo}
  • Exemplos de constantes reais:
3.141516
-22.354
+0.567
128.0
  • Constantes do tipo caractere serão representadas em nossos algoritmos pelo caractere entre ‘s.
  • Exemplos de constantes caractere são:
‘a’
‘0’
‘+’
‘ ’
‘A’
‘@’

  • Constantes cadeias de caracteres são conjuntos de caracteres e também devem ser representados entre ‘s.
  • Exemplos de cadeia de caracteres são:
‘Projeto de sistemas’
‘Pedro Silva’
’125’
‘Onde ela foi?’
  • Constantes do tipo lógica serão representadas em nossos algoritmos por verdadeiro e falso
4. Tipos de Operadores
  • Operadores são símbolos que indicam a operação que deve ser realizada entre os operandos (constantes e/ou variáveis).
  • Exemplos de operadores são: + e -
  • De acordo com o número de operandos envolvidos na expressão, os operadores podem ser classificados em:
.: Binários, quando atuam sobre dois operandos. Exemplo: soma
nota1 + nota2

.: Unários, quando modificam um único operando: Exemplo: sinal de –
-352
  • Operadores também podem ser classificados de acordo com o tipo dos operandos envolvidos.
  • De acordo com esta classificação os operadores podem ser divididos em:
.: Aritméticos, quando os operandos são dados aritméticos.
.: Exemplos:

a + b

4.0 * raio

.: Lógicos, quando os operandos são dados lógicos.

.: Exemplos:

optou ou saiu

maior e aprovado

não terminou

.: Relacionais, quando comparamos dados de tipos compatíveis e o resultado é um valor lógico.

Exemplos:

a > 10

x < -1 .: Caracteres, quando os operandos são dados do tipo caractere. .: Este tipo de operador não é padronizado e varia de linguagem para linguagem. .: Em nosso estudo não utilizaremos nenhum operador de caractere.
.: Um exemplo de operação comum em várias linguagens é a concatenação de duas cadeias de caracteres.

.: Símbolo + é usado em algumas linguagens para representar esta operação.

.: Considere as cadeias ‘dia’, ‘ ’, ‘de’ e ‘semana’

.: A operação

‘dia’ + ‘ ’ + ‘de’ + ‘ ’ + ‘semana’

.: cria a cadeia

‘dia de semana’

5. Operadores aritméticos



6. Expressões Aritméticas
  • Resultado é um valor numérico.
  • Os operadores aritméticos mostrados na tabela anterior estão classificados por prioridade.
  • Números baixos indicam maior prioridade, operações que devem ser executadas primeiro.
  • Os símbolos para multiplicação e divisão mostrados na tabela são os únicos permitidos na maioria das linguagens.
Expressões Aritméticas Representação



  • Não existem operações implícitas como em 4ac, que significa 4 vezes a vezes c.
  • A solução deve ser 4*a*c
  • Cuidado com expressões do tipo
  • A maneira correta é (a+b)/(c-d)‏
  • a + b / c – d equivale a


Observações nas Expressões Aritméticas
  • Expressões aritméticas que envolvem operandos inteiros fornecem resultados inteiros.
  • Expressões aritméticas que envolvem operandos reais fornecem resultados reais.
  • Em operações com dados de tipos diferentes (inteiro e real) os operandos são convertidos para o tipo real.
  • 1 / 4 – resultado 0
  • 1.0 / 4 – resultado 0.25
  • 1 / 4 + 7.1 – resultado 7.1
  • 1a. Operação: 1 / 4 = 0
  • 2a. Operacão: 0 + 7.1 = 7.1
  • (2 + 4)/(3 – 1) – resultado 3
    • 1a. Operação: 2 + 4 = 6
    • 2a. Operação: 3 – 1 = 2
    • 3a. Operação: 6 / 2 = 3

  • 10 mod 3 – resultado 1
.: O resto da divisão de 10 por 3 é igual a 1.

7. Bibliografia

dfaf

FAC - Aula 05: Indução Forte

Conteúdo:

1. Série de Fibonacci
2. Indução Forte
3. Indução Forte Generalizada
4. Questões de AD´s e AP´s
5. Bibliografia

1. Série de Fibonacci


????

segunda-feira, 25 de fevereiro de 2008

PDA - Aula 04: Variáveis

* Esta obra é uma adptação do autor desse blog da disciplina de Fundamento de Algoritmo para Computação do curso de Tecnologia em Sistemas de Computacão/Cederj UFF das aulas originais cujo os autores são: Adriano Cruz e Jonas Knopman.

Índice

1. Objetivos
2. Introdução
3. Modelo de Memória
4. Armazenamento de Dados Numéricos
  • Dados Inteiros
  • Dados Reais
5. Armazenamento de Dados Literais
6. Armazenamento de Dados Lógicos
7. Variáveis
8. Bibliografia

1. Objetivos
  • Apresentar o modelo de do computador
  • Mostras como os diversos tipos de dados são armazenados na memória do computador.
  • Apresentar o conceito de variável e sua utilidade no desenvolvimento de algoritmos.
2. Introdução
  • Variáveis são endereços de memória destinados a armazenar informações temporariamente.
  • Todo Algoritmo ou programa deve possuir variável!
  • Podemos classificar as variáveis em dois tipos as de Entradas e as de Saídas.
  • Variáveis de Entrada armazenam informações fornecidas por um meio externo, normalmente usuários ou discos.
  • Variáveis de Saída armazenam dados processados como resultados.
Exemplo:



  • De acordo com a figura acima A e B são Variáveis de Entrada e C é uma Variável de Saída.

3. Modelo de Memória
  • A memória é um conjunto ordenado de células, cada um identificada por um endereço.
  • A unidade mínima de informação na memória é o bit que consegue armazenar ou o valor 0 ou 1.
  • Um conjunto de 8 bits forma um byte.
  • Um conjunto de bytes, usualmente 4 (32 bits) forma uma palavra de memória.
Palavras e bytes

  • Usualmente uma palavra de memória é composta de 4 bytes.




  • A maioria das memórias são endereçadas por byte, portanto o endereço permite manipular o conteúdo de um determinado byte.
Memória e endereçamento
  • Memória com 2 - 1 palavras de 4 bytes.
  • Então n + 2 é o número de bits do endereço.
  • Podemos pensar cada byte como uma casa.
  • Uma palavra seria uma vila de casas.
  • A memória uma rua de vilas.
  • Suponha uma rua (memória) com 5 vilas (palavras), cada vila com 4 casas (bytes).
  • Temos endereços de casas indo de casa 0 até casa 19.
  • Temos endereço de vilas indo de vila 0 até vila 4.
  • Posso dar meu endereço como casa 6 ou casa 2 da vila 1.
  • Observar que 6 dividido por 4 (casas por vila) é igula a 1 com resto 2.
  • Em computação os endereços de memória começam sempre em 0.
Exemplo
  • Memória de 128 Mega (2?) bytes
  • Memória com 128 x 2 ? = 2? x 2 ? = 128 x 1.048.576 bytes
  • O endereço deve ter 27 bits
.: 7 bits devido aos 128 = 2 ?
.: 20 bits devido ao 2?
  • Se cada palavra de memória tem 4 bytes temos então 32 Mega palavras.
Bits e dados
  • Cada tipo de dado requer uma quantidade de bits para armazenar o valor.
  • Esta quantidade é variável e depende da linguagem e do computador.
  • Atualmente computadores típicos possuem memória com palavras de 32 bits, ou 4 bytes.
4. Armazenamento de Dados Numéricos

Armazenamento de Inteiros

  • O conjunto dos números inteiros ( Z = {..., -2, -1, 0, +1, +2, ...}) contém uma quantidade infinita de elementos.
  • Como o número de bits disponíveis na memória para armazenar os números é finito não é possível representar todos os números deste conjunto.
  • Considere uma palavra de 32 bits.
  • Um bit é reservado para o sinal.
  • O bit mais significativo está à esquerda e menos significativo à direita;
  • Um número interio i pode variar entre
- 2 ? <= i <= 2 ? = 1
-2.147.483.648 <= i <= 2.147.483.647
  • Como não temos + 0 e - 0, há um número negativo a mais que os positivos.
fig??

  • Observar que não podemos armazenar números maiores que 2.147.483.647 e menores que -2.147.483.648.
  • Isto pode ser contornado, em alguns casos, empregando-se os números reais que veremos em seguinda.
Armazenamento de Reais
  • Os números reais também são armazenados em 32 bits.
  • Estes números são, as vezes, chamados de números em ponto flutuante devido a forma como eles são processados.
  • O método é parecido com a notação científica que algumas calculadoras empregam.
Notação Científica
  • Os números em notação científica nas calculadoras são expressos por um número real normalizado multiplicado por um número elevado a uma potência.
  • Ex. 1,5 E + 8 = 1,5 X 10?
  • Um número normalizado implica que antes da vírgula somente deve aparecer um algarismo.
  • Ex. (5,0 E+8) + (6,0 E+8) = 11,0 E+8
  • Resultado final = 1,10 E+9
Armazenamento de Reais

O conjunto dos números reais contém uma quantidade infinita de elementos.
Como o número de bits para armazenar os números é finito não é possível representar todos os números deste conjunto.

Reais em bits
  • Considere uma palavra de 32 bits.
  • Um bit é reservado para o sinal.
  • Oito bits são reservado para o expoente.
  • A base do expoente depende do computador, normalmente 2.
  • Vinte e três bits são usados para o número real, chamado de mantissa.

fig. ??/

Quais números reais?

  • Computadores tem dificulade de armazenar os números reais muito grandes e os muito pequenos.
  • Os subconjunto dos números reais disponíveis pode ser representado como

fig???

  • O zero está incluído no conjunto.
  • Para uma palavra de 32 bits temos RMAX = 3.4 E + 38 e RMIN = 3.4 E -38
5. Armazenamento de Dados Literais

Armazenamento de caracteres

  • O código de caracteres normalmente empregado é o ASCII que precisa de 8 bits ou um byte.
  • Como os computadores endereçam a memória por bytes então é possível armazenar um caractere por byte.
  • Para armazenar um conjunto de caracteres normalmente se emprega um conjunto de bytes.
6. Armazenamento de Dados Lógicos

Valores Lógicos

  • Este tipo de dado somente possui dois valores verdadeiro e falso.
  • Portanto um bit é suficiente para armazenar estes dados.
  • Normalmente se usa um byte inteiro para armazenar valores lógicos devido a dificuldade de endereçar bits.
7. Variáveis
  • Diversos tipos de dados são armazenados na memória.
  • A memória é endereçada por meio de números.
  • Para procurar um determinado dado na memória seria preciso saber o número da palavra (ou byte) onde este dado está armazenado.
  • Este método seria complicado e ilegível.
  • Mais fácil empregar nomes como fazemos com as ruas de nossa cidade.
Nome de Variáveis
  • Variáveis receberão nomes.
  • Cada variável deve receber um nome diferente para poder ser identificada sem problemas.
  • Estes nomes deverão ser utilizados sempre que quisermos modificar ou saber o conteúdo de uma posição na memória do computador.
  • As regras para criação dos nomes das variáveis são as seguintes:
.: Um nome de variável pode conter letras, algarismos e o caracter_(sublinha);
.: Um nome de variável deve necessariamente começar por uma letra;
.: Um nome de variável não deve conter nenhum símbolo diferente de letras ou algarismo, exceto o símbolo_(sublinha)
.: Não existe limitação para o número de caracteres do nome;
.: Não será feita diferenciação entre letras maiúsculas e minúsculas.

Dicas
  • Escolher nomes significativos para as variáveis
.: P. Ex. salario, total, nota, pagamento
  • Nomes significativos ajudam a tornar os algoritmos e os programas auto-explicativos
  • Nomes de variáveis com mais de uma palavra podem ajudar também
  • Sempre as palavras por sublinhados
.: P. Ex. toal_pagamentos, prova_final
  • Não é necessário alongar desnecessariamente os nomes.
.: P. Ex. total_de_recebimentos_do_ano, variavel_nota
  • Evitar nomes que não ajudem o entendimento do algoritmo.
Exemplos de nomes corretos
  • soma
  • salario_total
  • nota_final
  • prova1
  • velocidade_inicial
Exemplos de nomes incorretos
  • soma$................$ não é permitido
  • salario total.......Espaço em branco não é permitido
  • 2prova...............Não começou por uma letra
  • Salario/hora...../não é permitido
Bibliografia

ss??



FAC - Aula 04: Princío da Indução Matemática

Módulo 02: Indução matemática

* Esta obra é uma adptação do autor desse blog da disciplina de Fundamento de Algoritmo para Computação do curso de Tecnologia em Sistemas de Computacão/Cederj UFF das aulas originais cujo as autoras são: Sulamita Klein e Susana Scheimberg de Makler.


Revisão em 28/fev/2008 19:29
Conteúdo:


Conteúdo:

1. Introdução

2. Princípio da indução matemática (PIM)


3. Princípio da indução matemática generalizada


4. Questões de AP´s e AD´s do Cederj


5. Bibliografia


1. Introdução

Idéia intuitiva:

Exemplo:

  • Consideremos uma sequência de dominós alinhados tal que: Se um cair ele vai derrubar o seguinte.

2. Princípio da indução matemática (PIM)

Formalização:
  • Seja P(n) uma afirmação, para cada n .
  • Se:
  • (i) P(1) verdadeira e
  • (ii) P(k) verdadeira P (k + 1) verdadeira k .
  • Então P(n) verdadeira para todo n
Para aplicarmos o PIM precisamos executar os três passos a seguir:

(1) Base da indução: Mostrar que P(n) verdadeira para n = 1

(2) Hipótese de indução: Assumir que P(k) verdadeira para k 1

(3) Passo indutivo:

Mostrar que P (k + 1) verdadeira, assumindo (2).

Exemplo:
  • Mostre que 1 + 2 + 3 + ... + n = k
Prova:
  • Seja P(n) : 1 + 2 + 3 + ... + n =
(1) Base da indução:
  • P ( 1 ): 1 = = 1 verdadeira
(2) Hipótese de indução (HI): Assuma que P (k) é verdadeira, k 1:
  • 1 + 2 + .... + k =
(3) Passo indutivo:
  • P (k) verdadeira P (k + 1) verdadeira







3. Princípio da indução matemática generalizada

  • Lembremos a formulas do PIM:
Seja P (n) uma afirmação, para cada inteiro positivo.

Se:

(i) P (1) verdadeira e
(ii) P (k) verdadeira
P (k + 1) verdade k .

Então P (n) verdadeira para todo n .

Para aplicarmos o PIM generalizado precisamos executar os três passos a seguir:

(1) Base da indução:
  • Mostrar que P (n) verdadeira para n = n0
(2) Hipótese de indução:
  • Assumir que P (k) verdadeira para k n0
(3) Passo indutivo:
  • Mostrar que P (k + 1) verdadeira, assumindo a hipótese de indução (2)
Exemplo:
  • Mostre que > 3n n k .
Prova:
  • Seja

4. Questões de AP´s e AD´s do Cederj

1) Cederj 2005/1 AD01 - Mostre usando indução matemática:

2 + 5 + 8 + ... + (3n - 1 ) = n

Resposta:

Por indução:

para n = 1, 3*1 - 1 = 2 =
= 2 é verdadeira

suponha verdadeira para n = k isto é, 2 + 5 + ... + ( 3k - 1 ) =


(Vamos mostrar que se é verdadeira para k
verdadeira para k + 1)

Desenvolvendo para n = k + 1



Logo a expressão é verdadeira
n

2) Cederj 2005/2 AD01
- Mostre usando indução matemática:



Resposta:

Prova:



Por indução:


Base da indução:




Hipótese indução:

Suponha verdadeiro para n = k, isto é , P ( k ) é verdadeira:



Vamos mostrar que se P ( k ) é verdadeiro então é P ( k + 1 ) é verdadeiro, isto é:


Temos que provar que:

Desenvolvendo para n = k + 1 e usando a hipótese de indução, temos que:



Logo a expressão é verdadeira n

3) Cederj 2006/1 AD01 - Mostre usando indução matemática:

Resposta:





Logo, pelo princípio da indução, a expressão é verdadeira n

4) Cederj 2006/2 AD01 - Use o Princípio da Indução matemática para provar que:

Resposta:



Resposta:



Base da indução:



Hipótese de Indução:

Suponha verdadeira para n = k, isto é, P ( k ) é verdadeira:



Passo da indução:


Vamos mostrar que se P ( k ) é verdadeiro então P ( k + 1 ) é verdade, isto é,

temos que provar que: P ( k + 1 ) = é

verdadeira. De fato,



Logo, pelo princípio da indução, a expressão é verdadeira
n

5) Cederj 2007/2 AP01 - Mostre por Indução Matemática que:

n ( n + 1 ) > 4 n para todo natural n
4.

Resposta:

Seja P ( n ) : n ( n + 1 ) > 4n, n , n 4

a) Base da indução:

Para n = 4, 4 ( 4 + 1 ) = 20 > 16 = 4 . 4 , logo P ( 4 ) é verdadeira.

b) Hipótese de Indução:

Suponha verdadeira para k 4, isto é, P ( k ) é verdadeira, para k 4:

P ( k ) : k ( k + 1 ) > 4 k

Passo da Indução:

Vamos mostrar que se P ( k ) é verdadeiro então P ( k + 1 ) é verdadeiro, isto é, temos que provar que:

P ( k + 1 ) : k + 1 ( ( k + 1 ) + 1 ) = ( k + 1 ) ( k + 2 ) = k ( k + 1 ) + 2 ( k + 1 ) ......



5. Bibliografia


http://pt.wikipedia.org/wiki/Indu%C3%A7%C3%A3o_matem%C3%A1tica

http://www.cepa.if.usp.br/e-calculo/ferramentas/pif/pif.htm

http://www.e-escola.pt/site/topico.asp?topico=5&ordem=3&canal=4