Grandes ideias na teoria da ciência da computação

GREAT IDEASGREAT IDEASIN THEORETICAL COMPUTER SCIENCEIN THEORETICAL COMPUTER SCIENCE

EQUIPEEQUIPEDiego TavaresDiego TavaresRaiff AndersonRaiff Anderson

Tárcito LuaTárcito LuaVictor BatistaVictor Batista

GREAT IDEASGREAT IDEAS IN THEORETICAL COMPUTER SCIENCE IN THEORETICAL COMPUTER SCIENCE

O QUE É CIÊNCIA DA

COMPUTAÇÃO ?

• Computação não é apenas estudar programação

• O computador é uma ferramenta• Conjunto de ferramentas e ideias para a

compreensão de sistemas

O QUE É O QUE É CIÊNCIA DA COMPUTAÇÃOCIÊNCIA DA COMPUTAÇÃO??

• Maturidade matemática• Exercitar o raciocínio lógico• Estar preparado para estudar conteúdos

novos todo o tempo

O QUE É NECESSÁRIO O QUE É NECESSÁRIO PARA ENTENDER PARA ENTENDER COMPUTAÇÃO?COMPUTAÇÃO?

• O Bacharel em Ciência da Computação é o profissional capacitado a solucionar problemas do mundo real, por meio da construção de modelos computacionais e de sua implementação.

• Capacidade para aplicar seus conhecimentos de forma independente e inovadora, acompanhando a evolução de setor e contribuindo na busca de soluções nas diferentes áreas de aplicação da computação;

http://www.di.ufpb.br/node/14

O CIENTISTA O CIENTISTA DA COMPUTAÇÃODA COMPUTAÇÃO

FÍSICA X COMPUTAÇÃO

• A física é a ciência que estuda a natureza e seus fenômenos em seus aspectos mais gerais.

• Físicos buscam por irregularidades para encapsulá-las em leis gerais.

• Cientistas da computação geralmente trabalham no sentido oposto.

FÍSICA FÍSICA VERSUS VERSUS COMPUTAÇÃOCOMPUTAÇÃO

QUESTÕESMOTIVACIONAISMOTIVACIONAIS

• O que é um algoritmo?• O que é um programa?• Você sabia que existem diferentes tipos de

infinitos?

QUESTÕES QUESTÕES MOTIVACIONAISMOTIVACIONAIS

CRIANDO UM SITEDE APOSTAS ONLINE

• Criando um jogo de roleta online• Como será o jogo?• Como o jogador ganha ou perde?• Qual a probabilidade de ganhar?• O que pode dar errado?

CRIANDO UM SITE DE CRIANDO UM SITE DE APOSTAS ONLINEAPOSTAS ONLINE

FACTORINGFACTORING IS HARD IS HARD

FACTORINGFACTORING IS HARD IS HARD

• Computador Quântico?

O que Fazer então? O que Fazer então?

O que Fazer então? O que Fazer então?

• Alguns processos são extremamente difíceis de serem revertidos.

Física e ComputaçãoFísica e Computação

• Nível microscópico: • Nível macroscópico:

Factoring is Hard

• Site de Apostas Online– Realiza-se a implementação com multiplicações por

números grandes e primos.• Não apenas fatorar os números é difícil como também

determinar se o ultimo dígito de um dos fatores é ou não 7.

COMPASS ANDSTRAIGHTEDGESTRAIGHTEDGE

• Algoritmo criado na Grécia antiga usado para criar complexas figuras geométricas usando apenas régua e compasso.

• Analogamente na computação criamos algoritmos que usam um conjunto limitado de operações simples para resolver problemas complexos.

COMPASS AND COMPASS AND STRAIGHTEDGESTRAIGHTEDGE

O ALGORTIMO MDC DE EUCLIDESDE EUCLIDES

Como reduzir uma fração grande como 510/646 ao um termo menor?

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDES

Como reduzir uma fração grande como 510/646 ao um termo menor?

Fatorando !

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDES

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDESFatoraçãoFatoração

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDESFatoraçãoFatoração

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDESFatoraçãoFatoração

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDESFatoraçãoFatoração

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDES

A observação de A observação de EuclidesEuclides

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDESA observação de EuclidesA observação de Euclides

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDESA observação de EuclidesA observação de Euclides

B = q.A+rB = q.A+r

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDESA observação de EuclidesA observação de Euclides

B = q.A+rB = q.A+rr = B-q.Ar = B-q.A

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDESA observação de EuclidesA observação de Euclides

B = q.A+rB = q.A+rr = B-q.Ar = B-q.A

MDC(A,B)=MDC(r,A)MDC(A,B)=MDC(r,A)

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDESA observação de EuclidesA observação de Euclides

MDC(510,646) = MDC(136,510)MDC(510,646) = MDC(136,510)

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDESA observação de EuclidesA observação de Euclides

MDC(136,510) = MDC(102,136) MDC(136,510) = MDC(102,136)

MDC(102,136) = MDC(34,102) MDC(102,136) = MDC(34,102)

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDES

MDC(0,34) = 34MDC(0,34) = 34

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDES

MDC(0,34) = 34MDC(0,34) = 34

Se A for maior que B troque as posiçõesSe A for maior que B troque as posiçõesif(if(AA====00) {) {returnreturn B B;;} else {} else {

returnreturn MDC(A%B,A) MDC(A%B,A);;}}

• Quantos restos teremos que calcular?• Quão menor ficam os números a cada passo?

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDES

• Quantos restos teremos que calcular?• Quão menor ficam os números a cada passo?

B%A < B/2

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDES

• Quantos restos teremos que calcular?• Quão menor ficam os números a cada passo?

B%A < B/2

• Existe uma forma de torna-lo mais eficiente?

O ALGORITMO MDC DE O ALGORITMO MDC DE EUCLIDESEUCLIDES

CONSIDERAÇÕESFINAISFINAIS

• Espera-se que o Cientista da Computação saiba como resolver problemas - uma vez que isto é considerado mais importante do que acumular informações.

• Deve estar preparado para lidar com mudanças e enfrentar desafios.

CONSIDERAÇÕES CONSIDERAÇÕES FINAISFINAIS

GREAT IDEASGREAT IDEASIN THEORETICAL COMPUTER SCIENCEIN THEORETICAL COMPUTER SCIENCE