Parte 1 - Algoritmos

Neste primeiro momento veremos o que são os algoritmos e como representá-los.

    Algoritmo - É uma série ordenada de passos não-ambíguos, executáveis.

    Desta definição formal, temos que o algoritmo  deve conter uma série de passos ordenados. Isso não implica que os passos devam ser executados em sequência mais sim que haja uma ordem de execução.
    Os passos devem ser claros e não ambíguos. Nào pode haver dúvidas quanto a execução do passo.
    Ser executáveis quer dizer que o passo tenha um começo e uma garantia que ele tenha um término. A origem dessa condição está na Teoria da Computação com o problema da parada.

BOLO DE FUBÁ DA MÃE DO ALDO * xícara de 200ml 3 ovos ou 4 se forem pequenos 1 xícara de leite 1 xícara de fubá 1 xícara de farinha de trigo 1 xícara de óleo (eu costumo usar apenas 2/3) 1 1/2 xícara de açúcar 1 colher (sopa) de fermento em pó 2 colheres (sopa) de queijo ralado ou coco ralado (pode usar uma colher de cada tbm) Bata tudo no liquidificador e despeje em forma untada e polvilhada com fubá. Leva para assar em forno pre-aquecido a 180oC por 40 a 50 minutos ou espetando o palito, este saia limpo. Morninho ou frio, é uma delíciaaaaaaaaaaa!!!! http://pecadodagula.blogspot.com/2005/12/bolo-de-fub.html

Exemplo de um Algoritmo para fazer um bolo

Representando um Algoritmo

    O exemplo de algoritmo que vimos, é uma representação  textual informal usando expressões ideomáticas. Nem sempre essas expressões conseguem definir bem o algoritmo. Por exemplo:

• Bata tudo no liquidificador  - Por quanto tempo?
• Despeje em forma untada e polvilhada com fubá - despejar o que? como untar e polvilhar o fubá?

    Temos ai a forma textual informal refinada que agrega essas informações e torna o algoritmo mais preciso. Por exemplo:

• Bata tudo no liquidificador por 10 minutos.

• Pegue uma forma e passe manteiga em toda superfície interna com um pincel e coloque um pouco de fubá por cima de toda a manteiga. Depois, coloque o conteúdo da mistura do liquidificador nesta forma.

    Temos também a forma de fluxogramas que utiliza de  figuras geométricas para representar as  possíveis ações do algoritmo.

Exemplo de um fluxograma

    Além destas representações, temos o pseudocódigo que procura empregar uma linguagem que esteja o mais próximo possível de uma linguagem de programação de computadores de alto nível mas evitando de definir regras de construção gramatical muito rígidas. A idéia é usar as vantagens do emprego da linguagem natural, mas restringindo o escopo da linguagem.

bater_liquidificador(ingredientes,10min) enquanto Bater_liquidificador(ingredientes,10min)     faça untar_tigera(manteiga,fubá)     faça ligar_forno(180oC) enquanto ligar_forno(180oC)     se bater_liquidificador = 10min         coloque a mistura na tigela     faça colocar_mesa(talheres,pratos) Se ligar_forno = 180oC     faça tigela_forno(40min) servir(bolo)

Exemplo de um pseudocodigo

Eficiência e correção

    Embora as máquinas modernas tenham a capacidade de executar milhões de instruções por segundo, a eficiência continua sendo uma preocupação centrasl do projeto de algoritmos. Geralmente a escolha entre um algoritmo eficiente e um ineficiente pode significar, para um dado problema, a diferença entre uma solução prática ou não.
    Considere um problema de atualização em um banco de dados com informações de sequências genéticas com 30.000 sequências. O bioinformata deverá acessar uma determinada sequência, que possui um código e uma descrição e incluir um comentário sobre uma nova funcionalidade.
    Foram apresentados 2 algoritmos de busca para tal lista: a busca sequêncial e a binária. A questão agora e decidir se a escolha entre estes 2 algoritmos fariam alguma diferença. Consideremos primeiro a busca sequêncial.
    Dado o número do código da sequência, o algoritmo de busca sequencial inicia a busca no começo da lista e compara um a um com o número desejado aos elementos da lista. Se não houver informação a cerca do valor procurado, nada concluiremos sobre a extensão da busca. Depois de muitas buscas, podemos dizer que em média teremos 15.000 registros por busca. Se para conferir cada registro for gasto 10 milissegundos, esta busca demorará cerca de 2,5 minutos.
    A busca binária, funciona comparando o valor desejado com o elemento do meio da lista. Se este não for o elemento desejado a busca se restringe ao meio da lista original. Assim, depois do primeiro teste teremos 15.000 registro e na segunda 7.500, se o elemento estiver na lista será encontrado com no máximo 15 comparações. Se cada tentativa levar 10 milissegundos teremos o resultado em 0,15 segundos. Isso nos faz pensar o quão eficiente o algoritmo deve ser e se é realmente viável sua implementação.
    Na criação de um algoritmo temos que considerar sua execução em 3 casos: o melhor caso, o caso médio e o pior caso. Na busca sequencial, o melhor caso é o primeiro elemento da lista, o caso médio são os elementos que se encontram no meio da lista e o pior caso é o último elemento. Não devemos implementar algoritmos prevendo apenas o melhor caso, e sim contando que ele execute a maioria das vezes o caso médio e algumas vezes o pior caso.

Parte 2 - Iniciando no Python

A partir deste ponto iremos vêr uma linguagem de programação e implementar nossos algoritmos.

O que é o Python?. É uma linguagem de programação que  nasceu  para ser de mais alto nível que C e que fosse mais poderosa que o shell scripting. Foi criada por Guido Van Rossum em 1990. Foi distribuida com código-aberto, como o linux, e logo ganhou espaço entre os programadores.
    Python é uma linguaguem interpretada de fácil utilização que incentiva a utilização de práticas de programação correta com uma vasta biblioteca de objetos e funções. Além de ser orientada a objeto e funcionar em multiplataforma.

Primeiros passos

    Para conseguir o interpretador do python, basta acessar: www.python.org e selecionar em download a plataforma que você deseja utilizar o python. Com o python instalado é só acessar a IDLE e começar a programar.

IDLE  do Python

• Strings - são cadeias de caracteres. É o primeiro tipo de arquivo que iremos aprender em python. Podemos concatenar strings.

>>> " Hello World"

'Hello World'

>>> 'Sao' + 'Jorge'

'Sao Jorge'

Podemos também usar o especificador de formatos como:

>>> " Universidade %s" % ("Federal")

'Universidade Federal'

>>>"%-10s %s %10s" % ('teste','de','impressao')

'teste          de         impressao'

    Vamos utilizar a função print para exibir as strings.

>>> print'Biologia Molecular'

Biologia Molecular

>>> print'Biologia\n Molecular'

Biologia
Molecular

     Como no python as strings são tratadas como objetos, temos alguns métodos definidos para a manipulação das strings. Para conhecermos esses métodos podemos utilizar o comando:

>>> dir('string')

      e para saber como utilizar o método

>>> help('metodo')

• Numeros e operações - Em python, os números e as operações básicas da matemática podem ser usadas como numa calculadora.

>>> 5+3

8

>>>6-2

4

>>> 15.0/2*2

15.0

    Temos ianda a opração de mod que representa o resto da divisão entre 2 números.

>>> 5/3

1

>>>5 % 3

2

• Variáveis

    Uma variável é uma relação unívoca entre um nome e um valor, num determinado valor. Os nomes das variáveis podem ter letras maiúsculas, minúsculas por dígitos e pelo caracter '_'.

Vamos declarar a variável Valor com um valor de 5.

>>> Valor = 5

>>> Valor

5

    Podemos inserir comentários no código que ajudam a identificar a funcionalidade e ajudar na legibilidade. o comentário é feito iniciando-se com o caracter '#'.

>>> Valor = 5 # variável de teste

>>> Valor

5

• Listas

    Temos um tipo de dados chamado de lista ou tuplas que consiste de uma sequência de elementos separados por vírgula e delimitados por chaves.

>>> l = [10,"casa",20.0]

>>> l

[10,"casa",20.0]

    Podemos indexar a lista e obter um elemento específico ou um intervalo.

>>> l[1]

["casa"]

>>>l[:1]

[10]

    Podemos concaternar as listas.

>>> print 2 * l

[10,"casa",20.0,10,"casa",20.0]

• Dicionários

    Assim como as listas os dicionários agrupam elementos arbitrários mas utilizam uma chave associada a cada elemento.

>>> d ={'nome':'André','idade':26}

>>>d['nome']

['André']

    Podemos atribuir valores a novas chaves no dicionário.

>>> d['peso'] =  80

>>>  print  d

['nome':'André','idade':26,'peso':80]

• Controle de fluxo

    São instruções que selecionam opções e definem condições ao programa.

   Função IF - avaliar um conjunto de condições e executar o bloco de instruções associado a primeira que seja avaliada como verdadeira.

 lf x == o:
    print "O x é zero"

    Função WHILE - existe um bloco de instruções que é executado enquanto uma dada condição for verdadeira. A partir do momento em
que essa condição passa a ser avaliada como falsa, executa-se um outro bloco de instruções - este bloco é opcional -, e o ciclo termina.

x=0

while x <5:

    x = x+1

    print " O valor de x é" x

    else:

       print " O valor de x ultrapassou 5"

    Função FOR - existe uma sequência (pode ser I uma string ou uma lista) e é sobre os elementos desta, na ordem em que estão dispostos na mesma, que o ciclo for itera.

for i in d:

    i == "casa":

    print "d é uma lista"

    else:

       print "d é um dicionário"

• Definindo uma função

    uma função é um bloco de instruções precedido por um cabeçalho que a identifica. Concretamente:

def contar(x):                # função que conta os elementos de uma lista

    for i in x:                    # para um elemento da lista

       cont = 0                 # condição inicial do contador

       cont = cont +1       # contando 1 a cada elemento da lista

       return  cont           # retornando o valor do contador