Ferramentas de Usuário

Ferramentas de Site


algoritmo:tutorial

Esta é uma versão antiga do documento!


O presente tutorial está em construção, por favor não o edites enquanto não estiver concluído.
Obrigado.

Tutorial de Introdução à Lógica e Algoritmia

Este tutorial tem o objectivo de dar algumas bases nestas duas disciplinas para iniciantes à programação.
Sendo que a programação está assente na algoritmia, e a algoritmia está assente na lógica, como se verá ao longo deste pequeno tutorial, este torna-se de extrema importância para se entender muitos "porquês" da programação que os beginners muitas vezes colocam.

Lógica

De forma resumida, a lógica é o ramo da filosofia que cuida das regras do bem pensar, ou do pensar correto, sendo, portanto, um instrumento do pensar.1)

Nesta parte vamos entender os operadores lógicos básicos - E, OU e OU… OU… - recorrendo às Tabelas de Verdade.

Proposições e condições

De forma muito resumida, seguem-se três exemplos simples e perceptíveis:

  • Sentença: O João gosta de ir à praia.
  • Proposição: O João gosta de ir à praia e ao campo.
  • Condição: O João gosta de ir à praia se estiver bom tempo.


Tabela de Verdade

Numa Tabela de Verdade são analisadas todas as hipóteses de resposta a um problema lógico, desde o mais simples ao mais complexo, sendo mesmo a base das bases da investigação criminal forense.
São lançadas as hipóteses de forma lógica, unindo as sentenças em proposições e relacionando estas últimas em condições. Um exemplo simples e sem fundamentação forense:
O João é culpado se a arma do crime tiver as impressões digitais dele. Ou a arma é uma faca se as impressões digitais forem as dextras, ou então é uma pistola se ele praticar carreira de tiro.
A Tabela de Verdade tem a seguinte estrutura básica:

proposição 1 (p) proposição 2 (q) Resultado com o operador lógico X (p X q)
V V V X V
V F V X F
F V F X V
F F F X F

Havendo duas proposições, há quatro hipóteses de conjugação conforme os valores lógicos da proposição.
Havendo N proposições num enunciado lógico como o anterior, vão existir 2^N combinações. Neste caso, havendo 2 proposições, existem 2^2=4 combinações.

Valor lógico: Verdadeiro, Falso.
Uma proposição só pode tomar um valor lógico - não pode ser V e F ao mesmo tempo!


Operadores lógicos

E - Conjunção

O João gosta de praia e do campo.
Ou seja, o João gosta de ambas as coisas, a praia e o campo.

p q p~wedge~q
V V V
V F F
F V F
F F F

Só é verdadeiro quando ambas as proposições são verdadeiras.

OU - Disjunção

O João gosta de praia ou do campo
Isto é, o João gosta ou da praia, ou do campo ou de ambos.

p q p OU q
V V V
V F V
F V V
F F F

Só é falso quando ambas as proposições são falsas.

OU... OU...

O João ou gosta de praia ou gosta de campo.
Ou seja, O João gosta de um só destes ambientes, e não dos dois ao mesmo tempo: ou um ou outro.

p q OU p OU q
V V F
V F V
F V V
F F F

É falso quando as proposições têm o mesmo valor lógico.

Condições

Implicação

Se o João gosta de ir à praia, então gosta do mar.

p q p~doubleright~q
V V V
V F F
F V V
F F V
NOTA: "Verdadeiro implica falso" é falso.
Mas "Falso implica verdadeiro" é uma condição verdadeira.


Equivalência

O João gosta de praia se e só se gosta de mar.

p q p~doubleleftright~q
V V V
V F F
F V F
F F V

Ou seja, só é verdade quando ambas as proposições tiverem o mesmo valor lógico - só assim as proposições equivalem uma à outra.

Outras operações lógicas

Negação

Esta é uma operação muito básica que, simplesmente, nega o resultado lógico de uma proposição ou condição.

p ~p
V F
F V

O João não gosta de ir à praia e gosta de de mar. - ~p~wedge~q

Dupla negação: ~~p~doubleleftright~p


Igualdade e diferença

Sem negação:

  • 2+2~=~4 - verdadeiro
  • 2-5~<>~-3 - falso


Com negação:

  • ~(5+6~=~11) - falso
  • ~(3-1~<>~2) - verdadeiro


Maior do que, menor do que, maior ou igual que, menor ou igual que

  • 5~>~9 - falso
  • 3~<~8 - verdadeiro
  • ~((3+pi)~>=~6) - falso
  • ~((1/e)~<=~(1/pi)) - verdadeiro


Principais Leis de Morgan

  • ~(p~wedge~q)~doubleleftright~~p~OU~~q
  • ~(p~OU~q)~doubleleftright~~p~wedge~~q


Algoritmia

Um algoritmo é uma sequência finita de instruções bem definidas e não ambíguas, cada uma das quais pode ser executada mecanicamente num período de tempo finito e com uma quantidade de esforço finita.2)
Ou seja, um algoritmo é um caminho bem definido para se resolver um determinado problema. Por exemplo:

Problema Algoritmo Geral
Multiplicar 36 por 2 Alg. da Multiplicação: matrix{2}{2}{~ 36 ~*~ 2} / matrix{1}{2}{~ 72}
Ordenar lista de forma crescente: {7,~3,~6} Alg. de Ordenação (Crescente): {3,~6,~7}


Representação de Algoritmos

Um algoritmo tem uma representação para que possa ser facilmente interpretado. Antes de se programar, os problemas devem ser estudados para se chegar a um algoritmo-solução. Este será representado num esquema, chamada Fluxograma, ou então escrito na linguagem-mãe (no nosso caso, Português) ou numa mistura desta com a linguagem de programação a que nos propomos resolver o dito problema.
Vamos então analisar um algoritmo muito simples que resolve o seguinte problema:
Dados dois números, inteiros, inseridos pelo utilizador, dizer qual é o maior, ou então se são iguais.

Fluxograma

Vamos resolver o problema anterior segundo o algoritmo tradicional: análise caso-a-caso, que com este problema é totalmente viáveis pois basta analisar duas situações, segundo esta ordem:

  • Se num1 é maior que num2, mostra num1…
  • Caso contrário, se num2 é que é maior que num1, então mostra num2…
  • Por fim, se num1 não é o maior e num2 também o não é, conclui-se que só podem ser iguais.


Um fluxograma respeita uma norma geral que pode ser adaptada por cada pessoa. A imagem seguinte mostra o algoritmo de resolução do problema proposto seguindo a norma geral dos fluxogramas. No canto superior direito da imagem está uma pequena legenda, que inclui símbolos não incluídos no esquema.

Fluxograma
De notar que cada "caminho" é chamado de fluxo, e no final do programa reconhecem-se três fluxos que são unidos antes de se dar o fim do programa: o símbolo é um círculo e denomina-se conector de fluxos.
Na prática, na programação não se nota esta conexão de fluxos, mas na teoria, havendo a um determinado ponto vários caminhos possíveis, eles unem-se sempre, pelo menos no fim do programa. Esta união pode ocorrer noutro ponto e pode reunir apenas alguns dos N fluxos que existam - vários conectores podem existir.
Pontos em que um fluxo se divide são quase sempre Condições, excepto nos Ciclos que, em si, têm dois fluxos: o fluxo das acções a processar dentro do ciclo e um fluxo de retoma do ciclo no caso de a condição de paragem não for satisfeita. Esta é a teoria básica de fluxos nas Estruturas de Repetição.

Pseudo-código

 Início Programa
    Ler num1
    Ler num2
    Se (num1>num2) Então
       Escrever "O maior é: " & num1
    SeNão
       Se (num1<num2) Então
          Escrever "O maior é: " & num2
       SeNão
          Escrever "São iguais."
       Fim Se   
    Fim Se
 Fim Programa


Alguns algoritmos

Algoritmo de ordenação

Ver o Capítulo 5 da Parte II do nosso Tutorial de Pascal: Ordenação crescente de uma lista.
Aproveita e vê como pode ser programado recorrendo a Pascal. ;-)

Grafos

Ver o artigo da Revista PROGRAMAR: Parte 13) e Parte 2.

Algoritmos de pesquisa

Vê o documento completo Algoritmos de pesquisa.

Autor

O autor original, thoga31.

3)
indisponível - faça o download da edição nº10 da Revista.
algoritmo/tutorial.1309979374.txt.gz · Última modificação em: 2018/05/14 21:37 (edição externa)