A COMPUTAÇÃO MODERNA
Valdemar W. Setzer
Depto. de Ciência da Computação da USP
www.ime.usp.br/~vwsetzer
1
Tópicos importantes no ensino
 O que é um computador
 Usar o Computador a papel e o HIPO
 O que é um algoritmo, como se
desenvolve, complexidade, problemas
intratáveis, etc.

Para isso, usar minha técnica de atividade
usando ordenação (ver detalhes em meu
artigo em meu site)
2
Introdução aos algoritmos
 Regras da atividade
 É possível examinar o conteúdo de um cartão,
isto é, o número nele inscrito.
 Se o número de um cartão estiver tapado, ele é
considerado desconhecido. O operador não
pode memorizar os conteúdos dos cartões.
 No máximo 2 cartões podem ser examinados ao
mesmo tempo para se ver seu número.
 Os números de 2 cartões abertos podem ser
comparados, determinado-se qual possui o
menor número.
 Dois cartões podem ser trocados de lugar.
3
Método de seleção
(Compara o 1o. com cada um dos outros, troca quando
ele for maior; depois compara o 2o. com cada um dos
outros, etc.)
5 10 3 7 15 2 1 9
1 10 5 7 15 3 2 9
5 10 3 7 15 2 1 9
1 5 10 7 15 3 2 9
3 10 5 7 15 2 1 9
1 3 10 7 15 5 2 9
2 10 5 7 15 3 1 9
1 2 10 7 15 5 3 9
1 10 5 7 15 3 2 9
1 2 10 7 15 5 3 9
1 2 9
7 15 5 3 10
4
Método da bolha
(Compara o 1o. com o 2o, troca se o 1o. for maior; depois
compara o 2o. com 3o. e troca se for maior, etc.)
5 10 3 7 15 2 1 9
1 5 7 10 3 2 15 9
5 10 3 7 15 2 1 9
1 5 7 10 3 2 9 15
3 5 10 7 15 2 1 9
1 5 7 10 3 2 9 15
2 5 7 10 15 3 1 9
1 5 7 10 3 2 9 15
1 5 7 10 15 3 2 9
1 5 7 10 3 2 9 15
1 5 7 10 3 15 2 9
1 5 7 3 10 2 9 15
5
Método de inserção
(Compara cada par consecutivo; quando houver troca,
compara para trás e troca se necessário)
5 10 3 7 15 2 1 9
3 5 7 10 15 2 1 9
5 10 3 7 15 2 1 9
3 5 7 10 2 15 1 9
5 3 10 7 15 2 1 9
3 5 7 2 10 15 1 9
3 5 10 7 15 2 1 9
3 5 2 7 10 15 1 9
3 5 7 10 15 2 1 9
3 2 5 7 10 15 1 9
3 5 7 10 15 2 1 9
3 2 5 7 10 1 15 9
6
Complexidade dos algoritmos
Critério: vamos usar o número de comparações
Seleção e bolha:
(n-1) + (n-2) + ... + 1 = n(n-1)/2
Inserção:
Inicialmente ordenada: n-1
Pior caso: n(n-1)/2
Valor assintótico de todos (n ): n2/2
NOTAÇÃO: O(n2)
7
Um método mais eficiente: ordenação por
árvore binária
Composta por nós e arestas
Nível
Raiz
0
1
2
3
Folhas
4
8
Uma árvore binária é uma estrutura de
dados em que cada nó tem no máximo 2
filhos e um só pai.
ou (definição indutiva)
Uma estrutura de dados de um só nó é uma
árvore binária; dado um nó de uma árvore
binária, a ele são associadas no máximo
duas árvores binárias.
9
Ordenação por
árvore binária
1
2
3
5
7
9
10
15
3
5
7
10
1
2
9
15
5
10
5
3
7
10
3
2
15
7
15
1
9
2
1
9
10
Nível Nós Total
de nós
0
1
1
1
2
3
2
4
7
3
8
15
4
16
31
...
...
...
m
2
m
m+1
2
-1
11
Nível
Nós No.compar.
0
1
n-1
1
2
n-2
2
4
n-4
3
8
n-8
4
16
n-16
...
...
...
m-1
m
m-1
2
m
2 =n
n-n/2
n-n=0
No. total de comparações: C = (n-1)+(n-2)+(n-4)+(n-8)+...+(n-n/2)
Como há m termos (0 a m-1) a serem somados,
C = mn - (1 + 2 + 4 + 8 + ... + n/2) = mn - (2(n/2) - 1)
12
Isto é,
C = mn - n + 1
Mas
m
2 =n
portanto
m
log2 2 = log2 n

m log2 2 = log2 n
m = log2 n
O número total de comparações será então
C = (log2 n)n - n + 1 = n log2 n - n + 1
isto é, assintoticamente, O(n log2 n)
13
Comparação com os métodos quadráticos
n
n (n -1)/2 n log2n - n + 1
1
0
2
1
4
6
8
28
16
120
32
496
64
2.016
128
8.028
256
32.640
512
130.816
1.024
523.776
2.048
2.096.128
4.096
8.386.560
8.192
33.550.336
...
...
131.072 8.589.869.056
0
1
5
17
49
129
321
769
1.793
4.097
9.217
20.481
45.057
98.305
...
2.097.153
Para 1.000.000 comparações/s:
131.072
6 dias
19 s
14
Espaço requerido
Em cada nível, temos n elementos; como são m = log2 n
níveis, o total de espaço requerido é de
n log2 n
posições (cada uma contendo um número).
Variação: usar apenas 2 linhas (ao fazer a intercalação,
passa-se o resultado para a outra linha). Cada uma terá n
elementos, de modo que o espaço requerido será
2n
15
Espaço requerido (cont.)
Variação: 2 linhas com total de 2n posições (ao fazer a
intercalação, passa-se o resultado para a outra linha)
1)
5
10
3
7
15
2
1
9
2)
5
10
3
7
2
15
1
9
1)
3
5
7
10
1
2
9
15
2)
1
2
3
5
7
9
10
15
Existem métodos com somente n posições (in-line merge).
O método que se usa é dessa categoria, o Quicksort, que
não usa intercalação.
16
Outras aplicações de árvores de dados
Jogos
Situação atual do jogo
Possíveis lances
Possíveis situações seguintes
Problema: como ir podando a árvore, pois ela cresce
exponencialmente  estratégias (cálculo de parâmetros de
vantagem conforme a posição)
17
Outras aplicações de árvores de dados
(cont.)
Árvores de busca
Usadas em gerenciadores de bancos de
dados, como o Access (“Árvores-B”)
18
Tópicos importantes no ensino (cont.)
 O que é um algoritmo?
 Uma seqüência finita de passos,
executados individualmente, cada um
matematicamente bem definido
 Normalmente, depois de executado um
passo, o passo seguinte da seqüência será
o próximo a ser executado
 Um passo pode indicar uma mudança na
ordem de execução, determinando qual
passo da seqüência deve ser executado em
seguida (desvio)
 A execução deve terminar
19
Tópicos importantes no ensino (cont.)
 Problemas causados pelo computador
 Triviais: perda da privacidade, diminuição
de empregos, etc.
 Profundos: influência na capacidade e na
maneira de pensar
 pois força um pensamento lógico-simbólico,
algorítmico e uma linguagem formal,
qualquer uso e exige enorme auto-controle

em
IMPRÓPRIO ANTES DOS 17 ANOS!!!
Mais profundos: influência na mentalidade
 Nunca houve uma metáfora tão grande para a
visão de mundo de que o ser humano é uma
máquina
20
Tópicos importantes no ensino (cont.)
 Problemas causados pelo computador
(cont.)

Conseqüências da visão de mundo de que
o ser humano é uma máquina: não fazem
sentido
 Liberdade
 Responsabilidade
 Dignidade
 Individualidade (que transcende o corpo)
 Compaixão (animais não têm!)
 Amor altruísta
21
Tópicos importantes no ensino (cont.)

Conseqüências da visão de mundo de que
o ser humano é uma máquina (cont.)
 Causa de grande parte da miséria social e
individual que está continuamente aumentando
 Pensamentos de máquina (isto é, que podem
ser introduzidos em uma máquina)
 Abafamento dos sentimentos (especialmente
compaixão)
 Ações bestiais (inconscientes)
22
Tópicos importantes no ensino (cont.)
 Solução:
educar para a visão de
mundo de que
O SER HUMANO NÃO É UMA MÁQUINA!
Ver meu artigo
“I.A.
Inteligância
Artificial
ou
Imbecilidade Automática? As máquinas
podem pensar e ter sentimentos?”
em meu site.
23