Skip to content

Latest commit

 

History

History
141 lines (113 loc) · 4.04 KB

contextualizacao.org

File metadata and controls

141 lines (113 loc) · 4.04 KB

Contextualização e Histórico, Origem dos Paradigmas

1 Paradigmas e Modelos

Imperativo

  • Estruturado: foco nas instruções, procedimentos
  • Orientado a Objetos: dados, métodos

Declarativo

  • Funcional: funções
  • Lógico: axiomas, predicados lógicos

O que nos levou a estes diferentes modelos/paradigmas?

2 Fundamentos

Trabalhos de matemáticos no início do século XX

  • Alan Turing, Alonzo Church, Stephen Kleene, Emil Post, etc

Formalização da noção de algoritmo → Método Efetivo

  • Transforma a solução em uma série de passos

Várias proposições independentes, exemplos

  • Autômatos, Manipulação Simbólica
  • Definição de funções recursivas, Combinatória

Um programa visto como uma prova construtiva.

Evitar Infinito (∞)

Assumir a Lei do Terceiro Excluído (falso = !verdadeiro)

3 Detalhamento histórico

1920

  • Moses Schönfinkel → Teoria de Funções
    (combinadores – função cujo argumento é outra função)

A partir de 1930

  • Alonzo Church → Cálculo Lambda
  • Haskell Curry → Estendeu Schönfinkel, mostrando que a teoria de funções é equivalente ao cálculo lambda
  • Kleene → Cálculo lambda é um sistema de computação universal
  • Turing escreveu o artigo: “On computable numbers with an application to the Entscheidungs-problem” (1936, 36p.) \linebreak → Máquina Universal

4 A origem dos diferentes modelos/paradigmas

O que nos levou a estes diferentes modelos/paradigmas?

Turing – Máquina de Turing

  • Autômato Finito com acesso arbitrário a uma Fita Infinita
  • Modelo Imperativo
    → computação via modificações de valores na fita

Church – Cálculo Lambda ($λ$)

  • Expressões Parametrizadas
    (cada parâmetro é uma ocorrência de $λ$)
  • Modelo Funcional
    → comput. via substituição de parâmetros em expressões

Boole – Axiomas Lógicos

  • Procedimento que descobre a prova construtiva para cada conjunto particular de entradas
  • Modelo Lógico

OO?

5 Exemplo: MDC entre dois números inteiros a e b

Imperativo

  • Para computar o MDC de a e b, teste se a e b são iguais. Se sim, imprima um deles e pare. Se não, substitua o maior pela diferença entre eles e repita o procedimento

Funcional

  • O MDC de a e b será a quando eles forem iguais e será o MDC de c e d quando forem diferentes, sendo c o menor valor entre a e b, e d a diferença entre a e b. Expanda e simplifique essa definição recursivamente até terminar.

Lógico

  • A proposição MDC(a,b,g) é verdadeira se a = b = g, MIN(a,b,c) é verdadeira, MENOS(a,b,d) é verdadeira, e MDC(c,d,g) é verdadeira. Para computar MDC(m,n), procure por um valor de g (e vários valores de c e d) para os quais essas regras permitam provar que MDC(m,n,g) é verdadeiro.

6 Exemplo: código simplificado

  • Imperativo (C++) 
    while(a != 0){
  tmp = a;
  a = b % a;
  b = tmp;
} cout << a;
  • Funcional (ML) 
    mdc a 0 = a
mdc a b = mdc b (a `mod` b)
  • Lógico (Prolog) 
    mdc(A,A,A).
mdc(A,B,R) :- A>B, A1 is A-B, mdc(A1,B,R).
mdc(A,B,R) :- B>A, B1 is B-A, mdc(A,B1,R).