(Parte 1 de 2)

Algoritmos e Estruturas de Dados

Prof. Patrick Pedreira

IntroduIntroduçção aos ão aos AlgoritmosAlgoritmos

SumárioSumário vvDefiniDefiniçção de algoritmosão de algoritmos vvLinguagem de programaLinguagem de programaççãoão vvLinguagem estruturadaLinguagem estruturada vvElaboraElaboraçção de programasão de programas

Conceito de ProblemaConceito de Problema

Conceito de ProblemaConceito de Problema vProblema (Dicionário Michaelis): w Substantivo Masculino.

wQuestão matemática proposta para ser resolvida.

wQuestão difícil, delicada, suscetível de diversas soluções.

wQualquer coisa de difícil explicação; mistério, enigma.

wDúvida, questão.

Exemplos de ProblemasExemplos de Problemas vProblemas fazem parte do nosso cotidiano.

vExemplo de problemas cotidianos: wTrocar a resistência de um chuveiro. wDefinir onde Almoçar. wTrocar o pneu de um carro vSempre que nos deparamos com um problema buscamos um procedimento para solucionar o mesmo.

Exemplos de SoluçãoExemplos de Solução vPor exemplo, para trocar a resistência de um chuveiro devemos:

wAdquirir uma resistência nova; wLocalizar o chuveiro a ser manipulado; wAbrir o chuveiro; wRetirar a resistência defeituosa; wColocar a resistência nova; wFechar o chuveiro; wDescartar a resistência defeituosa.

vDefinir onde Almoçar. v ...

Conceitos de LógicaConceitos de Lógica vO que orientou a obtenção dos procedimentos para as soluções vislumbradas? wA lógica.

vO que élógica? wA lógica éo ramo da Filosofia e da Matemática que estuda os métodos e princípios que permitem fazer distinção entre raciocínios válidos e não válidos, determinando o processo que leva ao conhecimento verdadeiro.

Conceitos de LógicaConceitos de Lógica vO uso da lógica éprimordial na solução de problemas. Com ela épossível alcançar objetivos com eficiência e eficácia.

vNinguém ensina outra pessoa a pensar, mas a desenvolver e aperfeiçoar esta técnica, com persistência e constância.

Conceito de AlgoritmoConceito de Algoritmo vAo utilizarmos a lógica para listar passos ordenados que resultam na solução de um determinado problema estamos construindo um algoritmo.

vContrapondo o que normalmente se imagina, o termo algoritmo não foi originado na computação e muito menos pode ser utilizado apenas no contexto computacional.

vPodemos definir um algoritmo como:

wuma seqüência de passos que visa atingir um objetivo bem definido; wuma seqüência de passos bem definida que deve ser seguida para a realização de uma tarefa ou solução de um problema em.

wwDescriDescriçção de um ão de um conjunto finitoconjunto finitode de comandoscomandospara a solupara a soluçção de ão de um problema em um um problema em um tempo finitotempo finito

Exemplos de AlgoritmosExemplos de Algoritmos vComo vimos os conceitos de algoritmo são bem amplos, éimportante salientar que qualquer tarefa que siga determinado padrão pode ser descrita por um algoritmo, como por exemplo:

Algoritmo –Exemplo :: Trocar o pneu de um carro

Algoritmo –Exemplo :: Trocar o pneu de um carro

Algoritmo –Exemplo :: Trocar o pneu de um carro

Algoritmo –Exemplo :: Trocar o pneu de um carro

1.1.Desparafusar a roda.Desparafusar a roda.

Algoritmo –Exemplo :: Trocar o pneu de um carro

Algoritmo –Exemplo :: Trocar o pneu de um carro

2.2.Suspender o carro com um macaco.Suspender o carro com um macaco.

Algoritmo –Exemplo :: Trocar o pneu de um carro

Algoritmo –Exemplo :: Trocar o pneu de um carro

3.3.Retirar a roda com o pneu furado.Retirar a roda com o pneu furado.

Algoritmo –Exemplo :: Trocar o pneu de um carro

Algoritmo –Exemplo :: Trocar o pneu de um carro

4.4.Colocar o Colocar o stepstep..

Algoritmo –Exemplo :: Trocar o pneu de umcarro

Algoritmo –Exemplo :: Trocar o pneu de umcarro

5.5.Abaixar o carro.Abaixar o carro.

Algoritmo –Exemplo :: Trocar o pneu de umcarro

Algoritmo –Exemplo :: Trocar o pneu de umcarro

6.6.Parafusar a roda.Parafusar a roda.

Algoritmo –Exemplo :: Trocar o pneu de umcarro

Algoritmo –Exemplo :: Trocar o pneu de umcarro vNote v1. Pré-suposições do algoritmo vExistem operações que você jásabe fazer, que podem ser básicas ou mais elaboradas.

v2. Nível de detalhamento vPASSO 2: Instalar o macaco e levantar o carro do lado do pneu a ser trocado.

v1. Tire o macaco da mala.

v2. Instale o macaco sob o carro próximo ao pneu a ser trocado.

v3. Se o carro estáem local ladeiroso, colocar um suporte de madeira para evitar que ele se mova.

v4. Alavanqueo macaco atéque haja espaço para o pneu estepe entrar.

Algoritmo –Mais ExemplosAlgoritmo –Mais Exemplos vvPegar um ônibus para a UESB.Pegar um ônibus para a UESB.

vvFazer um bolo.Fazer um bolo. vvFazer um barco de papel.Fazer um barco de papel.

Algoritmo – PropriedadesAlgoritmo – Propriedades vvPossui um Possui um estado inicialestado inicial vvPossui Possui seqseqüüência lência lóógicagica vvContContéém m aaçções claras e precisasões claras e precisas vvPossui Possui dados de entradadados de entrada vvProduz Produz estado final previsestado final previsíívelvel vvDeve ser Deve ser eficazeficaz

Algoritmos ComputacionaisAlgoritmos Computacionais vEntrada: Dados inicialmente conhecidos, os quais permitem encontrar a solução do problema.

vSaída:Resultado obtido pelo processamento de uma entrada específica (instância).

Entrada Saída

Definição alternativa de Algoritmo Computacional: Procedimento que transforma dados em informação. Método usado por um computador para resolver um problema

Algoritmo

SeqSeqüüência Lência Lóógicagica EntradaEntrada

SaSaíídada

Algoritmo –FluxoAlgoritmo –Fluxo

Raio Rde uma circunferência

Perímetro Pda circunferência

Algoritmo –FluxoAlgoritmo –Fluxo

Por que estudar algoritmos?Por que estudar algoritmos? vvRazões prRazões prááticas e teticas e teóóricasricas wwDevemos conhecer um conjunto de Devemos conhecer um conjunto de algoritmos de diferentes algoritmos de diferentes ááreasreas wwDevemos ser capazes de projetar novos Devemos ser capazes de projetar novos algoritmos e medirmos sua eficiênciaalgoritmos e medirmos sua eficiência wwO estudo de algoritmos O estudo de algoritmos ééreconhecidamente a reconhecidamente a pedra fundamental da ciência da computapedra fundamental da ciência da computaççãoão

Por que estudar algoritmos?Por que estudar algoritmos?

Algoritmos Algoritmos éémuito mais que um ramo da muito mais que um ramo da ciência da computaciência da computaçção. ão. ÉÉo no núúcleo da cleo da ciência da computaciência da computaçção e, com toda a ão e, com toda a imparcialidade, pode ser considerado imparcialidade, pode ser considerado relevante para a maioria das ciências, relevante para a maioria das ciências, negnegóócios e tecnologia.cios e tecnologia.

David David HarelHarel

Algoritmos ComputacionaisAlgoritmos Computacionais vvUm algoritmo deve satisfazer os seguintes Um algoritmo deve satisfazer os seguintes critcritéérios:rios:

wwEntrada: uma ou mais quantidades são fornecidas Entrada: uma ou mais quantidades são fornecidas externamenteexternamente wwSaSaíída: Ao menos uma quantidade da: Ao menos uma quantidade ééproduzida produzida wwCerteza: Cada instruCerteza: Cada instruçção ão ééclara e não ambclara e não ambíígua gua wwFinito: Se seguirmos as instruFinito: Se seguirmos as instruçções de um algoritmo, ões de um algoritmo, então, para todos os casos, o algoritmo termina apentão, para todos os casos, o algoritmo termina apóós s um num núúmero finito de passos.mero finito de passos.

wwEfetividade: Cada instruEfetividade: Cada instruçção deve ser simples o ão deve ser simples o suficiente de modo a permitir que uma pessoa suficiente de modo a permitir que uma pessoa utilizando somente lutilizando somente láápis e papel realizepis e papel realize––o.o.

Algoritmos ComputacionaisAlgoritmos Computacionais vvEm resumo:Em resumo:

wwTTéécnicas especcnicas especííficas de projeto de algoritmos ficas de projeto de algoritmos podem ser interpretadas como estratpodem ser interpretadas como estratéégias gias para a resolupara a resoluçção de problemas que podem ão de problemas que podem ser ser úúteis, estando teis, estando ouounão um computador não um computador envolvido.envolvido.

wwAtenAtençção!ão!!!!!Nem todos os problemas podem Nem todos os problemas podem ser resolvidos por algoritmos. Ex. Como se ser resolvidos por algoritmos. Ex. Como se tornar rico e famosotornar rico e famoso

SumárioSumário vvDefiniDefiniçção de algoritmosão de algoritmos vvLinguagem de programaLinguagem de programaççãoão vvLinguagem estruturadaLinguagem estruturada vvElaboraElaboraçção de programasão de programas

ProgramaPrograma vv1. Arquitetura do Computador1. Arquitetura do Computador wwPrograma Programa ééexecutado sobre a arquitetura do executado sobre a arquitetura do computadorcomputador wwHistoricamente utilizamos linguagens de Historicamente utilizamos linguagens de programaprogramaçção considerando de mão considerando de mááquinas de von quinas de von Neumann.Neumann.

wwÚÚltimos 40 anos: imensa maioria das linguagens de ltimos 40 anos: imensa maioria das linguagens de programaprogramaçção foi projetada em funão foi projetada em funçção da arquitetura ão da arquitetura Von NeumannVon Neumann

ProgramasProgramas

Modelo da arquitetura de Von NewmannModelo da arquitetura de Von Newmann

Execução de código numa máquina Von Newmann: ciclo “busca-executa” Programas: residem na memória mas são executados na CPU (cada instrução étransferida da memória para o processador) Endereço da próxima instrução: mantido num registro chamado “program counter” instruções e dados (“piped”) resultados

(“piped”) GARGALO de

Von Newmann

Unidade LUnidade Lóógico Aritmgico Aritméética Unidade de Controletica Unidade de Controle

ProgramasProgramas

EXECUEXECUÇÇÃOÃO vvinicialize o program counterinicialize o program counter vvrepeat foreverrepeat forever wwFetch (busca)Fetch (busca) w Decode (decodifica)Decode (decodifica) wwExecute (executa)Execute (executa)

ProgramaPrograma vvPrograma Programa ééa a codificacodificaççãoãode um algoritmo em uma linguagem de de um algoritmo em uma linguagem de programaprogramaçção.ão.

vvUm computador Um computador ééuma muma mááquina que, a partir de uma quina que, a partir de uma entradaentrada, , realiza um nrealiza um núúmero de mero de ccáálculoslculosmatemmatemááticos e lticos e lóógicos, gerando uma gicos, gerando uma sasaíídada..

vvPrograma Programa ééo elemento queo elemento quediz ao computadordiz ao computadorquais cquais cáálculos lculos devem ser realizados.devem ser realizados.

wwUm programa nada mais Um programa nada mais éédo que um tipo de algoritmosdo que um tipo de algoritmos wwSua particularidade Sua particularidade ééque suas operaque suas operaçções são especões são especííficas para o ficas para o computador e restritas ao conjunto de instrucomputador e restritas ao conjunto de instruçções que o processador ões que o processador pode executarpode executar wwPodemos considerar esse conjunto de Podemos considerar esse conjunto de intruintruççõesõescomo a primeira como a primeira linguagem de programalinguagem de programaçção do computador, tambão do computador, tambéém chamada de m chamada de linguagem de mlinguagem de mááquina.quina.

int a, b, c; if(a > 2) a = b + c; else a = b –c; return;

Algoritmo

Programa

Raciocínio Algoritmo ×Linguagem de ProgramaçãoAlgoritmo ×Linguagem de Programação

Linguagem de programaçãoLinguagem de programação vvEstabelece Estabelece regras de sintaxeregras de sintaxepara que o para que o algoritmo possa ser entendido por uma algoritmo possa ser entendido por uma mmááquina.quina.

vvClassificamos as linguagens de programaClassificamos as linguagens de programaçção ão segundo sua proximidade com a linguagem de segundo sua proximidade com a linguagem de mmááquinaquina wwQuanto maior a semelhanQuanto maior a semelhançça com a linguagem de a com a linguagem de mmááquina, mais baixo quina, mais baixo ééo no níível da linguagemvel da linguagem

Linguagens de baixo nLinguagens de baixo níível vel Linguagens de alto nLinguagens de alto níívelvel

Linguagem de programaçãoLinguagem de programação vvA linguagem de programaA linguagem de programaçção que o computador ão que o computador éécapaz de entender capaz de entender ééformada simplesmente formada simplesmente por npor núúmerosmeros wwAssim, fazer algoritmos na linguagem de Assim, fazer algoritmos na linguagem de programaprogramaçção do computador ou em sua linguagem ão do computador ou em sua linguagem de mde mááquina quina ééum processo extremamente um processo extremamente complicado para ncomplicado para nóós humanoss humanos wwFoi necessFoi necessáária a criaria a criaçção de um cão de um cóódigo que digo que relacionasse a linguagem de mrelacionasse a linguagem de mááquina a uma quina a uma linguagem mais flinguagem mais fáácil de ser compreendidacil de ser compreendida

A ling. de montagem (ou A ling. de montagem (ou assemblyassembly) ) ééum cum cóódigo que tem digo que tem uma instruuma instruçção alfanumão alfanuméérica para cada instrurica para cada instruçção numão numéérica rica em ling. de mem ling. de mááquina.quina.

Linguagem de programaçãoLinguagem de programação vvPara que um programa escrito em linguagem de Para que um programa escrito em linguagem de montagem possa ser executado montagem possa ser executado éénecessnecessáário rio sua tradusua traduçção para cão para cóódigo de mdigo de mááquina.quina.

wwIsso Isso ééfeito por meio de um programa chamado feito por meio de um programa chamado assemblerassembler vvLinguagem de montagem Linguagem de montagem ééainda muito prainda muito próóxima xima da ling. de mda ling. de mááquinaquina vvCada processador tem sua ling. de montagemCada processador tem sua ling. de montagem wwCCóódigo tem que ser refeito se quisermos executar o digo tem que ser refeito se quisermos executar o programa em um processador não compatprograma em um processador não compatíívelvel

Nesse caso, tem um cNesse caso, tem um cóódigo que não digo que não ééportportáávelvel

Linguagem de programaçãoLinguagem de programação vvPara diminuir a complexidade, facilitar e Para diminuir a complexidade, facilitar e aumentar a portabilidade foram criadas as ling. aumentar a portabilidade foram criadas as ling. de alto nde alto níívelvel wwSão independentes do processador em que serão São independentes do processador em que serão executadasexecutadas wwInstruInstruçções prões próóximas da ling. humanaximas da ling. humana wwO processo de traduO processo de traduçção do cão do cóódigodigo--fonte para ling. de fonte para ling. de mmááquina quina ééfeito por um compiladorfeito por um compilador

Métodos de ImplementaçãoMétodos de Implementação vvCompilaCompilaçção ão vvInterpretaInterpretaçção Puraão Pura vvSistemas hSistemas hííbridosbridos

Métodos de ImplementaçãoMétodos de Implementação vv1. Compila1. Compilaççãoão wwTraduz programas de altoTraduz programas de alto--nníível em cvel em cóódigo de digo de mmááquina;quina; wwTraduTraduçção vagarosa;ão vagarosa; wwExecuExecuçção do programa muito rão do programa muito ráápida;pida;

O processo de compilaçãoO processo de compilação

Programa-fonte

Analisador Léxico Analisador Sintático

Analisador Semântico Gerador de código intermediário

Gerador de código Computador

Otimização Tabela de símbolos

(Parte 1 de 2)

Comentários