Mapa mental Pensamento Computacional - COM100 - resumo matéria UNIVESP 2022

Prévia do material em texto

Resumo da matéria de Pensamento Computacional 
com mapas mentais 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
NÃO, NOT 
E, AND 
OU, OR 
NÃO OU, NOT OR 
OU EXCLUSIVO, XOR 
NÃO E, NOT AND 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
São 8 linhas porque nesse caso são três valores de entrada (A, B e C), portanto, basta fazer a 
base 2 (dois porque são 0 e 1) elevada a quantidade de entradas. Nesse caso são 2³ = 8; 
Na primeira coluna da tabela (A), metade das linhas serão 0 e metade serão 1; 
Na segunda coluna (B), metade da metade serão 0 e metade da metade serão 1, sempre 
intercalando até o final; 
Na terceira coluna (C), intercale: zero, um, zero, um, zero, um até o final; 
Coluna B+C: são entradas de uma porta OU, portando, utilize a tabela verdade da porta OU para 
comparar a combinação de 0 e 1 das colunas B e C; 
Coluna A(B+C): É a saída de uma porta E, portanto, utilize a tabela verdade da porta E para 
comparar a combinação de 0 e 1 das colunas A e B+C; 
 
. 
8
 li
n
h
as
 
+ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
OU EXCLUSIVO, XOR 
E, AND 
⊕ 
. 
1+1 = 10 em binário, por isso vai-um 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
BUSCA SEQUENCIAL 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
14 21 5 45 12 3 86 98 46 53 24 2 1 15 90 47 
 
 
 
Se o item procurado for o 86, o programa começará a pesquisa no início da lista até encontrar 
o item localizado no índice 7. Se o item procurado fosse o 23, ele percorreria a lista até o 
último item e encerraria a busca, pois, não o teria encontrado. 
CUSTO COMPUTACIONAL O(n): Onde custo computacional é o tempo que se leva no pior caso. 
Função linear. 
O = custo 
n = quantidade de elementos da lista 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ÍNDICE 
LISTA 
Chave = item procurado 
FLUXOGRAMA PERCORRER UMA LISTA 
FLUXOGRAMA BUSCA SEQUENCIAL 
Início 
 
 
BUSCA BINÁRIA 
 
Perguntas a se fazer: A chave é o meio? A chave é < ou > que o meio? 
 
Meio = n + 1 / 2= 
 9 + 1 / 2 = 
 10 / 2 = 5, sendo assim, o meio será o índice 5 
1 2 3 4 5 6 7 8 9 
0 4 7 10 14 23 45 47 53 
 
 
 
 
Se a chave for 47 
Sabendo que o meio é 14, e que esta é uma lista ordenada, logicamente o número 47 estará 
na segunda metade da lista, pois ele é > que o meio. Portanto, incluindo o meio, a primeira 
metade da lista é excluída 
1 2 3 4 5 6 7 8 9 
0 4 7 10 14 23 45 47 53 
 
 
 
Então, se inicia uma nova pesquisa na segunda metade. Sendo assim, encontraremos um novo 
meio e repetiremos as perguntas acima até encontrar a chave e se encerrar a busca. 
Meio = n + 1 / 2= 
 4 + 1 / 2 = 
 5 / 2 = 2,5 (pode-se arredondar tanto para mais quanto para menos) nesse caso, 
vamos arredondar para 3, que será o índice 8. 
1 2 3 4 5 6 7 8 9 
0 4 7 10 14 23 45 47 53 
 
 
 
Nesse exemplo a busca se encerra, pois a chave foi encontrada, ela é igual ao meio! 
ÍNDICE 
LISTA 
Direito (dir) Esquerdo (esq) 
Meio 
Chave = item procurado 
Direito (dir) Esquerdo (esq) 
Meio 
ÍNDICE 
LISTA 
ÍNDICE 
LISTA 
Direito (dir) Esquerdo (esq) 
Meio 
 
 
CUSTO COMPUTACIONAL O(log n): Onde custo computacional é o tempo que se leva no pior 
caso. Função logarítmica. 
 
 
 
 
 
 
 
 
 
 
 
 
Sobre os fluxogramas 
Existem símbolos normatizados para se elaborar os fluxogramas: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
FLUXOGRAMA BUSCA BINÁRIA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
No Selection Sort, a ordenação se faz com uma varredura afim de se encontrar o menor item. 
O índice se encarrega de fazer isso. Ele percorre a lista inteira, sempre perguntando se o item é 
< que o menor. Se caso for, os itens trocam de lugar. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Ao identificar o menor item da lista, que nesse caso é o 1, acontece uma troca, onde o menor 
item assume a posição de menor. 
 
1 2 3 4 5 6 7 8 9 
5 2 8 56 1 12 41 36 66 
1 2 3 4 5 6 7 8 9 
5 2 8 56 1 12 41 36 66 
Início 
menor 
índice 
Início 
índice 
menor 
 
 
 
 
 
1 2 3 4 5 6 7 8 9 
1 2 8 56 5 12 41 36 66 
 
 
 
Então, menor avança para a segunda posição da lista e o índice passa a varrer procurando o 
menor item a diante. 
 
 
1 2 3 4 5 6 7 8 9 
1 2 8 56 5 12 41 36 66 
 
 
Como não há um item < que o menor, que nesse caso é o 2, e também não se chegou ao final 
da lista, se avança uma posição. 
 
 
1 2 3 4 5 6 7 8 9 
1 2 8 56 5 12 41 36 66 
 
 
 
Segue-se então assim, sucessivamente, até índice chegar ao final da lista, que concluída, estará 
ordenada. 
CUSTO COMPUTACIONAL O(n²): Onde custo computacional é o tempo que se leva no pior 
caso. Função quadrática. 
 
 
 
 
Início 
menor 
menor 
menor 
índice 
índice 
índice 
Início 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
FLUXOGRAMA SELECTION SORT 
 
 
Para iniciar a ordenação, é necessário começar a partir do segundo item, pois ele irá 
comparar se é o menor item entre o primeiro e o terceiro item da lista. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CUSTO COMPUTACIONAL O(n²): Onde custo computacional é o tempo que se leva no pior 
caso. Função quadrática. 
 
 
 
 
 
1 2 3 4 5 
23 1 10 52 3 
1 2 3 4 5 
1 23 10 52 3 
 
1 2 3 4 5 
1 10 23 52 3 
1 2 3 4 5 
1 10 23 52 3 
1 2 3 4 5 
1 3 10 23 52 
Início 
1 é menor que 23? Sim, então se 
insere na posição do 23 
10 é menor do que 1? Não. É menor que 23? 
Sim, então se insere na posição do 23 
52 é menor 23? Não. É menor do que 10? Não. É 
menor do que 1? Não. Então permanece. 
3 é menor que 52? Sim, então se insere na posição do 52. 
É menor do que 23? Sim, então se insere na posição do 23. 
É menor do que 10? Sim, então se insere na posição do 10. 
É menor do que 1? Não. Então permanece. 
Fim da lista. Lista ordenada 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
FLUXOGRAMA INSERTION SORT 
 
 
Começaremos dividindo a lista ao meio. Depois, dividiremos ao meio as metades até os itens 
ficarem isolados. Após isso, basta ir juntando os itens de forma ordenada. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5 2 8 56 1 12 41 36 66 
 
 
1 2 5 8 12 36 41 56 66 
5 2 8 56 
2 5 8 56 1 12 36 41 66 
2 5 8 56 1 12 36 41 66 
1 12 41 36 66 
41 36 66 D
IV
ID
IR
 
C
O
N
Q
U
IS
TA
R