Algoritmos - Aula 01

  • View
    10

  • Download
    1

Embed Size (px)

Transcript

  • Algoritmos

    Prof. Msc. Carlos Queiroz

    Semestre 2014.2

  • Agenda

    Apresentao

    Ementa da Disciplina

    Avaliao

    Bibliografia

    Introduo

    2

  • Apresentao

    Carlos Alberto

    Graduao

    Especializao

    Mestrado

    Histrico Profissional

    3

  • Apresentao (Alunos)

    Algoritmo para apresentao: Faa:

    Diga o seu Nome; Responda: J possui algum conhecimento relacionado a

    disciplina?

    Indique um colega para se apresentar; Enquanto (tiverem alunos que no se apresentaram )

    4

  • Ementa

    Ementa disponvel no Plano de Ensino

    5

  • Avaliao

    3 Provas Avaliao Parcial 1 (AP1) -> Peso 30% da nota final Avaliao Parcial 2 (AP2) -> Peso 30% da nota final Avaliao Parcial 3 (AP3) -> Peso 40% da nota final

    Mdia deve ser superior a 5,0. Caso contrrio, nos veremos no prximo semestre =)

    Obs.: Terceira prova elaborada pela prpria faculdade (25 questes)

    6

  • Bibliografia Bsica

    FORBELLONE, Andr Luiz Villar. Lgica de Programao: a Construo de Algoritmos e Estrutura de Dados. So Paulo: Pearson, 2005.

    GUIMARAES, Angelo de Moura; LAGES, N. A. C. Algoritmos e Estrutura de Dados. Rio de Janeiro : LTC, 2008.

    SEBESTA, Robert W. Conceitos de Linguagens de Programao. So Paulo: Bookman, 2003.

    7

  • 8

  • Aula 1 - Introduo

    Agenda

    Conceito de Algoritmo

    Conceito de programa de computador

    9

  • Conceito de Algoritmo

    10

  • Conceito de Algoritmo (cont.)

    Algoritmos esto em toda parte

    Receita de bolo

    Descrio de um caminho

    Instrues medicamentosas

    Manual de instrues

    Atividades cotidianas

    Etc...

    11

  • Conceito de Algoritmo (cont.)

    12

  • Conceito de Algoritmo (cont.)

    13

  • Conceito de Algoritmo (cont.) Exemplo

    Trocar uma lampada...

    Pegar Lmpada nova

    Pegar Escada

    Posicionar escada embaixo da lmpada queimada

    Subir na escada com a lmpada nova na mo

    Retirar lmpada queimada

    Colocar lmpada nova

    Descer da escada

    Testar no interruptor

    Guardar a escada

    Descartar Lmpada velha

    14

  • Conceito de Algoritmo (cont.)

    Exemplo

    Calcular mdia

    Pegar nota da primeira prova

    Multiplicar primeira nota por 0,3 e guarde o resultado

    Pegar nota da segunda prova

    Multiplicar segunda nota por 0,3 e guarde o resultado

    Pegar nota da terceira prova

    Multiplicar terceira nota por 0,4 e guarde o resultado

    Some todos os resultados que foram guardados

    Mostre ao seu professor

    15

  • Conceito de Algoritmo (cont.)

    Computadores podem ajudar na realizao de tarefas mais complexas

    Problemas envolvendo um grande volume de dados

    Problemas que exijam um grande nmero de operaes

    Problemas que exijam preciso

    Caractersticas de um bom Algoritmo

    Finitude

    Exatido

    Entradas e Sadas determinadas

    Efetividade

    16

  • Conceito de Algoritmo (cont.)

    Representao

    Linguagem Natural

    Descrio textual da tarefa em linguagem natural

    Forma narrativa

    Ex.: Para chegar na minha casa basta que voc siga pela rua A por 2 quilmetros. Quando voc passar em frente a padaria vire esquerda e siga por mais 100 metros. Minha casa ficar logo sua direita.

    17

  • Conceito de Algoritmo (cont.)

    Representao

    Fluxograma

    Representao Grfica estruturada e simplificada

    Ilustra o fluxo de operaes

    Sintaxe e Semntica bem definidos

    Fcil para traduzir para uma linguagem de programao

    18

  • Conceito de Algoritmo (cont.)

    Fluxograma

    19

  • Conceito de Algoritmo (cont.)

    A sintaxe de um fluxograma corresponde ao emprego correto de seus Elementos Cada instruo possui um smbolo grfico especfico Cada smbolo admite um conjunto de expresses prprias Sub-rotinas pr-definidas podem ser utilizadas nas

    expresses

    A semntica de um fluxograma corresponde ao significado dos smbolos utilizados Cada instruo deve ser descrita de forma clara, sem

    ambiguidade

    20

  • Fluxograma/Resumo

  • Conceito de Algoritmo (cont.)

    Representao

    Pseudo-cdigo

    22

  • Algoritmo Aprofundando no conceito Um algoritmo uma sequncia de instrues finita e

    ordenada de forma lgica para a resoluo de uma determinada tarefa ou problema.

    No obrigatoriamente nico H vrios caminhos para o mesmo destino

    Deve seguir uma sequencia lgica Nem toda combinao de uma sequencia de passos vai

    levar ao mesmo objetivo completo

    23

  • Conceito de Programa

    Programa de Computador

    Algoritmo escrito em uma linguagem de programao

    24

  • 0-25

    Tipos de Software

    Software de Aplicao Programas para realizao de tarefas particulares utilizao da

    mquina Ex.: Sistemas de Banco de dados, Sistemas de Planilhas

    eletrnicas, sistemas de contabilidade, Software para desenvolvimento de programas, etc

    Software de Sistema Tratam da realizao de tarefas comuns aos sistemas

    computacionais em geral Fornecem a infraestrutura necessria para execuo das

    aplicaes

  • 0-26 Figura 3.3 Classificao de software

    Software

    Aplicao Sistema

    Sistema Sistema

    Operacional

  • Linguagem de Mquina

    Um processador executa apenas instrues escritas em linguagem de mquina (dgitos binrios)

    Cada instruo composta de duas partes

    Comando e operando

    1000 11101001

    A Linguagem de mquina a mais rpida

    27

  • 0-28

    O Computador

  • 0-29

    Viso geral sobre arquitetura de Computadores

    Unidade Central de Processamento (CPU)

    o conjunto de circuitos de computador que controla a manipulao de dados

    Em razo da sua evoluo, hoje so conhecidos tambm por microprocessadores

    Consiste em trs partes Unidade Lgica e Aritmtica Unidade de Controle Unidade de Registro

  • 0-30

    Viso geral sobre arquitetura de Computadores

    Unidade Lgica e Aritmtica Contm circuitos que realizam operaes sobre os dados

    Unidade de Controle Contm circuitos para a coordenao das atividades da

    mquina

    Unidade de Registro Contm clulas de armazenamento de dados Essas clulas so chamadas Registradores e servem

    como locais temporrios de armazenamento de dados que so manipulados pela CPU

    Registradores Propsito geral Propsito especfico

  • Memria

    Dispositivo capaz de armazenar dados.

    Possui uma grande quantidade de posies livres para armazenamento temporrio de dados.

  • 0-32

    Viso geral sobre arquitetura de Computadores

    Barramento Ligao entre a CPU de uma mquina e sua memria

    principal, para fins de transferncia de padres de bits, atravs de um conjunto de fios

  • Conceito de Programa Armazenado

    0-33

    Nos primeiros computadores, os passos que cada dispositivo executava eram definidos dentro das suas unidades de controle, como uma parte da mquina

    O objetivo que a CPU pudesse ser reconfigurada Ex.: Cartes perfurados

    A ideia que um programa assim como seus dados, pudesse ser codificado e armazenado na memria principal A CPU pode extrair as instrues e execut-las O programa a ser executado pode ser alterado mais facilmente No mais necessrio alteraes na CPU para modificaes no

    seu programa

  • 0-34

    Linguagem de Mquina

    A partir do conceito de programa armazenado, as CPUs so projetadas para reconhecer instrues codificadas como padres de bits

  • Forma geral de operao em dados

    1. Unidade de controle transfere dados da memria principal para os registradores

    2. Unidade de controle informa a unidade lgica e aritmtica (ULA) sobre quais registradores mantm os dados

    3. Ativa os circuitos apropriados da ULA e informa quais os registradores que devem receber o resultado

    0-35

  • 0-36

    Controlador

    Um aparato intermedirio que cuida da comunicao entre a CPU e um dispositivo

    Especializados para cada tipo de dispositivo Traduz mensagens e dados em ambas as

    direes entre formatos compatveis Atualmente existem controladores de propsito

    geral (Ex.: USB)

    Comunicao com outros dispositivos

  • 0-37

    Porta Ponto no qual um dispositivo se conecta ao

    computador

    E/S Mapeada em memria A CPU se comunica com os perifricos como se

    eles fossem clulas de memria

    Comunicao com outros dispositivos

  • 0-38

    Figura 2.13 Controladores anexados ao barramento

  • O QUE SER ARMAZENADO NA MEMRIA?

    n Tipos de Informaes: n Podemos classificar os tipos de informaes a serem

    processadas, a grosso modo, em dados e instrues.

    n Dados: So as informaes a serem processadas por um computador. Consideremos 3 tipos de dados primitivos: numricos (inteiros e reais), caracteres e lgicos.

  • Tipos primitivos de dados

    n Inteiro: toda e qualquer informao numrica que pertena ao conjunto dos nmeros inteiros (negativa, nula ou positiva).

    n Exemplos: 10, 5, -5, -10

  • Tipos primitivos de dados

    n Real: toda e qualquer informao numrica que pertena ao conjunto dos nmeros reais (negativa, nula ou positi