Algoritmos e Programação

de Computadores
Revisão e Exercícios para Prova 2

Inc. material do prof. Ricardo Caceffo (orig. para aula de revisão interativa com uso de clickers, A28)
Instituto de Computação (IC/Unicamp)
Resumo ...
 Resumo de Tópicos
Assuntos tratados Descrição
Algumas estruturas de dados Definição e uso de Tuplas e Dicionários.
básicas em Python Operações e métodos em {key:value}

Funções > def func(a,b,c): Definição, Uso e chamada (invocação) de

funções, passagem de parâmetros, return

Funções > def main, def f1, def f2 Uso de variáveis globais e locais

Escopo e visibilidade de variáveis Uso e visibilidades de listas em funções

Matrizes e Vetores Matrizes e vetores multi-dimensionais

Multidimensionais Declaração e uso de matrizes, vetores.
Uso de package NumPy e o tipo array
 Resumo de Tópicos
Tópicos Descrição
Algoritmos de Ordenação: selection Uso de função def selectionSort(vetor):
i in vetor > indiceMenor(vetor,i):
for

Sort, bubbleSort e insertionSort Uso de função def bubbleSort(vetor):

Uso de função de insertionSort(vetor):

Algoritmos de busca: busca Uso de função def buscaSequencial(lista,key):

Uso de função de buscaBinaria(lista,key):
sequencial e busca binária Exercicios …. Inc. múltiplos itens

***Arquivos (texto) (Não cobrado na Uso e manipulação de arquivos de tipo texto

(leitura e escrita); uso de parâmetros, [Link]
prova)
 Resumo de Tópicos
Tópicos Descrição
***Arquivos (binários), [Link]/ Definição, e manipulação (leitura, escrita)
load (parte I). de arquivos binários – uso de util. pickle

Funções Recursivas (parte II.) Definição e Uso de ~funções recursivas;

Exercícios (soma de elementos, fatorial)

Algoritmo de ordenação quickSort Descrição do algoritmo, definição de

estratégia divide-conquer e exercícios

Algoritmo de ordenação mergeSort Descrição do algoritmo, definição de

estratégia divide-conquer e exercícios
Exemplo da prova
Exemplo (Matrizes)
● Seja P a propriedade que indica que uma matriz é quadrada e que os elementos em
sua diagonal principal são iguais a 1 e os outros são iguais a 0. Maria gostaria de
escrever uma função em Python para verificar a propriedade P em uma matriz
representada por uma lista de listas contendo números inteiros.
● Inicialmente, Maria
2. (2.5 pontos) Seja precisaque
P a propriedade identificar a propriedade
indica que uma matriz é quadradaem algumas
e que matrizes.
os elementos Indique para
em sua diagonal
principal são iguais a 1 e os outros são iguais a 0. Maria gostaria de escrever uma função em Python para
cada estrutura
verficar dePdados
a propriedade apresentada
em uma matriz representada abaixo se de
por uma lista esta
listasrepresenta uma
contendo números matriz que
inteiros.
Inicialmente, Maria precisa identificar a propriedade em algumas matrizes. Indique para cada estrutura de
respeita a propriedade P ou não. Em caso de violação da propriedade, escreva uma
dados apresentada abaixo se esta representa uma matriz que respeita a propriedade P ou não. Em caso de violação
justificativa.
da propriedade, escreva uma justificativa.

[[2, 0, 0], [[2, 0, 0, 0], [[1, 0, 0], [[1, 0, 0],

[0, 1, 0], [0, 1, 0, 0], [0, 1, 0], [0, 1, 0, 0],
[0, 0, 1]] [0, 0, 1, 0]] [0, 0, 1]] [0, 0, 1]]
N~
ao garante P. N~
ao garante P. Garante P N~
ao garante P.
m[0][0] != 1 N~
ao é quadrada. N~
ao é quadrada.
Exemplo (Matrizes)
2. (2.5 pontos) Seja P a propriedade que indica que uma matriz é quadrada e que os elementos em sua diagonal
principal são iguais a 1 e os outros são iguais a 0. Maria gostaria de escrever uma função em Python para
verficar a propriedade P em uma matriz representada por uma lista de listas contendo números inteiros.
Inicialmente, Maria precisa identificar a propriedade em algumas matrizes. Indique para cada estrutura de
dados apresentada abaixo se esta representa uma matriz que respeita a propriedade P ou não. Em caso de violação
da propriedade, escreva uma justificativa.

[[2, 0, 0], [[2, 0, 0, 0], [[1, 0, 0], [[1, 0, 0],

[0, 1, 0], [0, 1, 0, 0], [0, 1, 0], [0, 1, 0, 0],
[0, 0, 1]] [0, 0, 1, 0]] [0, 0, 1]] [0, 0, 1]]
N~
ao garante P. N~
ao garante P. Garante P N~
ao garante P.
m[0][0] != 1 N~
ao é quadrada. N~
ao é quadrada.

Em seguida, escreva a função verifica P(m) que recebe uma lista de listas de inteiros como parâmetro e retorna
True se a matriz atende a propriedade P ou False caso contrário.

def verifica P(m) :

n = len(m)
for i in range(n) :
if len(m[i]) != n :
return False
for j in range(n) :
Exemplo (Matrizes)

● Em seguida, escreva a função verifica P(m) que recebe uma lista de listas de
inteiros como parâmetro e retorna True se a matriz atende a propriedade P
ou False caso contrário.
 [0, 1, 0], [0, 1, 0, 0], [0, 1, 0],
[0, 0, 1]] [0, 0, 1, 0]] [0, 0, 1]]
N~
ao garante P. N~
ao garante P. Garante P
m[0][0] != 1 N~
ao é quadrada.
Exemplo (Matrizes)

● Em seguida, escreva a função verifica P(m) que recebe uma lista de listas de
Em seguida, escreva a função verifica P(m) que recebe uma lista de lista
inteiros como parâmetro eTrue
retorna Trueatende
se a matriz se a amatriz atende
propriedade P ouaFalse
propriedade P
caso contrário.
ou False caso contrário.
def verifica P(m) :
n = len(m)
for i in range(n) :
if len(m[i]) != n :
return False
for j in range(n) :
if i == j and m[i][j] != 1 :
return False
if i != j and m[i][j] != 0 :
return False
return True
Exemplo (Funções)

● Rafaela começou a estudar o algoritmo de ordenação QuickSort. Antes de

analisar as chamadas recursivas, ela vai explorar o algoritmo que posiciona
corretamente o pivô a cada passo.
● O elemento escolhido para ser o pivô pode ser, por exemplo, o primeiro
elemento do vetor. Após a execução da função particiona, à esquerda do
3. (2 pontos) Rafaela começou a estudar o algoritmo de ordenação QuickSort. Antes de analisar as chamadas
pivô ficarão
recursivas, osexplorar
ela vai elementos com
o algoritmo que valores
posiciona menores
corretamente do passo.
o pivô a cada que o valor do pivô e à
O elemento escolhido para ser o pivô pode ser, por exemplo, o primeiro elemento do vetor. Após a execução
direita doparticiona,
da função pivô ficarão osdoelementos
à esquerda com valores
pivô ficarão os elementos maiores.
com valores menores do que Veja o pivô
o valor do exemplo
e à a
direita do pivô ficarão os elementos com valores maiores. Veja o exemplo a seguir:
seguir:
12 14 6 7 18 2 21

7 2 6 12 18 14 21

Observe o código abaixo, em que a partição pode atuar na lista inteira ou em uma sublista, de acordo com os
valores dos ı́ndices e e d passados como parâmetro para a função. Para acompanhar os passos, Rafaela introduziu
 direita do pivô ficarão os elementos com valores maiores. Veja o exemplo a seguir:

12 14 6 7 18 2 21

Exemplo (Funções) 7 2 6 12 18 14 21

Observe o código abaixo, em que a partição pode atuar na lista inteira ou em uma su
valores dos ı́ndices e e d passados como parâmetro para a função. Para acompanhar os p
algumas chamadas ao comando print em pontos estratégicos, logo após as trocas dos el

● Observe o código abaixo, em que a def particiona(lista, e, d) :

valor pivo = lista[e]
partição pode atuar na lista inteira ou pos pivo = e
e += 1
em uma sublista, de acordo com os print("e =", e, "d =", d, lista)
while e < d :
valores dos índices e e d passados while e <= d and valor pivo >= lista[e] :

como parâmetro para a função. Para e += 1

while e <= d and valor pivo <= lista[d] :
acompanhar os passos, Rafaela d -= 1
if e > d :
introduziu algumas chamadas ao break
lista[e], lista[d] = lista[d], lista[e]
comando print em pontos print("e =", e, "d =", d, lista)
lista[pos pivo], lista[d] = lista[d], lista[pos pivo]
estratégicos, logo após as trocas dos print("e =", e, "d =", d, lista)
return d
elementos.
Para a lista e as chamadas abaixo indique o resultado dos comandos print segui
indique o valor das variáveis ponto1 e ponto2.
 e += 1
print("e =", e, "d =", d, lista)
while e < d :
while e <= d and valor pivo >= lista[e] :

Exemplo (Funções) e += 1
while e <= d and valor pivo <= lista[d] :
d -= 1
if e > d :
break
lista[e], lista[d] = lista[d], lista[e]
● Para a lista e as chamadas abaixo indique o resultado dos comandos print
print("e =", e, "d =", d, lista)
seguindo o modelo. Ao final, indique o valor das variáveis ponto1 e ponto2.
lista[pos pivo], lista[d] = lista[d], lista[pos pivo]
print("e =", e, "d =", d, lista)
● Execução 0 return d

Para a lista e as chamadas abaixo indique o resultado dos comandos print seguindo o modelo. Ao final,
indique o valor das variáveis ponto1 e ponto2.

lista = [22, 10, 6, 30, 19, 2, 27]

ponto1 = particiona(lista, 0, len(lista) - 1)
ponto2 = particiona(lista, 0, ponto1 - 1)

e = 1 d = 6 [ 22 , 10 , 6 , 30 , 19 , 2 , 27 ]

e = 3 d = 5 [ 22 , 10 , 6, 2 , 19 , 30 , 27 ]

e = 5 d = 4 [ 19 , 10 , 6, 2 , 22 , 30 , 27 ]
, ela vai explorar o algoritmo que posiciona corretamente o pivô a cada [Link]("e =", e, "d =", d, lista)
mento escolhido para ser o pivô pode ser, por exemplo, o primeiro elemento do vetor.
lista[pos Após alista[d]
pivo], execução = lista[d], lista[pos pivo]
particiona, à esquerda do pivô ficarão os elementos com valores menores
print("e =", e, "d pivô
do que o valor do =", ed,à lista)
pivô ficarão os elementos com valores maiores. Veja o exemplo a seguir:
return d

Exemplo (Funções) 12 14 6 7 18 2 21
Para a lista e as chamadas abaixo indique o resultado dos comandos print seguindo o mode
indique o valor das variáveis ponto1 e ponto2.
7 2 6 12 18 14 21

ve o código abaixo, em que a partição pode atuar na lista inteira oulista

em uma= sublista,
[22, 10,de6, 30, com
acordo 19, os
2, 27]
ponto1os=passos,
s ı́ndices e e d passados como parâmetro para a função. Para acompanhar particiona(lista, 0, len(lista) - 1)
Rafaela introduziu
● Execução 1 ponto2 = particiona(lista,
hamadas ao comando print em pontos estratégicos, logo após as trocas dos elementos. 0, ponto1 - 1)

def particiona(lista, e, d) : e = 1 d = 6 [ 22 , 10 , 6 , 30 , 19 , 2 , 27 ]
valor pivo = lista[e]
pos pivo = e
e += 1 e = 3 d = 5 [ 22 , 10 , 6, 2 , 19 , 30 , 27 ]
print("e =", e, "d =", d, lista)
while e < d : e = 5 d = 4 [ 19 , 10 , 6, 2 , 22 , 30 , 27 ]
while e <= d and valor pivo >= lista[e] :
e += 1
e = 1 d = 3 [ 19 , 10 , 6, 2 , 22 , 30 , 27 ]
while e <= d and valor pivo <= lista[d] :
d -= 1
if e > d : e = 4 d = 3 [ 2 , 10 , 6 , 19 , 22 , 30 , 27 ]
break
lista[e], lista[d] = lista[d], lista[e] 4 3
ponto1 = ponto2 =
print("e =", e, "d =", d, lista)
lista[pos pivo], lista[d] = lista[d], lista[pos pivo]
print("e =", e, "d =", d, lista)
return d
, ela vai explorar o algoritmo que posiciona corretamente o pivô a cada passo.
print("e =", e, "d =", d, lista)
mento escolhido para ser o pivô pode ser, por exemplo, o primeiro elemento do vetor. Após a execução
lista[pos pivo], lista[d] = lista[d], lista[pos pivo]
particiona, à esquerda do pivô ficarão os elementos com valores menores do que o valor do pivô e à
print("e =", e, "d =", d, lista)
pivô ficarão os elementos com valores maiores. Veja o exemplo a seguir:
return d

Exemplo (Funções) 12 14 6 7 18 2 21
Para a lista e as chamadas abaixo indique o resultado dos comandos print seguindo o mod
indique o valor das variáveis ponto1 e ponto2.
7 2 6 12 18 14 21
lista
ve o código abaixo, em que a partição pode atuar na lista inteira ou em uma=sublista,
[22, 10, 6, 30,com
de acordo 19,os2, 27]
ponto1
s ı́ndices e e d passados como parâmetro para a função. Para acompanhar os =passos,
particiona(lista, 0, len(lista) - 1)
Rafaela introduziu
● Execução 2 ponto2 = particiona(lista,
hamadas ao comando print em pontos estratégicos, logo após as trocas dos elementos. 0, ponto1 - 1)

def particiona(lista, e, d) : 1 d = 6 [ 22 , 10 , 6 , 30 , 19 , 2 , 27 ]
e =
valor pivo = lista[e]
pos pivo = e
e += 1 e = 3 d = 5 [ 22 , 10 , 6, 2 , 19 , 30 , 27 ]
print("e =", e, "d =", d, lista)
while e < d : e = 5 d = 4 [ 19 , 10 , 6, 2 , 22 , 30 , 27 ]
while e <= d and valor pivo >= lista[e] :
e += 1
while e <= d and valor pivo <= lista[d] : e = 1 d = 3 [ 19 , 10 , 6, 2 , 22 , 30 , 27 ]
d -= 1
if e > d : e = 4 d = 3 [ 2 , 10 , 6 , 19 , 22 , 30 , 27 ]
break
lista[e], lista[d] = lista[d], lista[e] 4 3
print("e =", e, "d =", d, lista) ponto1 = ponto2 =
lista[pos pivo], lista[d] = lista[d], lista[pos pivo]
print("e =", e, "d =", d, lista)
return d
, ela vai explorar o algoritmo que posiciona corretamente o pivô a cada passo. print("e =", e, "d =", d, lista)
mento escolhido para ser o pivô pode ser, por exemplo, o primeiro elemento dolista[posApós
vetor. a execução
pivo], lista[d] = lista[d], lista[pos pivo]
particiona, à esquerda do pivô ficarão os elementos com valores menores doprint("e =", e, pivô
que o valor do e à d, lista)
"d =",
pivô ficarão os elementos com valores maiores. Veja o exemplo a seguir: return d

Exemplo (Funções) 12 14 6 7 18 2 Para21 a lista e as chamadas abaixo indique o resultado dos comandos print seguindo o m
indique o valor das variáveis ponto1 e ponto2.
7 2 6 12 18 14 21
lista = [22, 10, 6, 30, 19, 2, 27]
ve o código abaixo, em que a partição pode atuar na lista inteira ou em uma sublista, de acordo com os
ponto1 = particiona(lista, 0, len(lista) - 1)
s ı́ndices e e d passados como parâmetro para a função. Para acompanhar os passos, Rafaela introduziu
● Execução 3 ponto2 = particiona(lista, 0, ponto1 - 1)
hamadas ao comando print em pontos estratégicos, logo após as trocas dos elementos.

def particiona(lista, e, d) : e = 1 d = 6 [ 22 , 10 , 6 , 30 , 19 , 2 , 27 ]
valor pivo = lista[e]
pos pivo = e
e = 3 d = 5 [ 22 , 10 , 6, 2 , 19 , 30 , 27 ]
e += 1
print("e =", e, "d =", d, lista)
while e < d : e = 5 d = 4 [ 19 , 10 , 6, 2 , 22 , 30 , 27 ]
while e <= d and valor pivo >= lista[e] :
e += 1 1 d = 3 [ 19 , 10 , 6, 2 , 22 , 30 , 27 ]
while e <= d and valor pivo <= lista[d] : e =
d -= 1
if e > d : e = 4 d = 3 [ 2 , 10 , 6 , 19 , 22 , 30 , 27 ]
break
lista[e], lista[d] = lista[d], lista[e] 4 3
ponto1 = ponto2 =
print("e =", e, "d =", d, lista)
lista[pos pivo], lista[d] = lista[d], lista[pos pivo]
print("e =", e, "d =", d, lista)
return d
, ela vai explorar o algoritmo que posiciona corretamente o pivô a cada passo.
print("e =", e, "d =", d, lista)
mento escolhido para ser o pivô pode ser, por exemplo, o primeiro elemento do vetor.
lista[pos Após lista[d]
pivo], a execução= lista[d], lista[pos pivo]
particiona, à esquerda do pivô ficarão os elementos com valores menores do que o valor do pivô e à
print("e =", e, "d =", d, lista)
pivô ficarão os elementos com valores maiores. Veja o exemplo a seguir:
return d

Exemplo (Funções) 12 14 6 7 18 2 21
Para a lista e as chamadas abaixo indique o resultado dos comandos print seguindo o modelo
indique o valor das variáveis ponto1 e ponto2.
7 2 6 12 18 14 21

ve o código abaixo, em que a partição pode atuar na lista inteira oulista

em uma= [22, 10,de6,acordo
sublista, 30, 19,
com 2,
os 27]
ponto1 os
s ı́ndices e e d passados como parâmetro para a função. Para acompanhar = passos,
particiona(lista, 0, len(lista) - 1)
Rafaela introduziu
● Execução 4 ponto2 = particiona(lista,
hamadas ao comando print em pontos estratégicos, logo após as trocas dos elementos. 0, ponto1 - 1)

def particiona(lista, e, d) : 1 d = 6 [ 22 , 10 , 6 , 30 , 19 , 2 , 27 ]
e =
valor pivo = lista[e]
pos pivo = e
e += 1 e = 3 d = 5 [ 22 , 10 , 6, 2 , 19 , 30 , 27 ]
print("e =", e, "d =", d, lista)
while e < d : e = 5 d = 4 [ 19 , 10 , 6, 2 , 22 , 30 , 27 ]
while e <= d and valor pivo >= lista[e] :
e += 1
e = 1 d = 3 [ 19 , 10 , 6, 2 , 22 , 30 , 27 ]
while e <= d and valor pivo <= lista[d] :
d -= 1
if e > d : e = 4 d = 3 [ 2 , 10 , 6 , 19 , 22 , 30 , 27 ]
break
lista[e], lista[d] = lista[d], lista[e] 4 3
ponto1 = ponto2 =
print("e =", e, "d =", d, lista)
lista[pos pivo], lista[d] = lista[d], lista[pos pivo]
print("e =", e, "d =", d, lista)
return d
Exemplo (Recursividade)

● João agora está estudando recursão e elaborou nova série de testes. Como
na questão 1, você deve escrever a saída do programa ou indicar “Nada será
escrito”. Caso algum erro seja encontrado, indique o motivo e marque na
coluna da esquerda a linha em que ele ocorre. Você também deve indicar
claramente se o programa tiver entrado em loop.
 4. (2.5 pontos) João agora está estudando recursão e elaborou nova série de testes. Como na questão 1, você deve
escrever a saı́da do programa ou indicar “Nada será escrito”. Caso algum erro seja encontrado, indique o motivo

Exemplo (Recursividade)
e marque na coluna da esquerda a linha em que ele ocorre. Você também deve indicar claramente se o programa
tiver entrado em loop.

Programa O que será escrito

def rec(n):
print("n =", n)
n = 9
if n == 1 or n == 0: n = 6
return n n = 3
rec(n-3) n = 0
rec(9)

def rec(n):
if (n >= 2):
n = 1 r = 5
return n n = 0 r = 7
r = rec(n+1) + rec(n+2)
print ("n =", n, "r =", r)
return r
rec(0)

def rec(n):
if n < 2 :
Nada será escrito
n += 1 Loop infinito (comentário sobre estouro
return n + rec (n+1) de pilha n~ao é obrigatório)
rec(0)
 return n n = 0 r = 7
r = rec(n+1) + rec(n+2)
print ("n =", n, "r =", r)
return r
rec(0)

Exemplo (Recursividade) def rec(n):

if n < 2 :
Nada será escrito
n += 1 Loop infinito (comentário sobre estouro
return n + rec (n+1) de pilha n~ao é obrigatório)
rec(0)
● João também fez testes para comparar versões recursivas e iterativas (não
recursivas) dos mesmos algoritmos. Seguindo esta ideia, complete a tabela
João também fez testes para comparar versões recursivas e iterativas (não recursivas) dos mesmos algoritmos.
abaixo, escrevendo a versão iterativa do código à esquerda.
Seguindo esta ideia, complete a tabela abaixo, escrevendo a versão iterativa do código à esquerda.

Versão recursiva Versão iterativa

def rec(n):
def iterativa(n) :
print(n)
aux = 0
if n == 0:
while (n >= 0) :
return 0
print(n)
else:
aux += n
return n + rec(n-1)
n = n-1
return aux
ou
def iterativa(n) :
aux = 0
for i in range(n,-1,-1) :
print(i)
aux += i
return aux
Exercícios
II revisão ...
 Exercício (A18: cópia de listas)
# Ref. A28, ex3_clickers_A16-[Link], cópia de listas via atribuição lista_a = lista_b
# Em Python, uma cópia de lista via atribuição simples apenas gera uma referência à mesma estrutura
em memória. Assim, qualquer modificação à lista_a, gera a mesma modificação na lista_b
# para gerar cópias independentes, use #copia de listas via atribuição simples
1. Slicing> b = a[:] def adicionaElem(lista,elem):
[Link](elem); return lista
2. Copia via list # main
a = [0,1,2] lista_a = [20,30]
lista_b = lista_a
b = list(a) adicionaElem(lista_b, 40)
3. Via método copy lista_b[0]=-1;lista_b[1]=-2;lista_b[0]=-3
print(“la: ”,lista_a); print(“lb: ”,lista_b)
a = [0, 1, 2]
>> la: [-1, -2, -3]
b = [Link]() >> lb: [-1, -2, -3]
Cópia de listas em Python
# copia de listas via
# 1. atribuição simples
lista_a = [0,1,2]
lista_b = lista_a
# as 2 listas referenciam a
# mesma posição de memória

# 2. cópia via método copy

# são geradas cópias
# independentes, localizadas
# em posições de memória
# diferentes (shallow copy)

lista_c = lista_a.copy()
 Exercício (A15: Tuplas, Dicionários)
# definindo tuplas; tupla1 = ('setembro', 26, 9, 2018); tupla2 = (1, 2, 3, 4, 5, 6, 7)
print ( ...); print(len(tupla1)); print(tupla1[1:3]), ... ;
1. dados da tupla 1.
#definindo lista de tuplas
length of 'tupla1' is : 4 # ex.
lista_de_tuplas=[ ];
tupla1 is : ('setembro', 26, 9, 2018)
lista_de_tuplas.append((18,20))
lista_de_tuplas.append((novembro,25))
print(lista_de_tuplas)
2. dados da tupla 2.
length of 'tupla2' is : 7 > [(18,20),(‘setembro’,25)]
tupla2 is : (1, 2, 3, 4, 5, 6, 7)
 Exercício (A15: Tuplas, Dicionários)
# 1. definindo dicionário; e percorrendo as chaves na sequencia
RA = {“Liz”: 229874, “Hugo”:215793,”Sofia”:199745}
for i in RA:
print (i) # verificando pares (KEY, VALUE), get
# uso : get(key)
1. Sofia, Liz, Hugo
# [Link] os pares do dicion.
# 2. Verificando se há chaves no dic. [Link](“Hugo”) > 215793
A1 = “Sofia” in RA
for i, j in [Link]():
A2 = “Aline in RA print(i,j,sep=‘ ‘)
print(A1, A2) > True, False
# saida do loop acima
print(RA[“Hugo”]) > 215739 Ø Sofia 199745
Ø Liz 229874
Ø Hugo 215793
 Exemplos (A16: Funções)
Há duas formas ou estruturas para uso e definição de funções em Python
#1. funçoes declaradas antes do seu uso no programa principal
def funcao_nome(parametros ou argumentos):
corpo/comandos da função
return <valor/variavel de retorno)
# programa principal (aqui e onde a funcao_nome eh invocada)
funcao_nome(x, y, …)
#2. funções declaradas posteriormente, a função main é declarada no inicio
def main()
def funcao_f1(parametros da funçao f1)
def funcao_f2 (parametros da funcao f2)
# programa principal (aqui eh invocada a funcao progrma principal > main)
main()
 Exemplos (A16: funções)
# funcao 0. def. programa principal
Revisar exercício sld. 30 e 31, present. Aula 16
def main():
def leNota(num): n = int(input(“digitar notas”))
notas = [] notas = leNota(n)
…. media = calculaMedia(notas)
return ....
def calculaMedia(notas): # funcao 1. def. leitura de notas
soma = 0 def leNota(num):
…. notas = [ ]
return ....
# funcao 2. def. calcula media
# comandos do programa principal def calculaMedia(notas):
n=int(input(“digitar numero de notas”)) soma = 0
....
notas = leNota(n)
# programa principal (execucao)
Media = calculaMedia(notas) main()
 Exemplos (A17: funções, var. globais e locais)
# funcao 0. def. programa principal
# definicao e uso de variaveis globais; escopo: todo o programa
def main():
def leNota(num): # aqui z esta restrita a funcao main
x=0 # variavel x local a func. leNota # x eh uma variavel global
notas = [x] x=5; z = int(input(“digitar notas”))
notas = leNota(z)
…. media = calculaMedia(notas)
def calculaM(notas): ....
y=1 # variavel y local a func. calculaM # funcao 1. def. leitura de notas
def leNota(num):
soma = y global x
…. notas = [ ]
x=0 # x eh global ...
# programa principal, var. global x e z # funcao 2. def. calcula media
x=4;z=2 # x e z: globais, criadas fora funcões def calculaMedia(notas):
soma = 0
notas = leNota(z) ....
Media = calculaM(notas) # programa principal (execucao)
main() > imprime x = 0 !!
print(x) # sera impresso valor 4 (global)
 A18: Matrizes e Vetores multi-dimensionais
● Inicialização de uma matriz de dimensões l x c vazia utilizando listas.
● Exemplo de uma matriz 3 x 4 (com elementos inicialmente vazios):

mat = [[] for i in range(3)]

#dentro da lista externa criam-se 3 listas vazias []
mat
[[], [], []]

● Assim, em “mat” , cada lista interna representa uma linha da matriz i.e.,
Ø [[a01,a02,a03], [a11, a12, a13], [a21,a22,a23]]
 A18: Matriz e Vetores multi-dimensionais
● Ex. Criar matriz 3 x 4 onde cada posição (i , j) contém o valor de i * j.

0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 4 6
 A18: Matriz e Vetores multi-dimensionais
● Criar matriz 3 x 4 onde cada posição (i , j) contém o valor de i * j.

mat = []
for i in range(3): # para cada linha de 0 ate 2
l = [] # linha começa vazia
for j in range(4): # para cada coluna de 0 ate 3
[Link](i*j) # preenche colunas da linha I
[Link](l) # adiciona linha na matriz
print(mat)

[[0, 0, 0, 0], [0, 1, 2, 3], [0, 2, 4, 6]]

 Exemplo de Declaração de Matriz
● Obtendo o mesmo resultado utilizando compreensão de listas:

mat = [[i*j for j in range(4)] for i in range(3)]

print(mat)

[[0, 0, 0, 0], [0, 1, 2, 3], [0, 2, 4, 6]]

 Exercício (A18: Matrizes e Vetores multi-D)
Uso de bibliotecas NumPy (Python)
# Ex. Array 3x3 Uso de bibliotecas NumPy (Python
import numpy as np Se Mi é uma matriz n-dimensional)
b = [Link]([[1,2,3],[4,5,6]])
[Link]. K0*M0, M1+M2,...
print([Link])
print([Link]) print(b) # uso de numpy
import numpy as np
# re-arrange/reshape a = [Link]([[1,2],[4,5]])
a= [Link](10) print([Link])
print(a) b = [Link]([[7,8],[2,0]])
A – [Link]([Link](2,5 c = [Link](a,b)
print(a) c= a*b [[11 8]
(matricial) [38 32]]
Exemplos RegEx
ref. apresentação orig. Aula 28
Exemplos Algoritmos de Ordenação
BubbleSort
InsertionSort
ref. apresentação orig. em Aula 28
 36

Aula 20

Ordenação:
Ø Bubble Sort
 37

lista = [3,2,9,7,5,1,8,4]

[A20-Q7] Qual será o conteúdo da lista após uma

iteração do algoritmo Bubble Sort?
Índice i percorre todas as posições de 0 a tam-2,
trocando lista[i+1] com lista[i] se
lista[i] > lista [i+1]
 38
lista = [3,2,9,7,5,1,8,4]

[A20-Q7] Qual será o conteúdo da lista após uma

iteração do algoritmo Bubble Sort?
Índice i percorre todas as posições de 0 a tam-2,
trocando lista[i+1] com lista[i] se
lista[i] > lista [i+1]
A C
E
lista = [3,2,9,7,5,1,8,4] lista = [1,2,3,4,5,7,8,9]
lista =
B D [1,2,3,7,5,8,4,9]
lista = [2,3,7,5,1,8,4,9] lista = [2,3,5,7,1,8,4,9]
 39
lista = [3,2,9,7,5,1,8,4]

[A20-Q7] Qual será o conteúdo da lista após uma

iteração do algorítmo Bubble Sort?
Índice i percorre todas as posições de 0 a tam-2,
trocando lista[i+1] com lista[i] se
lista[i] > lista [i+1]
A C
E
lista = [3,2,9,7,5,1,8,4] lista = [1,2,3,4,5,7,8,9]
lista =
B D [1,2,3,7,5,8,4,9]
lista = [2,3,7,5,1,8,4,9] lista = [2,3,5,7,1,8,4,9]
 lista = 40

[25,20,15,10,3,2,30,35,39,40,55,9,7,60,80,5,1,8,4]
[A20-Q9] Qual será o conteúdo das 4 últimas
posições da lista após 4 iterações do Bubble Sort?
 lista = 41

[25,20,15,10,3,2,30,35,39,40,55,9,7,60,80,5,1,8,4]
[A20-Q9] Qual será o conteúdo das 4 últimas posições da lista após 4
iterações do Bubble Sort?

A C

lista = […,5,1,8,80] lista = […,40,55,60,80]

B D

lista = […, 50,55,60,80] lista = […,39,40,55,60]

D

lista = […,55,40,60,80]
 lista = 42

[25,20,15,10,3,2,30,35,39,40,55,9,7,60,80,5,1,8,4]
[A20-Q9] Qual será o conteúdo das 4 últimas posições da lista após 4
iterações do Bubble Sort?

A C

lista = […,5,1,8,80] lista = […,40,55,60,80]

B D

lista = […, 50,55,60,80] lista = […,39,40,55,60]

D

lista = […,55,40,60,80]
 43

Aula 21

Ordenação:
Ø Insertion Sort
[A21-Q1] Este programa implementa o Insertion Sort. Quais linhas 44
obrigatoriamente devem ser removidas para que o programa funcione como esperado?
 45

Nenhuma
linha. O B C D E

programa Linha 10 Linha 2 e

Linha 2 Linha 8
funciona
Linha 10
corretament
e assim.
 46

Nenhuma
linha. O B C D E

programa Linha 10 Linha 2 e

Linha 2 Linha 8
funciona
Linha 10
corretament
e assim.
[A21-Q4] O que será impresso pelo programa abaixo? 47

Implementação correta do
Insertion Sort.
 48

A B C D E

10 13 15 17 20
 49

A B C D E

10 13 15 17 20
Exemplos Algoritmos de Busca
Sequencial
Binária
ref. apresentação orig. em Aula 28
 51

Aula 22

Busca:
Ø Sequencial
Ø Binária
[A22-Q1] O que será impresso pelo programa abaixo? 52
 53

A B C D E

Não irá Não Pos = 0 Pos = -1 Pos = 1

compilar.
 54

A B C D E

Não irá Não Pos = 0 Pos = -1 Pos = 1

compilar.
[A22-Q9] Qual o valor da chave para que o programa seja executado conforme abaixo? 55
[A22-Q9] Qual o valor da chave para que o programa seja executado conforme abaixo? 56

A B B D E

5 6 8 10 12
[A22-Q9] Qual o valor da chave para que o programa seja executado conforme abaixo? 57

A B B D E

5 6 8 10 12
Exemplos Algoritmos de Ordenação
MergeSort
QuickSort
ref. apresentação orig. em Aula 28
 59

Aula 27

Merge Sort
[A27-Q2] Qual o resultado da fusão (ordenação por intercalação) 60

realizada com as listas abaixo?

2 5 7 11 -1 2 2 2 30
[A27-Q2] Qual o resultado da fusão (ordenação por intercalação) 61
61

realizada com as listas abaixo?

2 5 7 11 -1 2 2 2 30

A B C D E

Não é -1 2 2 2 30 -1 2 2 2 2 -1 2 2 2 5 -1 2 2 2 2 5
possível 11 30 7 11 30 7 11 30
fazer a
fusão.
[A27-Q2] Qual o resultado da fusão (ordenação por intercalação) 62
62

realizada com as listas abaixo?

2 5 7 11 -1 2 2 2 30

A B C D E

Não é -1 2 2 2 30 -1 2 2 2 2 -1 2 2 2 5 -1 2 2 2 2 5
possível 11 30 7 11 30 7 11 30
fazer a
fusão.
[A27-Q3] Considere a seguinte lista. Qual a árvore gerada 63

considerando-se apenas a fase de Divisão e Chamada Recursiva?

2 4 1 3 5 0
[A27-Q3] Considere a seguinte lista. Qual a árvore gerada 64

considerando-se apenas a fase de Divisão e Chamada Recursiva?

A B

2 4 1 3 5 0 2 4 1 3 5 0

2 4 1 3 5 0 2 4 1 3 5 0

2 4 1 3 5 0 2 4 1 3 5 0

1 2 4 0 3 5 4 1 5 0
[A27-Q3] Considere a seguinte lista. Qual a árvore gerada 65

considerando-se apenas a fase de Divisão e Chamada Recursiva?

C D

2 4 1 3 5 0 2 4 1 3 5 0

2 4 1 3 5 0 2 4 1 3 5 0

2 4 1 3 5 0 2 4 1 3 5 0

2 4 1 3 5 0 1 4 0 5

E Nenhuma das alternativas

anteriores.
 [A27-Q3] Revelação: 66

2 4 1 3 5 0

2 4 1 3 5 0

2 4 1 3 5 0

4 1 5 0
 67

Aula 28

Quick sort
[A28-Q1] Considere a seguinte lista. Qual será a lista após a 68

chamada da função particiona, e qual será o valor retornado?

8 7 1 2 4 9 3 5 6
[A28-Q1] Considere a seguinte lista. Qual será a lista após a 69

chamada da função particiona, e qual será o valor retornado?

8 7 1 2 4 9 3 5 6

A
871249356 C
12345678
Retornará 6 Retornará 5
E
912438576
Retornará 5
B
512438976 D
651243978
Retornará 5 Retornará 6
[A28-Q1] Considere a seguinte lista. Qual será a lista após a 70

chamada da função particiona, e qual será o valor retornado?

8 7 1 2 4 9 3 5 6

A
871249356 C
12345678
Retornará 6 Retornará 5
E
512438976
Retornará 6
B
512438976 651243978
Retornará 5 Retornará 6
[A28-Q2] Considere a seguinte lista. Qual será a lista após a 71

chamada da função particiona, e qual será o valor retornado?

9 0 8 1 7 2 6 3 4

A
403127689 C
041327698
Retornará 4 Retornará 4
E
041327698
Retornará 6
B
403127689 D
041327698
Retornará 5 Retornará 5
[A28-Q2] Considere a seguinte lista. Qual será a lista após a 72

chamada da função particiona, e qual será o valor retornado?

9 0 8 1 7 2 6 3 4

A
403127689 C
041327698
Retornará 4 Retornará 4
E
041327698
Retornará 6
B
403127689 D
041327698
Retornará 5 Retornará 5
[A28-Q2] Considere a seguinte lista. Qual será a lista após a 73

chamada da função particiona, e qual será o valor retornado?

9 0 8 1 7 2 6 3 4

A
403127689 C
041327698
Retornará 4 Retornará 4
E
041327698
Retornará 6
B
403127689 D
041327698
Retornará 5 Retornará 5
 Referências & Exercícios
● [Link]
● [Link]
● [Link]
● [Link]
● [Link]
● [Link]

Apresentação original com exercícios interativos (aula 28), do prof. Ricardo Caceffo em :
[Link]

Tópicos principais
Listas, Tuplas, Dicionários, RegEx: Expressões Regulares,
Algoritmos de Busca Binaria e Sequencial
Ordenação: selection Sort, BubbleSort, Insertion Sort, MergeSort, QuickSort