segunda-feira, 10 de março de 2008

FAC - Aula 06: Princípios Aditivo e Multiplicativo

Módulo: 03

Índice:

1. Objetivos
2. Importância
3. Princípio Aditivo
4. Princípio Multiplicativo
5. Extensão do Princípio Aditivo
6. Extensão do Princípio Multiplicativo
7. Bibliografia

1. Objetivos
  • Apresentar as idéias e técnicas básicas para resolver problemas de contagem.
  • Dividir um problema grande a vários problemas pequenos, usando os Princípios Aditivos e Multiplicativo.
2. Importância
  • Os problemas de contagem estão inseridos naturalmente na nossa vida diária.
  • Em alguns casos estamos apenas interessados em contar os elementos de um determinado conjunto, sem enumerá-los.
  • No desenvolvimento de técnicas de contagem que serão abordadas nas aulas posteriores, tais como: permutações, combinações, etc. estaremos usando basicamente os Princípios Aditivo e Multiplicativo.
3. Princípio Aditivo
  • Princípio Aditivo (para dois conjuntos)
  • Se A e B são dois conjuntos disjuntos (A ? b = ?), então n (A ? B) = n (A) + n(B)
  • Outra notação usual

4. Princípio Multiplicativo
  • Este princípio lida com situações em que uma tarefa se divide em várias etapas. Vamos ver um exemplo.
  • Uma pessoa mora em Nova Iguaçu e trabalha em Copacabana. Ela vai trabalhar todos os dias usando apenas transporte coletivo. Esta pessoa vaia de Nova Iguaçu ao Centro do Rio tomando ônibus, van ou trem. Do Centro do Rio, pode ir a Copacabana de ônibus, van ou metrô. Levando em conta apenas estas possibilidades, de quantas maneiras ele poderá ir de cada ao trabalho?
  • inserir figura
  • Neste caso podemos contar facilmente todas as 9 possibilidades:
  • {(V,


5. Extensão do Princípio Aditivo

6. Extensão do Princípio Multiplicativo

7. Bibliografia

sábado, 1 de março de 2008

PDA - Aula 07: Desvios Condicionais

* 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.

Conteúdo:
  1. Objetivos
  2. Comando de desvio
  3. Comando de desvio aninhado
1. Objetivos
  • Apresentar o comando de desvio
  • Apresentar o funcionamento dos comandos de desvio aninhados
2. Comando de desvio
  • Permite que o algoritmo decida autonomamente entre dois caminhos possíveis, qual irá executar.
Traga a cesta com as batatas Se a roupa é clara então coloque avental Fim se Descasque as batatas

Bloco de comandos
  • Os comandos na nossa linguagem são escritos um por linha
  • Não há nenhum sinal de pontuação ao final da linha
  • Um bloco de comandos é uma série de comandos
  • Em um bloco ou todos os comandos são executados ou nenhum é.
leia n1, n2
media <- (n1+n2)/2 imprima 'A média vale ', media

Fluxograma do desvio
  • Somente um dos blocos de comando é executado.


se então bloco de comandos 1 senão bloco de comandos 2 fim se

Comando se simplificado
  • Caso o bloco de comandos depois do senão seja vazio, esta parte pode ser omitida
  • A forma geral simplificada é:
se então bloco de comandos fim se

Fluxograma se simplificado
  • Neste caso o bloco de comandos é executado somente se a condição for verdadeira
  • Caso contrário o algoritmo prossegue normalmente


início
acorde
se estiver fazendo sol então
vai à praia
senão
lê jornal
dorme
acorda
fim se
almoça
fim

Sequencia de ações

Se estiver fazendo sol
acorda
vai à praia
almoça

Senão
acorda
lê jornal
dorme
acorda
almoça

Exemplo algoritmo

Ler dois números e imprimir o maior
início
imprima 'Primeiro número?'
leia num1
imprima 'Segundo número?'
leia num2
se num1 > num2 então
imprima 'O maior é ', num1
senão
imprima 'O maior é ', num2
fim se
fim

Comando se aninhado
  • As duas formas do comando se podem aparecer dentro de outros comando se.
  • Diz-se que o comando se interno está aninhado no comando se externo.

se estiver sol então
se eu tiver dinheiro então
Vou à praia
fim se
fim se

  • Como o computador liga um fim se a um se?
  • A indentação não é significativa para os compiladores!
  • O fim se estará relacionado com o se mais próximo.
Usando comando se aninhado
  • Observe as seguintes construções:
se estiver sol então
se eu tiver dinheiro então
vou à praia
fim se
fim se
ou
se estiver sol e
eu tiver dinheiro
então
vou à praia
fim se
  • As duas construções são equivalentes. Então, quando usar comandos aninhados?
Quando usar comando aninhado?

  • Quando tivermos de executar blocos de comandos diferentes para a cláusula senão das duas condições.

se estiver sol então
se eu tiver dinheiro então
Vou à Fazenda Felicidade
senão
Vou à praia
fim se
senão
Vou dormir
fim se

Como construir sem aninhamento?

  • Construir o exemplo anterior sem aninhamento.
  • Construir o exemplo anterior sem aninhamento.

se estiver sol e tiver dinheiro então Vou à Fazenda Felicidade
fim se

se estiver sol e não tiver dinheiro
então Vou à praia
fim se

se não estiver sol então
Vou dormir
fim se

Um exemplo

  • Exemplo: Uma empresa vai dar um abono aos empregados que tenham mais de 1 ano de casa: 10% para os que tenham menos de 10 anos e 25% para os demais. Calcule o abono de um dado funcionário, dado o seu salário e o tempo de casa




Exemplo: Solução

início
imprima 'Entre com o salario: '
leia salario
imprima 'Entre com o tempo de servico:'
leia tempo
se tempo > 1 então
se tempo < style="font-weight: bold;">Outro exemplo

  • Sistema de controle de temperatura

PDA - Aula 06: Operadores e Expressões 2

* 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.

Conteúdo:
  1. Objetivos
  2. Operadores Relacionais
  3. Expressões Relacionais
  4. Operadores Lógicos
  5. Expressões Lógicas
  6. Expressões Mistas
  7. Atribuição
  8. 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. Operadores Relacionais
  • Usados para fazer comparação entre dados compatíveis.

  • O resultado de uma expressão que envolve operadores relacionais é do tipo lógico (verdadeiro ou falso).
  • No curso do PDA Cederj/UFF são considerados que os operadores deste grupo têm a mesma prioridade entre si.
3. Expressões Relacionais
  • Considere a=3, b=7, total=200.0, média=8.1 e ano=2000
  • a > b -- resultado falso
  • total = 100.0 -- resultado falso
  • média >= 7.0 -- resultado verdadeiro
  • ano <> 2001 -- resultado verdadeiro
Exemplos:
  • Considerando a=3, b=7, t=20.0 e m=8.1 qual o resultado das expressões?
  • t <> 100.0
  • (m + b) <= 7.0
  • (t/(b+a)) = 2.0
Solução
  • Temos a=3, b=7, t=20.0 e m=8.1.
  • t <> 100.0 -- resultado verdadeiro
  • (m + b) <= 7.0 -- resultado falso
  • 1a. Operação m+b = 15.1
  • 2a. Operação 15.1 <= 7.0 resultado falso
  • Temos a=3, b=7, t=20.0 e m=8.1.
  • (t/(b+a)) = 2.0
    • 1a. Operação: b+a = 10
    • 2a. Operação: t / 10 = 20.0 /10 = 2.0
    • 3a. Operação: 2.0 = 2.0 portanto resultado verdadeiro

  • Usados em expressões cujo resultado dever ser ou o valor verdadeiro ou falso


4. Operadores Lógicos
  • Existem outros operadores lógicos, como por exemplo, os operadores ou-exclusivo, ne (não e), nou (não ou).
  • Estes outros operadores podem ser obtidos a partir dos três já definidos (e, ou e não).
  • Como os operadores aritméticos estes operadores também têm uma “tabuada”.
  • A ou B tem como resultado verdadeiro se A ou B for igual a verdadeiro.
  • A e B tem como resultado verdadeiro somente se A e B forem iguais a verdadeiro.

  • Algumas vezes estas tabelas são mostradas com o algarismo 0 representando falso e 1 verdadeiro.
  • Para ilustrar os resultados dos operadores lógicos vamos usar como exemplo interruptores que devem ser usados para acender lâmpadas.


  • Lâmpada acende (verdade) somente se interruptor a e interruptor b estiverem ligados (verdade).

  • Lâmpada apaga (falso) porque interruptor a está desligado (falso).
  • Basta um interruptor desligado para que a lâmpada apague.

  • Para a lâmpada acender (verdade) basta pelo menos um interruptor ligado (verdade).

  • Para a lâmpada apagar (falso) é necessário que os dois interruptores sejam desligados (falso).
  • Considere a=falso, b=verdadeiro e c=falso.
  • a e b ou c -- resultado falso
  • 1a. Operação: a e b = falso e verdadeiro = falso
  • 2a. Operação: falso ou c = falso ou falso = falso
  • Considere a=falso, b=verdadeiro e c=falso.
  • não a e b -- resultado verdadeiro
    1a. Operação: não a = não falso = verdadeiro
    2a. Operação: verdadeiro e b = verdadeiro e verdadeiro = verdadeiro
  • Considerando a=falso, b=verdadeiro e c=falso, qual é o resultado das expressões?
  • a e (b ou c)
  • não (a e b)
  • a ou b ou c
5. Expressões lógicas
  • Considerando a=falso, b=verdadeiro e c=falso temos:
  • a e (b ou c) -- resultado falso
    1a. Operação: b ou c = verdadeiro ou falso = verdadeiro
    2a. Operação: a e verdadeiro = falso e verdadeiro = falso
  • Considerando a=falso, b=verdadeiro e c=falso temos:
  • não (a e b) -- resultado verdadeiro
    1a. Operação: a e b = falso e verdadeiro = falso
    2a. Operação: não falso = verdadeiro
  • Considerando a=falso, b=verdadeiro e c=falso temos:
  • a ou b ou c -- resultado verdadeiro
    1a. Operação: a ou b = falso ou verdadeiro = verdadeiro
    2a. Operação: verdadeiro ou c = verdadeiro ou verdadeiro = verdadeiro
6. Expressões mistas
  • É muito comum em algoritmos juntar operadores relacionais e lógicos em expressões.
  • Estas expressões são geralmente do tipo
    (nota1 > 7.0) ou (nota2 > 7.0)‏
    (salario > valor) e (ano > 2001)‏
  • O resultado destas expressões é do tipo lógico (verdadeiro ou falso).
  • Considerando l1=5.0, l2=3.0, l3=4.0 e l4=7.1:
  • (l1 > l3) e (l2 > l4) -- resultado falso
    1a. Operação: 5.0 > 4.0 = verdadeiro
    2a. Operação: 3.0 > 7.1 = falso
    3a. Operação: verdadeiro e falso = falso
  • É possível juntar também operadores aritméticos.
  • Considere l1=5.0, l2=3.0, l3=4.0 e l4=7.1, qual o resultado da expressão?
  • ((l1+2) = l3) ou (l2 <= l4) -- resultado verdadeiro 1a. Operação: 5.0 + 2 = 7.0 2a. Operação: 7.0 = 3.0 = falso 3a. Operação: 3.0 <= 7.1 = verdadeiro 4a. Operação: falso ou verdadeiro = verdadeiro
  • Considerando presente=verdadeiro , n1=7.5 e n2=6.5, qual é o resultado da expressão?
  • (((n1+n2)/2.0) >= 7.0) e presente
  • Considerando presente=verdadeiro , n1=7.5 e n2=6.5 temos:
  • Observe o uso de parênteses para indicar a prioridade das operações
  • (((n1+n2)/2.0) >= 7.0) e presente
    1a. Operação: n1+n2 = 7.5+6.5 = 14.0
    2a. Operação: 14.0/2.0 = 7.0
    3a. Operação: 7.0 >= 7.0 = verdadeiro
    4a. Operação: verdadeiro e presente = verdadeiro e verdadeiro = verdadeiro.
  • Em expressões podemos misturar vários tipos de operadores.
  • A tabela mostra a prioridade relativa dos operadores estudados.
7. Atribuição
  • O resultado de expressões normalmente deve ser armazenado em uma variável para uso futuro.
  • Costuma-se chamar de atribuição esta operação.
  • Em nosso pseudo-código o comando de atribuição é representado pelo símbolo 
  • Por exemplo:
    a  35 * 6 + 2
  • O comando acima faz com que o resultado da expressão (=212) seja armazenado na variável a.
  • Todo comando de atribuição pode ser dividido em duas etapas:

    2. Avaliação da expressão;
    3. Armazenamento do resultado da avaliação na posição de memória representada pela variável.
  • Considere x=10, y=5 e z=8.
  • As figuras abaixo mostram a memória antes e depois do comando de atribuição
    x <- y + z
‏‏

8. Bibliografia

http://equipe.nce.ufrj.br/adriano/algoritmos/apostila/expressoes.htm