1. Apresentação do curso¶
Página do curso: http://paca.ime.usp.br¶
- Linguagem: Python 3
- Avaliação
- Presença
- Monitoria
- Vídeos do Coursera
- Aulas/Livro interativos
- Pré-requisitos (preciso saber programar??)
Ábaco (possivelmente Mesopotâmia, ca 2700-2300 AC)¶
- representação de inteiros e racionais em base 10 (mas existem ábacos em bases 2, 4, 5, 16, 20, 60...)
- operações: +, -, *, /, $\sqrt[2]{\;\;}$, $\sqrt[3]{\;\;}$
In [38]:
# Exemplo de representação numérica em um ábaco
YouTubeVideo('cJvNtiRygY8',start=42, end=85)
Out[38]:
In [39]:
# Exemplo de uso eficiente de um ábaco
YouTubeVideo('GQtqlB-jXO0',start=8)
Out[39]:
Pascaline (Blaise Pascal, 1642)¶
- calculadora mecânica
- operações: +, - (e indiretamente *, /)
- mecanização do "vai 1"
- Gottfried Leibniz introduziu em 1671 a multiplicação automática na Pascaline (Rodas de Leibniz, 1671)
In [40]:
# Funcionamento do Pascaline: 985+547+9724=11256
YouTubeVideo('olfNFXJEZOA',start=36, end=99)
Out[40]:
In [41]:
# Mecanismo do Pascaline: conta-giros
YouTubeVideo('Fv1IawE3Hw4',start=24, end=57)
Out[41]:
Tear de Jacquard (Joseph Marie Jacquard, 1804)¶
- codifica padrões de tecelagem em cartões perfurados (sistema binário)
- acelera a realização de padrões complexos reduzindo a probabilidade de falhas
- foi utilizado de forma automática usando eixos de transmissão
In [42]:
# Tear de Jacquard para a confecção de padrões elaborados com cartões perfurados
YouTubeVideo('K6NgMNvK52A',start=72, end=164)
Out[42]:
Dispositivo conceitual¶
Engenho Analítico (Charles Babbage, 1837)¶
- projeto de computador mecânico de uso geral
- previa uma unidade lógico-aritmética, controle de fluxo de execução (desvios condicionais e loops) e memória integrada
- nunca foi construída por falta de financiamento
- inspirou o desenvolvimento de inúmeros algoritmos pela primeira programadora da história: Ada Lovelace
In [43]:
# Ada Lovelace e o Engenho Analítico
YouTubeVideo('bYCDVwyuVt4',start=0)
Out[43]:
Dispositivos eletromecânicos¶
Máquina de Hollerith (Hermann Hollerith, 1889)¶
- usada para automatizar a contabilidade dos dados do censo americano de 1890
- usava cartões perfurados com as respostas tabuladas pelos pesquisadores
- relés eletromecânicos permitiam incrementar um contador específico para cada furo no cartão
- reduziu o tempo de processamento dos dados do censo de vários anos para algumas semanas
- Hollerith fundou a Tabulating Machine Company em 1896, rebatizada International Business Machines em 1924
In [44]:
# Máquina de Hollerith para o censo americano de 1890
YouTubeVideo('9HXjLW7v-II',start=106, end=168)
Out[44]:
Enigma e Turing (1939)¶
- Durante a II Guerra Mundial os Alemães criptografavam mensagens usando a máquina Enigma
- Alan Turing construiu a máquina "The Bombe" para decifrar as mensagens escritas com Enigma
- The Bombe funcionava como várias máquinas Enigma acopladas
- Possíveis configurações válidas eram verificadas posteriormente por seres humanos
- Filme relacionado: The Imitation Game
In [45]:
# A falha na máquina Enigma que permitiu a Alan Turing criar o "The Bombe"
YouTubeVideo('V4V2bpZlqx8',start=35, end=160)
Out[45]:
Colossus I (1943) - 1° computador eletrônico de uso específico¶
- usado para quebrar o código Lorenz, sucessor do Enigma
- desenvolvido no mesmo lugar que o "The Bombe" (Bletchley Park)
- programável através de interruptores e cabos
- ao invés de relés e engrenagens usava válvulas (muito mais rápidas)
- baseado em representação binária e lógica Booleana
- desmontado em segredo após o final da guerra
In [46]:
# Colossus - 1° computador eletrônico
YouTubeVideo('knXWMjIA59c',start=215, end=335)
Out[46]:
Dispositivo conceitual¶
Máquina de Turing (Alan Turing, 1936) - Modelo de computador universal¶
- construção abstrata para realizar computações em geral
- possui memória infinita (uma fita com 0's e 1's)
- uma unidade de leitura/escrita se movimenta sobre a fita, realizando alterações nos valores armazenados
- permite representar qualquer algoritmo
In [47]:
# Máquina de Turing
YouTubeVideo('gJQTFhkhwPA',start=0, end=137)
Out[47]:
Harvard Mark I (1944) - 1° computador eletromecânico de uso geral¶
- inspirado no engenho analítico de Charles Babbage
- baseado em interruptores, relés, eixos rotativos e embreagens
- usado por John von Neumann para testar a viabilidade do método da Implosão (Projeto Manhattan)
- baseado em representação binária de dados através de chaves
- leitura de instruções a partir de cartões perfurados
- resposta produzida por máquinas de escrever automáticas
In [48]:
# Harvard/IBM Mark I - 1° computador eletro-mecânico programável
YouTubeVideo('OMO9a2h-s2I',start=77, end=135)
Out[48]:
Dispositivos eletrônicos¶
ENIAC (1945) - 1° computador eletrônico de uso geral¶
- projetado por Mauchly & Eckert na Universidade de Pennsylvania
- usava válvulas, diodos, relés, resistores e capacitores
- baseado em representação decimal
- leitura e impressão de dados por cartões perfurados
- programação feita por chaves e cabos
In [49]:
# ENIAC programmers
YouTubeVideo('_J7THWDSKFY',start=0, end=195)
Out[49]:
In [50]:
# Illiac Suite (1956)
YouTubeVideo('n0njBFLQSk8',start=0, end=29)
Out[50]:
3. Representação e manipulação de dados¶
- codificação/decodificação
- eficiência
- espaço de armazenamento
- tempo de acesso
- robustez
- interferências
- ataques
- conveniência
- facilidade de manipulação
- legibilidade
Exemplo de notação inconveniente: $$\Huge\begin{array}{r} \mbox{MMXVIII}\\ \mbox{-XLIV}\\\hline \mbox{??????}\end{array}$$
Solução $$\Huge\begin{array}{r} \mbox{MMXVIII}\\ \mbox{-XLIV}\\\hline \mbox{MCMLXXIV}\end{array}$$
In [51]:
# discussão: representação decimal x binária
# fatores que podem tornar difícil o discernimento entre
# muitos níveis de cor/energia/intensidade em um código
Dec = np.round(np.linspace(255,0,10))
Bin = np.round(np.linspace(255,0,2))
Dec = [ Dec, Dec ]
Bin = [ Bin, Bin ]
plt.subplot(2,1,1)
plt.imshow(Dec,cmap='gray', interpolation='none')
plt.xticks([], [])
plt.yticks([], [])
plt.subplot(2,1,2)
plt.imshow(Bin,cmap='gray', aspect=0.2, interpolation='none')
plt.xticks([], [])
plt.yticks([], [])
Out[51]:
In [52]:
# gera um quadrado de cor aleatória
val = [ np.random.randint(10)*25.5 ]
val = [ val, val ]
print(str(int(val[0][0]/25.5)))
plt.imshow(val, vmin = 0, vmax = 255, cmap='gray', aspect = 0.5, interpolation='none')
plt.xticks([], [])
plt.yticks([], [])
Out[52]:
- algoritmos
- eficiência
- uso de memória
- tempo de execução
- robustez
- adaptabilidade
- gerenciamento de exceções
- conveniência
- portabilidade
- modularidade
- legibilidade
4. Atividade prática:¶
uso do sistema binário de representação e adição em binário¶
Sistema decimal: $$(101)_{10} = 1*10^2+0*10^1+1*10^0 = 1*100+0*10+1*1$$
Sistema binário: $$(101)_{2} = 1*2^2+0*2^1+1*2^0 = 1*4+0*2+1*1$$
Potências de 2: $$1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192\ldots$$
Passagem de binário para decimal: soma-se as potências de 2 dos bits "ligados"
$$(101)_2 = 2^2+2^0 = 5$$
- Passagem de decimal para binário: soma-se todas as potências de 2 que "cabem"
$$(101)_{10} = 64+32+4+1 = 2^6+2^5+2^2+2^0 = (1100101)_{10}$$
- Soma em binário: igual em decimal (sqn!)
$$\Huge\begin{array}{llll} {\large 1}&{\large 1}&{\large 1}&\\ &1&0&1\\ &+&1&1\\\hline 1&0&0&0\end{array}$$
Nosso primeiro algoritmo:¶
- Dividiremos a sala em grupos de 4 pessoas.
- Após as devidas apresentações, cada equipe coloca os nomes dos participantes em ordem lexicográfica crescente e decide quem começa com um jogo de 0-inho-ou-1: cada pessoa mostra um 0 ou 1, e sendo n a soma dos resultados, escolhe-se para começar o n-ésimo participante na ordem lexicográfica (se a soma for 0 repete-se a operação).
- O primeiro participante representa sua idade em binário (todos anotam), sem revelar em decimal o valor representado.
- O próximo participante em sentido horário (à esquerda do primeiro) soma ao valor anterior sua própria idade em binário, sem revelar sua idade em decimal (todos anotam o resultado), e assim se segue até o quarto participante.
- O primeiro participante então converte o resultado da soma para decimal.
- Ao final, todos anunciam suas idades em decimal, e verificam se a soma está certa.
- Se não estiver, o próximo passo da equipe será depurar em que etapa(s) houve erro(s) de cálculo.
In [53]:
# Computer History, Part 1: From Enigma to ENIAC and the UNIVAC.
YouTubeVideo('rO2SScF6rrM')
Out[53]:
In [54]:
# Computer History, Part 2: From IBM to Steve Jobs and Bill Gates.
YouTubeVideo('8r1KAjgZ5zQ')
Out[54]:
In [55]:
# Computer Pioneers: Pioneer Computers Part 1
YouTubeVideo('qundvme1Tik')
Out[55]:
In [56]:
# Computer Pioneers: Pioneer Computers Part 2
YouTubeVideo('wsirYCAocZk')
Out[56]:
Mulheres na computação¶
In [57]:
# Why Are There So Few Women in Computer Science?
YouTubeVideo('_ZjGOiJXVBA')
Out[57]:
In [58]:
# How Did Tech Become So Male-Dominated?
YouTubeVideo('OZ7zX6LalLI')
Out[58]:
In [59]:
# Women in the History of Computer Science, Panel Discussion
YouTubeVideo('iwpR5-OC-Z0')
Out[59]:
In [60]:
# TED Talks by Women in Computer Science
YouTubeVideo('d38LKbYfWrs',list='PL_cmA_chUzeaLY-ABcc6gEypDHBb4Od8x')
Out[60]:
Vídeos relacionados à atividade prática (soma em binário) e outros vídeos interessantes¶
In [61]:
# See How Computers Add Numbers In One Lesson:
YouTubeVideo('VBDoT8o4q00')
Out[61]:
In [62]:
# Why Do Computers Use 1s and 0s? Binary and Transistors Explained:
YouTubeVideo('Xpk67YzOn5w')
Out[62]:
In [63]:
# Como funciona a memória de computador - Kanawat Senanan
YouTubeVideo('p3q5zWCw8J4')
Out[63]:
In [64]:
# How do hard drives work? - Kanawat Senanan
YouTubeVideo('wteUW2sL7bc')
Out[64]: