Algoritmiae Programação - dei.isep.ipp.pt anamadur/cpro/  · 6 11 Algoritmo Algoritmo - sequência…

  • Published on
    03-Dec-2018

  • View
    213

  • Download
    0

Embed Size (px)

Transcript

  • 1

    Algoritmia e Programao

    Engenharia Informtica1 ano - 1 semestre

    Ano Lectivo 2004/2005

    Ana Maria Madureira

    2

    Apresentao

    Programa da DisciplinaMetodologiaMtodo de AvaliaoBibliografia

  • 2

    3

    Introduo Informtica

    Informao Informao Binria - bit, byte, word

    Informtica = Informao + Automtica

    Computador conjunto de circuitos elctricos e electrnicos

    capazes de realizar tarefas de modo autnomo por obedincia a um programa

    4

    Conceitos

    Hardware (Componente Fsica) o conjunto de componentes mecnicos, elctricos, magnticos e

    electrnicos de um sistema informtico

    executar um determinado tipo de instrues a determinada velocidade

    armazenar um nmero de bytes

    comunicar com um conjunto de perifricos

    Software (Componente Lgica) que o conjunto de programas utilizados em determinado sistema informtico

  • 3

    5

    Sistema de Computao

    Hardware

    Software Software de Sistema

    Sistema Operativo Utilitrios (editores, compiladores,...)

    Software de Desenvolvimento Ambientes de programao SGBD- Sistemas de Gesto de Bases de Dados Folhas Clculo,...

    Aplicaes Packages Aplicaes por medida

    6

    Sistema Operativo

    um programa (ou conjunto de programas) que dirige o processadorno

    controlo dos recursos do sistema de computao controlo da execuo dos programas de aplicao dos utilizadores

    do sistema de computao

    Funciona como uma interface entre o utilizador e o hardware, escondendo os detalhes de hardware, fornecendo assim uma mquina virtual de mais fcil utilizao

    Apresenta ao programador servios de alto nvel para uma explorao

    fcil e eficiente do hardware.

  • 4

    7

    Desenvolvimento de Software

    Desenho e Programao Estruturados Desenho Modular

    Refinamento gradual do topo para a base

    Programao Estruturada

    8

    Paradigmas da Programao

    Programao Imperativa (Procedimental)

    Programao orientada Aco

    PROGRAMA = Algoritmo + Estrutura de Dados.

    Programao Orientada a Objectos

    Programao Funcional

    Programao Declarativa

  • 5

    9

    Resoluo de Problemas

    Analisar o problema Conhecer o bem o problema

    Descrever o problema: subdividir, detalhar

    Resolver o problema passo a passo, verificar se no h ambiguidade na soluo apresentada, ou seja,

    descrever o algoritmo.

    Implementar a soluo numa linguagem de programao

    10

    Resoluo de Problemas

  • 6

    11

    Algoritmo

    Algoritmo - sequncia de passos lgicos para a realizao de uma tarefa

    Propriedades Entrada e Sada

    Finito

    Definido

    Eficaz

    Descrio de Algoritmos - com base na Lgica da Programao e utilizando

    Pseudo- Cdigo

    Fluxograma

    Anlise de Algoritmos Tracing, Implementao e teste

    12

    Conceitos

    Tipo de Dados Numricos:

    Inteiros (12, 1, 1908654, ...)

    Reais (-12.4, 0.0000765, ...)

    Cadeias de caracteres

    Alfabticos, algarismos ( Carlos, Semestre2, ... )

    Outros smbolos (!, #, @,, ...)

    As cadeias de caracteres so representadas entre aspas.

    Estruturas de Dados (modo como os dados esto organizados e como so acedidos e

    alterados ...)

    variveis simples, arrays mono e multi-dimensionais, listas, filas,

    rvores, grafos,

  • 7

    13

    Conceitos

    Noo de Varivel - posio de memria Nome - sugestivo e curto, iniciado sempre por uma letra Endereo valor (contedo)

    Tipo de Dados tipo de valores

    tipo de operaes

    Estrutura de Dados Atribuir valor a varivel

    Aceder ao valor de uma varivel

    14

    Operadores

    Aritmticos * , / , : multiplicao, diviso e exponenciao + , - : adio e subtraco

    Relacionais

    = , : menor ou igual, maior ou igual, diferente

    Lgicos Negar : Negao

    E : conjuno

    Ou : disjuno

  • 8

    15

    Programao Estruturada

    Qualquer programa pode ser descrito utilizando as trs

    estruturas bsicas de controlo:

    Sequncia - permite a ordenao em srie de instrues

    Seleco/ Deciso - permite a seleco em alternncia de um ou outro conjunto de aces por avaliao de uma

    condio

    Repetio - permite a execuo condicional em circuito fechado (ciclo) de um dado grupo de instrues. A condio testada em cada iterao para decidir se sair ou no do ciclo.

    16

    Algoritmos

    Linguagem formal Fluxograma

    INICIO ou FIM

    LER()

    ESCREVER()

    PROCEDIMENTO/FUNO SE...ENTO...SENO PARA...AT...FAZER ENQUANTO...FAZER REPETIR...AT

    Inicio ou fim

    Entrada de dados

    Saida de resultados

    Processamento

    Inicio de sub-rotina

    Transferncia para sub-rotina

    Deciso

  • 9

    17

    Algoritmos - Sequncia

    Linguagem formal Representao Grfica

    Instruo 1

    :::::::::::::::::

    Instruo N

    Instruo 1

    Instruo 2

    Instruo N

    18

    Sequncia (Exemplo)

    Esboce o algoritmo que, sabendo um valor em metros, mostre o valor correspondente em centmetros.

    ED: m, cm real

    Algoritmo

    Inicio

    escrever(Introduza o valor em metros:)

    ler(m)

    cm m*100

    escrever(m,m =,cm,cm)

    Fim

  • 10

    19

    Sequncia (Exemplo)

    Esboce o algoritmo que permita determinar a rea de um tringulo,

    dada a base e altura.

    ED: real base, altura, area

    Algoritmo

    INICIO

    ler( base, altura)

    area

  • 11

    21

    Estruturas Encaixadas

    Linguagem formal R epresentao Grfica

    SE cond io 1 ENTO SE Condio 2 ENTO Instrues SENO Instrues FIMSE SENO SE Condio 3 ENTO Instrues SENO Instrues FIMSE FIMSE

    SE...

    SENO SE...

    SE...

    ENTO ENTOSENO

    ENTOSENO

    Instrues Instrues Instrues Instrues

    22

    Deciso (Exemplo)

    Desenvolver um programa que permita verificar se um dado nmero inteiro fornecido pelo utilizador par ou impar.

    Algoritmo 1:1 passo ler o valor introduzido no teclado;2 passo verificar se o valor par ou impar;3 passo enviar para o monitor a informao;

    Algoritmo 2:Inicio

    Ler(valor)

    Se valor fr par ento

    Escrever (o valor par)

    Seno

    Escrever (o valor impar)

    FimSe

    Fim

  • 12

    23

    Deciso (Exemplo)

    Descrever um algoritmo para ler dois valores diferentes e determinar qual o maior.

    ED : A e B variveis inteiras

    Inicio

    ler(A,B)

    Se A > B Ento

    MAXASeno

    MAXBFimSe

    Escrever(MAX)

    Fim

    24

    Deciso Estruturas Encaixadas (Exemplo)

    Descrever um algoritmo para ler trs valores, e imprimir o maior valor, assumindo que so valores

    diferentes.

    ED: 3 variveis inteiras INICIO

    LER(A,B,C)SE A>B ENTO

    SE A>C ENTOMAX A

    SENOMAX C

    FIMSESENO

    SE B>C ENTOMAX B

    SENOMAX C

    FIMSEFIMSEESCREVER(MAX)

    FIM

  • 13

    25

    Estrutura de Deciso MltiplaCaso ...

    ...

    Caso expresso

    =1:

    =2:

    =3:

    ...

    =n:

    FimCaso

    expresso

    S1 S2 S3 S4 Sn...

    ...

    =1 =2 =3 =4 =n

    26

    Repetio - enquanto (...) fazer ...

    Enquanto condio fazer

    Instrues

    FimEnquanto

    condio

    Instrues

    No

    Sim

  • 14

    27

    Repetio Enquanto (...) fazer ...Exemplo

    ExemploLer uma sequncia de nmeros terminada por zero, e mostr-la.

    ED: 1 varivel real

    INICIO

    LER(NUM)

    ENQUANTO NUM 0 FAZER

    ESCREVER(NUM)

    LER(NUM)

    FIMENQUANTO

    FIM

    28

    Repetio Repetir ... at (...)

    Repetir

    Instrues

    Enquanto condio

    condio

    Instrues

    Sim

  • 15

    29

    Repetio Repetir ... at (...) Exemplo

    Ler uma sequncia de nmeros terminada por zero, e mostr-la.

    ED: 1 varivel realINICIO

    REPETIRLER(NUM)ESCREVER(NUM)

    AT NUM = 0FIM

    30

    Repetio para (... ) fazer

    Linguagem formal Representao Grfica

    PARA varivel de controlo = valor1 AT valor 2 FAZER Instrues FIMPARA

    Instrues

    Verdade

    Falsovarivel controlo

  • 16

    31

    Repetio para (... ) fazerExemplo

    Ler uma sequncia de 10 nmeros reais, e mostr-la.

    ED: 1 varivel real, 1 varivel inteira

    INICIO

    PARA I 1 AT 10 FAZER

    LER(NUM)

    ESCREVER(NUM)

    FIMPARA

    FIM

    32

    Repetio para (... ) fazerExemplo

    Desenvolver um programa que permita calcular o valor da potncia de base x

    e expoente inteiro y - xy.

    Inicio

    Ler (x,y)

    res 1

    Para a1 at y incrementando 1 fazer

    res res * x

    Fim Para

    Escrever (res)

    Fim

  • 17

    33

    Traagem

    A traagem consiste em testar um algoritmo para determinados valores de entrada, observando o seu comportamento. Todos os passos do algoritmo devem ser numerados: P1, P2 ...

    A forma mais simples construir uma tabela, em que os ttulos das colunas so constitudas por todas as operaes efectuadas pelo algoritmo, desde atribuies, condies, repeties.

    Os ttulos das linhas correspondem aos passos P1, P2, etc. O algoritmo pode a partir de agora ser executado manualmente. A ideia determinar se a sua lgica vlida e corresponde aos objectivos que se pretendem atingir.