Em que consiste a ciência, na computação? - dcc.ufrj.brcollier/Palestras/computacao.pdf · Algumas perguntas O que é ciência da computação? O que é um computador ? Existia

Em que consiste a ciência, nacomputação?

S. C. Coutinho

Instituto de Matematica–UFRJ

Open House 2009 – p. 1/50

Algumas perguntas


Algumas perguntas

O que é ciência da computação?


Algumas perguntas


O que é um computador ?


Algumas perguntas


O que é um computador ?

Existia ciência da computação antes do computador?


Segundo a Wikipedia


Segundo a Wikipedia

Um computador é uma máquina que manipula dadosde acordo com um conjunto de instruções.


Segundo a Wikipedia

Um computador é uma máquina que manipula dadosde acordo com umconjunto de instruções.


Segundo a Wikipedia

Um computador é uma máquina que manipula dadosde acordo com um programa.


Computer


Computer

Now it is manifest, and most men likewise know, thatthe Calenders of these computers, and the accountsof these days are very different (...)


Computer

Now it is manifest, and most men likewise know, thatthe Calenders of thesecomputers, and the accountsof these days are very different (...)


Computer


Sir Thomas Browne


Computer


Sir Thomas BrownePseudodoxia Epidemica


Computer


Sir Thomas BrowneErros Vulgares


Computer


Sir Thomas BrowneErros Vulgares (1646)


Computer



Portanto, naquela épocacomputerera umapessoaquefazia cálculos,


Computer



Portanto, naquela épocacomputerera umapessoaquefazia cálculos, como os que são necessários para fazerum calendário.


Duas conclusões


Duas conclusões

No passado:


Duas conclusões

No passado:

• um computador era umapessoanão umamáquina;


Duas conclusões

No passado:


• os cálculos estavam frequentemente associados àastronomia:


Duas conclusões

No passado:


• os cálculos estavam frequentemente associados àastronomia: calendário, eclipes, posição dosplanetas, etc.


Duas conclusões

No passado:


• os cálculos estavam frequentemente associados àastronomia: calendário, eclipes, posição dosplanetas, etc.

• tais cálculos são geralmente muito laboriosos.


Ideia perdida no tempo...


Ideia perdida no tempo...

Que tal inventar uma máquina capaz de efetuarcálculos repetitivos e laboriosos?


Alguns exemplos


Antikhytera, 100 a.C.


Antikhytera, 100 a.C.


Pascal, 1652


Pascal, 1652


Jacquard, 1801

Open House 2009 – p. 10/50

Jacquard, 1801

Open House 2009 – p. 10/50

Babbage, 1822

Open House 2009 – p. 11/50

Babbage, 1822

Open House 2009 – p. 11/50

Babbage, 1837

Open House 2009 – p. 12/50

Babbage, 1837O analytical engine:

Open House 2009 – p. 12/50


• movido a vapor;

Open House 2009 – p. 12/50


• movido a vapor;• totalmente programável;

Open House 2009 – p. 12/50


• movido a vapor;• totalmente programável;• usava cartões perfurados como Jacquard;

Open House 2009 – p. 12/50


• movido a vapor;• totalmente programável;• usava cartões perfurados como Jacquard;• saída seria impressa;

Open House 2009 – p. 12/50


• movido a vapor;• totalmente programável;• usava cartões perfurados como Jacquard;• saída seria impressa;• linguagem semelhante a “assembler”;

Open House 2009 – p. 12/50


• movido a vapor;• totalmente programável;• usava cartões perfurados como Jacquard;• saída seria impressa;• linguagem semelhante a “assembler”;• nunca chegou a ser construído.

Open House 2009 – p. 12/50

Ada Lovelace, 1815-1852

Open House 2009 – p. 13/50

Ada Lovelace, 1815-1852

Open House 2009 – p. 13/50

Ada Lovelace, 1842

Open House 2009 – p. 14/50

Ada Lovelace, 1842

“Podemos dizer de maneira muito apta que oAnalytical Engine tece padrões algébricos exatamentecomo o tear de Jacquard tece flores e folhas.”

Open House 2009 – p. 14/50

Ada Lovelace, 1842

“Podemos dizer de maneira muito apta que oAnalytical Engine tece padrões algébricos exatamentecomo o tear de Jacquard tece flores e folhas.”

Escreveu programas para amáquina anlíticadeBabbage.

Open House 2009 – p. 14/50

Porém,

Open House 2009 – p. 15/50

Porém,

A ciência da computação é sobre computadores tantoquanto a astronomia é sobre telescópios.

Open House 2009 – p. 15/50

Porém,

A ciência da computação é sobre computadores tantoquanto a astronomia é sobre telescópios.

E. W. Dijkstra

Open House 2009 – p. 15/50

Edsger Dijkstra, 1930-2002

Open House 2009 – p. 16/50

Edsger Dijkstra, 1930-2002

Open House 2009 – p. 16/50

Quem foi Dijkstra?

Open House 2009 – p. 17/50

Quem foi Dijkstra?Pioneiro da computação,

Open House 2009 – p. 17/50

Quem foi Dijkstra?Pioneiro da computação,programadordaUniversidade de Amsterdam entre 1952 e 1962.

Open House 2009 – p. 17/50

Quem foi Dijkstra?Pioneiro da computação,programadordaUniversidade de Amsterdam entre 1952 e 1962.Contribuiu para:

Open House 2009 – p. 17/50


• linguagens de programação;

Open House 2009 – p. 17/50


• linguagens de programação;• sistemas operacionais;

Open House 2009 – p. 17/50


• linguagens de programação;• sistemas operacionais;• processamento distribuído;

Open House 2009 – p. 17/50


• linguagens de programação;• sistemas operacionais;• processamento distribuído;• especificação formal de programas;

Open House 2009 – p. 17/50


• linguagens de programação;• sistemas operacionais;• processamento distribuído;• especificação formal de programas;• desenvolvimento de algoritmos;

Open House 2009 – p. 17/50


• linguagens de programação;• sistemas operacionais;• processamento distribuído;• especificação formal de programas;• desenvolvimento de algoritmos;• desenvolvimento de programas;

Open House 2009 – p. 17/50


• linguagens de programação;• sistemas operacionais;• processamento distribuído;• especificação formal de programas;• desenvolvimento de algoritmos;• desenvolvimento de programas;• desenvolvimento de argumentos matemáticos.

Open House 2009 – p. 17/50


... quase tudo ...

Open House 2009 – p. 17/50

Definição

Open House 2009 – p. 18/50

Definição

A Ciência da Computação é sobre

Open House 2009 – p. 18/50

Definição

A Ciência da Computação é sobre computação;

Open House 2009 – p. 18/50

Definição

A Ciência da Computação é sobre computação; isto é:

Open House 2009 – p. 18/50

Definição

A Ciência da Computação é sobre computação; isto é:• o que deve ser uma computação;

Open House 2009 – p. 18/50

Definição

A Ciência da Computação é sobre computação; isto é:• o que deve ser uma computação;• o que pode e o que não pode ser computado;

Open House 2009 – p. 18/50

Definição

A Ciência da Computação é sobre computação; isto é:• o que deve ser uma computação;• o que pode e o que não pode ser computado;• como fazê-lo quando é possível;

Open House 2009 – p. 18/50

Definição

A Ciência da Computação é sobre computação; isto é:• o que deve ser uma computação;• o que pode e o que não pode ser computado;• como fazê-lo quando é possível;• qual o custo de uma computação;

Open House 2009 – p. 18/50

Definição

A Ciência da Computação é sobre computação; isto é:• o que deve ser uma computação;• o que pode e o que não pode ser computado;• como fazê-lo quando é possível;• qual o custo de uma computação;

e coisas do gênero.

Open House 2009 – p. 18/50

O que é uma computação?

Open House 2009 – p. 19/50

Alan Turing, 1912-1954

Open House 2009 – p. 20/50

Alan Turing, 1912-1954

Open House 2009 – p. 20/50

O que um computador faz?

Open House 2009 – p. 21/50


Segundo Turing,

Open House 2009 – p. 21/50


Segundo Turing, o que um “computador humano”efetuando cálculos segundo regras pré-estabelecidasfaz resume-se em:

Open House 2009 – p. 21/50



• ler uma instrução e guardá-la na memória;

Open House 2009 – p. 21/50



• ler uma instrução e guardá-la na memória;• escrever símbolos em um papel quadriculado;

Open House 2009 – p. 21/50



• ler uma instrução e guardá-la na memória;• escrever símbolos em um papel quadriculado;• manipular estes símbolos, escrevendo-os ou

apagando-os.

Open House 2009 – p. 21/50


Open House 2009 – p. 22/50


Portanto,

Open House 2009 – p. 22/50


Portanto, uma máquina que imita um “computadorhumano” precisa de:

Open House 2009 – p. 22/50



• um “estado mental” onde lembrar as instruções;

Open House 2009 – p. 22/50



• um “estado mental” onde lembrar as instruções;• uma memória equivalente ao papel quadriculado;

Open House 2009 – p. 22/50



• um “estado mental” onde lembrar as instruções;• uma memória equivalente ao papel quadriculado;• capacidade de escrever e apagar da memória e de

mudar seu “estado mental”.

Open House 2009 – p. 22/50

Ideia-chave do Turing

Open House 2009 – p. 23/50


Existe uma máquina capaz de executar qualquerprograma que se possa fazer.

Open House 2009 – p. 23/50



Isto não é óbvio:

Open House 2009 – p. 23/50



Isto não é óbvio: a demonstração é dada ao final docurso de linguagens formais.

Open House 2009 – p. 23/50



Em sua versão abstrata, tais máquinas são conhecidascomoMáquinas de Turing Universais.

Open House 2009 – p. 23/50



Em sua versão abstrata, tais máquinas são conhecidascomoMáquinas de Turing Universais. Sua versãoconcreta é chamada simplesmente

Open House 2009 – p. 23/50



Em sua versão abstrata, tais máquinas são conhecidascomoMáquinas de Turing Universais. Sua versãoconcreta é chamada simplesmente computador.

Open House 2009 – p. 23/50

Tese de Church-Turing

Open House 2009 – p. 24/50


Um problema admite umasolução computacionalseexiste um programa que resolve este problema e quepode ser implementado em

Open House 2009 – p. 24/50


Um problema admite umasolução computacionalseexiste um programa que resolve este problema e quepode ser implementado em uma máquina de Turing

Open House 2009 – p. 24/50


Um problema admite umasolução computacionalseexiste um programa que resolve este problema e quepode ser implementado em um computador.

Open House 2009 – p. 24/50

Existe algum problema que nãopossa ser resolvido

computacionalmente?

Open House 2009 – p. 25/50

Alan Turing, 1936

Open House 2009 – p. 26/50

Alan Turing, 1936

SIM!

Open House 2009 – p. 26/50

Problema da parada

Open House 2009 – p. 27/50

Problema da parada

Existe um programaH capaz de decidir

Open House 2009 – p. 27/50

Problema da parada


dado um programa qualquerP e uma entradaE deP

Open House 2009 – p. 27/50

Problema da parada



seP para ou não com entradaE?

Open House 2009 – p. 27/50

Problema da parada




Este não foi o problema original tratado pelo Turing,

Open House 2009 – p. 27/50

Problema da parada




Este não foi o problema original tratado pelo Turing,o problema original chama-se

Open House 2009 – p. 27/50

Problema da parada




Este não foi o problema original tratado pelo Turing,o problema original chama-se Entscheidungsproblem

Open House 2009 – p. 27/50

Problema da parada




Este não foi o problema original tratado pelo Turing,o problema original chama-se Problema da decisão.

Open House 2009 – p. 27/50

Problema da parada




Este não foi o problema original tratado pelo Turing,o problema original chama-se Problema da decisão.O problema da paradadata de 1952.

Open House 2009 – p. 27/50

Problema da parada




Usando ideias do Turing podemos provar que:

Open House 2009 – p. 27/50

Problema da parada




Usando ideias do Turing podemos provar que:

não existe um programaH que resolva oproblema da parada!

Open House 2009 – p. 27/50

Problema da parada

Open House 2009 – p. 28/50

Problema da parada

Ideia fundamental:

Open House 2009 – p. 28/50

Problema da parada

Ideia fundamental:

reduzir o problema a um paradoxo deauto-referência.

Open House 2009 – p. 28/50

Paradoxo

Open House 2009 – p. 29/50

Paradoxo

Segundo a Wikipedia:

Open House 2009 – p. 29/50

Paradoxo

Segundo a Wikipedia:

paradoxo é uma declaração aparentementeverdadeira que leva a uma contradiçãológica, ou a uma situação que contradiz aintuição comum.

Open House 2009 – p. 29/50

Alguns exemplos

Open House 2009 – p. 30/50

Paradoxo de Zeno

Open House 2009 – p. 31/50

Paradoxo de Zeno

Aquiles vai correr contra uma tartaruga.

Open House 2009 – p. 31/50

Paradoxo de Zeno

Como a tartaruga tem a metade da sua velocidade,Aquiles deixa que parta 100 m à sua frente.

A T

Open House 2009 – p. 31/50

Paradoxo de Zeno

Quando Aquiles percorrer os 100 m a tartarugapercorreu 50m e continua à sua frente.

A T

A T

Open House 2009 – p. 31/50

Paradoxo de Zeno

Quando Aquiles percorrer os 50 m a tartarugapercorreu 25m e continua à sua frente.

A T

A T

A T

Open House 2009 – p. 31/50

Paradoxo de Zeno

Continuando assim, Aquiles nunca alcançará atartaruga!

A T

A T

A T

Open House 2009 – p. 31/50

Paradoxo de Zeno


Conclusão do Zeno:

Open House 2009 – p. 31/50

Paradoxo de Zeno


Conclusão do Zeno: não existe movimento!

Open House 2009 – p. 31/50

M. C. Escher

Open House 2009 – p. 32/50

M. C. Escher

Uma imagem paradoxal.

Open House 2009 – p. 32/50

M. C. Escher

Uma imagem paradoxal.

Open House 2009 – p. 32/50

M. C. Escher

Open House 2009 – p. 33/50

M. C. Escher

Uma imagem paradoxal, com auto-referência.

Open House 2009 – p. 33/50

M. C. Escher

Uma imagem paradoxal, com auto-referência.

Open House 2009 – p. 33/50

O Problema da Parada

Open House 2009 – p. 34/50


Suponha que o programaH existe.

Open House 2009 – p. 34/50



(P,E) // H //SIM

��

NÃO

Open House 2009 – p. 34/50



(P,E) // H //SIM

��

NÃOSIM = P para com entrada E.

Open House 2009 – p. 34/50



(P,E) // H //SIM

��

NÃOSIM = P para com entrada E.NÃO = P não para com entrada E.

Open House 2009 – p. 34/50



P //(P,P) // H //SIM

��

NÃO

Open House 2009 – p. 35/50



P //(P,P) // H //LOOP

��

NÃO

Open House 2009 – p. 36/50



P //(P,P) // H //LOOP

��

NÃOLOOP = o programa entra em loop infinito e não para

Open House 2009 – p. 36/50


SeH existe entãoH também existe.

P //H

//LOOP

��

NÃO

Open House 2009 – p. 37/50

O que obtemos se dermos aH aentrada H?

Open House 2009 – p. 38/50


Open House 2009 – p. 39/50


H(P ) =

{

NÃO seP nãopara com entradaP .LOOP seP para com entradaP .

Open House 2009 – p. 39/50


H(P ) =

{


SuponhamosH(H) = NÃO

Open House 2009 – p. 39/50


H(P ) =

{


SuponhamosH(H) = NÃO⇒ H(H, H) = SIM

Open House 2009 – p. 39/50


H(P ) =

{


SuponhamosH(H) = NÃO⇒ H(H, H) = SIM⇒ H entra em LOOP com entradaH.

Open House 2009 – p. 39/50


H(P ) =

{


SuponhamosH(H) = NÃO⇒ H(H, H) = SIM⇒ H entra em LOOP com entradaH.Contradição.

Open House 2009 – p. 39/50


H(P ) =

{


SuponhamosH(H) = LOOP.

Open House 2009 – p. 39/50


H(P ) =

{


SuponhamosH(H) = LOOP.⇒ H(H, H) = NÃO.

Open House 2009 – p. 39/50


H(P ) =

{


SuponhamosH(H) = LOOP.⇒ H(H, H) = NÃO.⇒ H para com entradaH e tem saída NÃO.

Open House 2009 – p. 39/50


H(P ) =

{


SuponhamosH(H) = LOOP.⇒ H(H, H) = NÃO.⇒ H para com entradaH e tem saída NÃO.Contradição.

Open House 2009 – p. 39/50


H(P ) =

{


Portanto:

Open House 2009 – p. 39/50


H(P ) =

{


Portanto:

não importa o que aconteça, obtemos umacontradição.

Open House 2009 – p. 39/50

Não computabilidade

Outros problemas não computáveis incluem:

Open House 2009 – p. 40/50



• antivírus universal;

Open House 2009 – p. 40/50




• descompilação;

Open House 2009 – p. 40/50




• descompilação;

• soluções de equações diofantinas.

Open House 2009 – p. 40/50

Contribuições do Turing

Open House 2009 – p. 41/50


• modelo de computação;

Open House 2009 – p. 41/50


• modelo de computação;• problemas não computáveis;

Open House 2009 – p. 41/50


• modelo de computação;• problemas não computáveis;• o Bombe;

Open House 2009 – p. 41/50


• modelo de computação;• problemas não computáveis;• o Bombe;• Manchester Mark 1;

Open House 2009 – p. 41/50


• modelo de computação;• problemas não computáveis;• o Bombe;• Manchester Mark 1;• as bases químicas da morfogênese;

Open House 2009 – p. 41/50


• modelo de computação;• problemas não computáveis;• o Bombe;• Manchester Mark 1;• as bases químicas da morfogênese;• primeiras simulações em computador;

Open House 2009 – p. 41/50


• modelo de computação;• problemas não computáveis;• o Bombe;• Manchester Mark 1;• as bases químicas da morfogênese;• primeiras simulações em computador;• teste de Turing.

Open House 2009 – p. 41/50

O Manchester Mark 1, 1949

Open House 2009 – p. 42/50

O Manchester Mark 1, 1949

Open House 2009 – p. 42/50

Porém,

Open House 2009 – p. 43/50

Porém,

Perguntar se uma máquina pode pensar...é tãorelevante quanto perguntar se um submarino podenadar...

Open House 2009 – p. 43/50

Porém,

Perguntar se uma máquina pode pensar...é tãorelevante quanto perguntar se um submarino podenadar...

E. Dijkstra

Open House 2009 – p. 43/50

Como resolver um problemacomputacionalmente quando é

possível?

Open House 2009 – p. 44/50

Solução computacional

Open House 2009 – p. 45/50


Não existe receita universal,

Open House 2009 – p. 45/50


Não existe receita universal, nem existe métodouniversal para encontrá-las

Open House 2009 – p. 45/50


Não existe receita universal, nem existe métodouniversal para encontrá-las

Cada caso é um caso!

Open House 2009 – p. 45/50

Alguns exemplos

Open House 2009 – p. 46/50

Alguns exemplos

• busca binária: combinatória;

Open House 2009 – p. 46/50

Alguns exemplos


• fatoração: teoria de números;

Open House 2009 – p. 46/50

Alguns exemplos



• fractais: cálculo;

Open House 2009 – p. 46/50

Alguns exemplos




• “ray tracing”: óptica;

Open House 2009 – p. 46/50

Alguns exemplos





• criptografia quântica: mecânica quântica;

Open House 2009 – p. 46/50

Alguns exemplos





• criptografia quântica: mecânica quântica;

• movimento de líquidos e gases: mecânica dosfluidos.

Open House 2009 – p. 46/50

Computação segundo o Dijkstra

Open House 2009 – p. 47/50


...isto nos dá uma indicação clara de onde localizar aciência da computação no mapa-mundi das disciplinasintelectuais:

Open House 2009 – p. 47/50


...isto nos dá uma indicação clara de onde localizar aciência da computação no mapa-mundi das disciplinasintelectuais: na direção da matemática formal e dalógica aplicada,

Open House 2009 – p. 47/50


...isto nos dá uma indicação clara de onde localizar aciência da computação no mapa-mundi das disciplinasintelectuais: na direção da matemática formal e dalógica aplicada, mas, em última análise, muito alémde onde estas se encontram atualmente,

Open House 2009 – p. 47/50


...isto nos dá uma indicação clara de onde localizar aciência da computação no mapa-mundi das disciplinasintelectuais: na direção da matemática formal e dalógica aplicada, mas, em última análise, muito alémde onde estas se encontram atualmente, porque aciência da computação está interessada no uso efetivode métodos formais e em escala muito, muito maiordo que testemunhamos até agora.

Open House 2009 – p. 47/50

Mais opiniões do Dijkstra

Open House 2009 – p. 48/50

Quatro conselhos impopulares

Open House 2009 – p. 49/50

Quatro conselhos impopularesTestar um programa pode ser usado para indicar apresença de bugs,

Open House 2009 – p. 49/50

Quatro conselhos impopularesTestar um programa pode ser usado para indicar apresença de bugs, mas nunca a sua ausência!

Open House 2009 – p. 49/50


A exploração efetiva de seus próprios poderes deabstração deve ser considerada como uma dasatividades mais vitais de um programador competente.

Open House 2009 – p. 49/50


A exploração efetiva de seus próprios poderes deabstraçãodeve ser considerada como uma dasatividades mais vitais de um programador competente.

Open House 2009 – p. 49/50



Além de inclinação para a matemática,

Open House 2009 – p. 49/50



Além de inclinação para a matemática, um domínioexcepcionalmente bom de sua língua nativa é um dosrecursos mais vitais de um programador competente.

Open House 2009 – p. 49/50




Como convencer as pessoas de que, em programação,simplicidade e clareza

Open House 2009 – p. 49/50




Como convencer as pessoas de que, em programação,simplicidade e clareza – o que os matemáticoschaman “elegância” –

Open House 2009 – p. 49/50




Como convencer as pessoas de que, em programação,simplicidade e clareza – o que os matemáticos chaman“elegância” – não são luxos dispensáveis, but questõescruciais, que decidem entre sucesso e fracasso?

Open House 2009 – p. 49/50

Um pensamento final

Open House 2009 – p. 50/50

Um pensamento final

Não é tarefa da universidade oferecer o que asociedade pede,

Open House 2009 – p. 50/50

Um pensamento final

Não é tarefa da universidade oferecer o que asociedade pede, mas sim aquilo que a sociedadeprecisa.

Open House 2009 – p. 50/50

Um pensamento final

Não é tarefa da universidade oferecer o que asociedade pede, mas sim aquilo que a sociedadeprecisa.

E. Dijkstra

Open House 2009 – p. 50/50

Documents

Em que consiste a ciência, na computação? - dcc.ufrj.brcollier/Palestras/computacao.pdf · Algumas perguntas O que é ciência da computação? O que é um computador ? Existia