B.2 · Programação

Este material didático aborda o Tema B2, Programação, para o curso avaliado pela primeira vez em 2027, usando Python. As seções marcadas AHL são apenas para Nível Superior.

Pré-requisitos: pensamento computacional de B1 (decomposição, abstração, algoritmos como fluxogramas e pseudocódigo). Você deve ser capaz de executar um programa curto em Python e ler sua saída.

Por que um programa funcional falha na segunda-feira?

O programa de caixa de uma loja funcionou por um mês. Na segunda-feira, um cliente digita two em vez de 2 para a quantidade e o programa travou. Nenhuma parte do código mudou: a entrada mudou. Bons programas são escritos para cada entrada que possam encontrar, não apenasquelas que o programador testou.

Variáveis e tipos de dados

Uma variável é um armazenamento nomeado para um valor que pode mudar enquanto o programa executa. Uma constante é um valor nomeado que não deve mudar; no Python, escreve-se em letras maiúsculas por convenção, como VAT_RATE = 0.2.

Cada valor tem um tipo de dado, que determina o que ele pode armazenar e quais operações funcionam sobre ele.

• int("42") converte texto em inteiro e str(42) converte um número em texto. Essa conversão de tipo é necessária porque input() sempre retorna uma string.
• 7 / 2 é 3.5; 7 // 2 é 3 (divisão inteira); 7 % 2 é 1 (o resto, modulo).

Strings

Uma string é uma sequência de caracteres, indexada a partir de 0.

code = "ib-2027"
len(code)        # 7
code[0]          # "i"
code[3:7]        # "2027": from index 3 up to, not including, 7
code.upper()     # "IB-2027"
code.find("-")   # 2; -1 if not found
"2027" in code   # True

As strings em Python são imutáveis: code.upper() retorna uma nova string e deixa code inalterado. Juntar strings com + é concatenação.

Exceções: lidando com entrada inválida

Uma exceção é um erro levantado enquanto o programa executa, como ValueError para int("two") ou ZeroDivisionError para 5 / 0. Se não tratada, ela interrompe o programa. Um bloco try … except a captura:

while True:
    text = input("Quantity: ")
    try:
        qty = int(text)
        break
    except ValueError:
        print("Enter a whole number.")

O loop se repete até que o cast tenha sucesso, evitando travamentos no programa em two. Um bloco finally, se presente, executa-se independentemente de exceção: é usado para fechar arquivos.

Depuração e tabelas de traçagem

Existem três tipos de erro:

Uma tabela de traçagem registra o valor de cada variável após cada passo, manualmente. É o método padrão para encontrar erros lógicos e uma questão comum de exame.

total = 0
for k in range(1, 5):
    if k % 2 == 0:
        total = total + k
print(total)

Saída: 6. Note que range(1, 5) para antes de 5. Outras técnicas de depuração incluem instruções print em pontos-chave, breakpoints em um debugger que pausam o programa e mostram as variáveis, e avançar linha por linha.

Estruturas estáticas e dinâmicas

Uma estrutura de dados estática tem tamanho fixo no momento da criação, como um array em Java ou C. Uma estrutura de dados dinâmica cresce e encolhe conforme o programa executa, como uma lista em Python.

Arrays unidimensionais e bidimensionais

Um array unidimensional armazena itens do mesmo tipo sob um único nome, cada um acessado por seu índice. Em Python, uma lista assume esse papel:

marks = [67, 82, 45, 90]
marks[2]          # 45
marks[2] = 50     # change one item
marks.append(71)  # add at the end: [67, 82, 50, 90, 71]
len(marks)        # 5

Um array bidimensional é uma tabela: uma lista de linhas, onde cada linha é uma lista. O primeiro índice seleciona a linha e o segundo a coluna.

grid = [[4, 7, 1, 9],
        [2, 8, 5, 3],
        [6, 0, 7, 4]]

row_total = 0
for col in range(len(grid[1])):
    row_total = row_total + grid[1][col]
print(row_total)   # 2 + 8 + 5 + 3 = 18

Para visitar todas as células, aninhe dois laços: o externo sobre as linhas e o interno sobre as colunas.

Pilhas e filas

Ambos são tipos abstratos de dados: definidos por suas operações, não por como são armazenados.

stack = []
stack.append("A"); stack.append("B"); stack.append("C")   # push
stack.pop()        # "C"

from collections import deque
queue = deque()
queue.append("A"); queue.append("B"); queue.append("C")   # enqueue
queue.popleft()    # "A"

Antes de um pop ou dequeue, verifique isEmpty: remover de uma estrutura vazia é um underflow. Empilhar em uma pilha fixa cheia é um overflow.

Sequência, seleção e iteração

Todo algoritmo é construído a partir de três construtos: sequência (etapas em ordem), seleção (if, elif, else) e iteração (loops).

Um loop while cuja condição nunca se torna falsa é um loop infinito. Seleções aninhadas ou loops colocam um construto dentro do outro; a indentação mostra qual está dentro de qual.

Funções, parâmetros e escopo

Uma função é um bloco de código nomeado que pode ser chamado várias vezes. Ela recebe parâmetros e pode retornar um valor. Dividir um programa em funções é modularidade: cada parte é escrita, testada e reutilizada separadamente.

def mean(values):
    """Return the mean of a non-empty list of numbers."""
    total = 0
    for v in values:
        total = total + v
    return total / len(values)

print(mean([4, 8, 9]))   # 7.0

• Uma variável local, como total, existe apenas dentro da função enquanto ela executa.
• Uma variável global é definida no nível do módulo e pode ser lida onde as regras de escopo e vinculação de nomes do Python a resolvem; um nome local pode ocultá-la. Usar muitas variáveis globais torna um programa difícil de testar, pois qualquer função pode alterá-las.
• O docstring estabelece o contrato da função: o que ela precisa (uma lista não vazia) e o que retorna. mean([]) viola o contrato e levanta ZeroDivisionError.

Teste uma função contra seu contrato: valores normais, casos limite na borda do que ela aceita (uma lista com um item) e valores inválidos que ela deve rejeitar (uma lista vazia).

Medindo eficiência: Big O

Notação Big O fornece um limite assintótico superior para o crescimento de um custo escolhido em relação ao tamanho da entrada $n$. Indique se o custo analisado é pior-caso, caso médio ou melhor-caso. Constantes e termos menores são descartados.

Um único loop sobre os dados geralmente é $O(n)$; um loop dentro de outro loop sobre os mesmos dados geralmente é $O(n^2)$.

Busca linear e busca binária

Uma busca linear verifica cada item sucessivamente. Funciona em qualquer lista, ordenada ou não, e é $O(n)$.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

Uma busca binária precisa de uma lista ordenada. Verifica o item do meio e descarta a metade que não pode conter o alvo, então cada verificação reduz à metade o restante: $O(\log n)$.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Rastreamento para 23: low 0, high 8, mid 4 (16 < 23) → low 5; mid $(5 + 8) // 2 = 6$ (38 > 23) → high 5; mid 5: encontrado, retorne 5. Em uma lista não ordenada, a busca binária pode omitir um valor presente, portanto o contrato deve exigir entrada ordenada.

Bubble sort e selection sort

Uma bubble sort compara cada par de vizinhos e os troca se estiverem na ordem errada. Após cada passagem, o maior item restante "subiu" até o final.

def bubble_sort(a):
    n = len(a)
    for p in range(n - 1):
        swapped = False
        for i in range(n - 1 - p):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break

A bandeira swapped interrompe precocemente quando uma passagem não realiza trocas: a lista já está ordenada.

Uma selection sort encontra o menor item na parte não ordenada e o troca para a próxima posição.

def selection_sort(a):
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]

Passagens de cada ordenação em [5, 1, 4, 2]:

Ambas são $O(n^2)$. A selection sort faz no máximo $n - 1$ trocas; a bubble sort pode parar precocemente em uma lista quase ordenada.

Leitura e escrita de arquivos de texto

As variáveis de um programa são perdidas quando ele termina; um arquivo mantém os dados entre execuções. Abra o arquivo com um modo, use-o, depois feche-o.

with open("scores.txt", "a") as f:
    f.write("Ada,91\n")

best_name, best = "", -1
with open("scores.txt", "r") as f:
    for line in f:
        name, score = line.strip().split(",")
        if int(score) > best:
            best_name, best = name, int(score)
print(best_name, best)

• with fecha o arquivo automaticamente, mesmo se uma exceção ocorrer.
• Cada linha lida termina com "\n"; strip() o remove antes que split(",") divida a linha em campos.
• Abrir um arquivo inexistente para leitura levanta FileNotFoundError: capture-o com try … except.

Uma função que se chama a si mesma

Uma função recursiva se chama a si mesma em uma versão menor do mesmo problema. Ela precisa de duas partes:

1. Um caso base que é respondido diretamente, sem chamada adicional.
2. Um caso recursivo que chama a função com uma entrada menor, aproximando-se do caso base.

def total(items):
    if items == []:                      # base case
        return 0
    return items[0] + total(items[1:])   # recursive case

*Chamadas descem até o caso base; resultados voltam para cima

Cada chamada é colocada na pilha de chamadas com suas próprias variáveis locais. As chamadas aguardam até que o caso base retorne, depois terminam em ordem inversa: último chamado, primeiro terminado, como uma pilha.

Rastreando uma chamada recursiva

def power(b, e):
    if e == 0:
        return 1
    return b * power(b, e - 1)

power(3, 3) → 3 * power(3, 2) → 3 * 3 * power(3, 1) → 3 * 3 * 3 * power(3, 0) → 3 * 3 * 3 * 1 = 27: quatro chamadas no total.

Recursão ou iteração?

O quicksort é recursivo: escolhe um pivô, divide a lista em itens menores e maiores que o pivô, então aplica quick_recursively em cada parte. Seu caso médio é $O(n \log n)$, muito mais rápido que as ordenações $O(n^2)$ acima para grandes $n$.

1. Indique o tipo de dado mais adequado para cada caso: (a) número de alunos numa turma; (b) se uma porta está trancada; (c) um código postal como "SW1A 1AA"; (d) uma temperatura de 21.5 °C.
2. s = "Programming". Forneça (a) len(s); (b) s[3:7]; (c) s.find("g").
3. Classifique cada erro como sintaxe, tempo de execução ou lógica: (a) print("Hi"; (b) um loop que adiciona um item a menos; (c) int("abc").
4. Preencha uma tabela de traço para x = 1 depois while x < 20: x = x * 3, e indique o valor final de x.
5. Os itens 10, 20 e 30 são empilhados em uma pilha vazia, depois um item é desempilhado e 40 é empilhado. Indique o item no topo.
6. Os mesmos itens passam por uma fila: enfileira-se 10, 20, 30, desfilera-se uma vez, enfileira-se 40. Indique o item na frente.
7. Para a lista [3, 8, 12, 19, 25, 31, 40], liste os valores com que uma busca binária para 31 compara.
8. Mostre a lista [6, 3, 8, 2] após cada passagem de uma ordenação bolha.
9. Escreva uma função Python count_over(marks, limit) que retorne quantos elementos na lista são maiores que limit.
10. Explique por que abrir "log.txt" com modo "w" a cada início do programa perde dados e indique a correção.
11. AHL Para power acima, indique o número de chamadas feitas por power(2, 5) e o valor retornado.
12. AHL Explique o que acontece quando uma função recursiva não possui caso base.

Respostas.

1. (a) inteiro; (b) Booleano; (c) string, pois armazena letras e espaços; (d) real.

2. (a) 11; (b) "gram"; (c) 3.

3. (a) sintaxe: parêntese faltando; (b) lógica; (c) tempo de execução: um ValueError.

4. x assume os valores 1, 3, 9, 27; o loop para quando x é 27. Valor final 27.

5. Empilha-se 10, 20, 30; desempilha-se remove 30; empilha-se 40. Topo: 40.

6. Enqueue 10, 20, 30; dequeue remove 10; enqueue 40. Frente: 20.

7. low 0, high 6: mid 3, valor 19 < 31, logo low = 4; mid $(4 + 6) // 2 = 5$, valor 31: encontrado. Comparado com 19 e 31.

8. Passe 1: [3, 6, 2, 8]; passe 2: [3, 2, 6, 8]; passe 3: [2, 3, 6, 8].

9. Uma resposta:

   def count_over(notas, limite):
       contador = 0
       for n in notas:
           if n > limite:
               contador = contador + 1
       return contador
   

10. Modo "w" esvazia um arquivo existente antes de escrever, então o log anterior é perdido. Abra-o com "a" para anexar.

11. power(2, 5) chama a si mesmo com e = 4, 3, 2, 1, 0: 6 chamadas, retornando $2^5 =$ 32.

12. Ele se chama infinitamente; cada chamada adiciona um frame à pilha de execução até a memória acabar, um overflow da pilha (em Python uma RecursionError).

• Em uma tabela de traço, forneça uma nova linha sempre que uma variável mudar e mostre a saída separadamente. Verifique onde range para.
• Declare a convenção de indexação (Python indexa a partir de 0) antes de traçar uma matriz ou uma busca.
• Para uma resposta de busca binária, diga que a lista deve estar ordenada e forneça low, high e mid em cada verificação.
• Bubble sort e selection sort são ambos $O(n^2)$: compare-os por trocas, parada antecipada e passes, não por Big O.
• "Explique" uma pilha ou fila com sua ordem (LIFO ou FIFO), suas duas operações e um uso real.
• Ao escrever código, use nomes claros, feche arquivos com with e trate entrada inválida com try … except.
• AHL Uma resposta de recursão nomeia o caso base, o caso recursivo e como cada chamada se aproxima do caso base.