Algoritmos definem procedimentos para solucionar problemas, e sua eficiência é avaliada mediante complexidade de tempo e espaço assintóticas. A notação grande O expressa a complexidade de tempo assintótica. Exemplos comuns incluem algoritmos de ordenação como seleção, bolha e merge, bem como algoritmos de busca sequencial e binária.

def ordenacao_por_selecao(dados_brutos, comparacao=lambda x, y: x < y):
    """Ordenação simples por seleção"""
    elementos = dados_brutos[:]
    for posicao in range(len(elementos) - 1):
        menor_indice = posicao
        for idx in range(posicao + 1, len(elementos)):
            if comparacao(elementos[idx], elementos[menor_indice]):
                menor_indice = idx
        elementos[posicao], elementos[menor_indice] = elementos[menor_indice], elementos[posicao]
    return elementos

def ordenacao_bolha_melhorada(dados_brutos, comparacao=lambda x, y: x > y):
    """Ordenação por bolha aprimorada"""
    elementos = dados_brutos[:]
    for i in range(len(elementos) - 1):
        houve_troca = False
        for j in range(i, len(elementos) - 1 - i):
            if comparacao(elementos[j], elementos[j + 1]):
                elementos[j], elementos[j + 1] = elementos[j + 1], elementos[j]
                houve_troca = True
        if houve_troca:
            houve_troca = False
            for j in range(len(elementos) - 2 - i, i, -1):
                if comparacao(elementos[j - 1], elementos[j]):
                    elementos[j], elementos[j - 1] = elementos[j - 1], elementos[j]
                    houve_troca = True
        if not houve_troca:
            break
    return elementos

def ordenacao_merge(dados, comparacao=lambda x, y: x <= y):
    """Ordenação por merge (algoritmo de divisão e conquista)"""
    if len(dados) < 2:
        return dados[:]
    metade = len(dados) // 2
    esquerda = ordenacao_merge(dados[:metade], comparacao)
    direita = ordenacao_merge(dados[metade:], comparacao)
    return combinar(esquerda, direita, comparacao)

def combinar(seq1, seq2, comparacao):
    """Combina duas listas ordenadas em uma lista ordenada"""
    resultado = []
    idx1, idx2 = 0, 0
    while idx1 < len(seq1) and idx2 < len(seq2):
        if comparacao(seq1[idx1], seq2[idx2]):
            resultado.append(seq1[idx1])
            idx1 += 1
        else:
            resultado.append(seq2[idx2])
            idx2 += 1
    resultado += seq1[idx1:]
    resultado += seq2[idx2:]
    return resultado

def busca_sequencial(elementos, alvo):
    """Busca sequencial"""
    for indice, item in enumerate(elementos):
        if item == alvo:
            return indice
    return -1

def busca_binaria(elementos, alvo):
    """Busca binária"""
    inicio, fim = 0, len(elementos) - 1
    while inicio <= fim:
        meio = (inicio + fim) // 2
        if alvo > elementos[meio]:
            inicio = meio + 1
        elif alvo < elementos[meio]:
            fim = meio - 1
        else:
            return meio
    return -1

Expressões geradoras (compreensões) permitem criar listas, conjuntos e dicionários de forma concisa. Exemplo de dicionário com compreensão para filtrar valores acima de 100:

cotacoes = {
    'MELI': 180.75, 'AMZN': 1350.20, 'MSFT': 210.50,
    'GOOGL': 1420.80, 'PETR4': 28.30, 'VALE3': 85.40
}
cotacoes_altas = {ticker: preco for ticker, preco in cotacoes.items() if preco > 100}
print(cotacoes_altas)

Listas aninhadas devem ser criadas com cuidado para evitar referências indesejadas. Exemplo de matriz para notas de alunos:

nomes = ['Ana', 'Carlos', 'Maria']
disciplinas = ['Português', 'Matemática', 'Ciências']
notas = [[None] * len(disciplinas) for _ in range(len(nomes))]
for linha, nome in enumerate(nomes):
    for coluna, disciplina in enumerate(disciplinas):
        notas[linha][coluna] = float(input(f'Insira a nota de {nome} em {disciplina}: '))

Módulos úteis incluem heapq para operações com heaps e itertools para iterações combinatórias:

import heapq
import itertools

lista_numeros = [45, 22, 89, 12, 67, 34]
print(heapq.nlargest(3, lista_numeros))
print(heapq.nsmallest(3, lista_numeros))

permutacoes = list(itertools.permutations('ABC'))
combinacoes = list(itertools.combinations('ABCD', 2))
produto_cartesiano = list(itertools.product('XY', '12'))

O módulo collections oferece utilitários como Counter para contagem de elementos:

from collections import Counter

palavras = ['python', 'java', 'python', 'c++', 'python', 'java']
contagem = Counter(palavras)
print(contagem.most_common(2))

Algoritmos Comuns

Algoritmos comuns incluem:

• Força bruta: testa todas as possibilidades até encontrar a solução.
• Guloso: toma decisões localmente ótimas em cada passo, sem garantir a solução global ótima.
• Divisão e conquista: divide o problema em subproblemas menores, resolve recursivamente e combina os resultados.
• Backtracking: explora caminhos e retrocede quando encontra becos sem saída.
• Programação dinâmica: resolve subproblemas sobrepostos armazenando soluções intermediárias.

Exemplo de força bruta para o problema dos cem ovos e cem galos:

# Galo custa 5 moedas, galinha 3 moedas, e pintinho 1 moeda por 3 unidades
# Com 100 moedas para comprar 100 aves
for g in range(20):
    for galinha in range(33):
        pintinho = 100 - g - galinha
        if 5 * g + 3 * galinha + pintinho // 3 == 100 and pintinho % 3 == 0:
            print(f'Galo: {g}, Galinha: {galinha}, Pintinho: {pintinho}')

Exemplo guloso para o problema da mochila com limite de peso:

class Item:
    """Representa um item com nome, valor e peso"""
    def __init__(self, nome, valor, peso):
        self.nome = nome
        self.valor = valor
        self.peso = peso
    
    @property
    def razao_valor_peso(self):
        return self.valor / self.peso

def resolver_mochila_gulosa(itens, capacidade_maxima):
    itens_ordenados = sorted(itens, key=lambda x: x.razao_valor_peso, reverse=True)
    peso_total = 0
    valor_total = 0
    for item in itens_ordenados:
        if peso_total + item.peso <= capacidade_maxima:
            peso_total += item.peso
            valor_total += item.valor
    return valor_total

Exemplo de divisão e conquista com ordenação rápida:

def ordenacao_rapida(dados, comparacao=lambda x, y: x <= y):
    elementos = dados[:]
    _ordenacao_rapida_recursiva(elementos, 0, len(elementos) - 1, comparacao)
    return elementos

def _ordenacao_rapida_recursiva(elementos, inicio, fim, comparacao):
    if inicio < fim:
        pivo_posicao = _particionar(elementos, inicio, fim, comparacao)
        _ordenacao_rapida_recursiva(elementos, inicio, pivo_posicao - 1, comparacao)
        _ordenacao_rapida_recursiva(elementos, pivo_posicao + 1, fim, comparacao)

def _particionar(elementos, inicio, fim, comparacao):
    pivo = elementos[fim]
    i = inicio - 1
    for j in range(inicio, fim):
        if comparacao(elementos[j], pivo):
            i += 1
            elementos[i], elementos[j] = elementos[j], elementos[i]
    elementos[i + 1], elementos[fim] = elementos[fim], elementos[i + 1]
    return i + 1

Exemplo de backtracking para o passeio do cavalo em um tabuleiro de xadrez:

import sys
sys.setrecursionlimit(10000)

TAMANHO_TABULEIRO = 5
total_solucoes = 0

def exibir_tabuleiro(tabuleiro):
    for linha in tabuleiro:
        print(' '.join(f'{c:3d}' for c in linha))
    print()

def passeio_cavalo(tabuleiro, linha, coluna, passo=1):
    global total_solucoes
    if 0 <= linha < TAMANHO_TABULEIRO and 0 <= coluna < TAMANHO_TABULEIRO and tabuleiro[linha][coluna] == 0:
        tabuleiro[linha][coluna] = passo
        if passo == TAMANHO_TABULEIRO * TAMANHO_TABULEIRO:
            total_solucoes += 1
            print(f'Solução {total_solucoes}:')
            exibir_tabuleiro(tabuleiro)
        movimentos = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
        for dx, dy in movimentos:
            passeio_cavalo(tabuleiro, linha + dx, coluna + dy, passo + 1)
        tabuleiro[linha][coluna] = 0

tabuleiro = [[0] * TAMANHO_TABULEIRO for _ in range(TAMANHO_TABULEIRO)]
passeio_cavalo(tabuleiro, TAMANHO_TABULEIRO - 1, TAMANHO_TABULEIRO - 1)

Exemplo de programação dinâmica para a sequência de Fibonacci:

def fibonacci_dp(n, memo=None):
    if memo is None:
        memo = {}
    if n in (1, 2):
        return 1
    if n not in memo:
        memo[n] = fibonacci_dp(n - 1, memo) + fibonacci_dp(n - 2, memo)
    return memo[n]

Exemplo de programação dinâmica para a soma máxima de sublista contígua:

def soma_maxima_sublista(numeros):
    n = len(numeros)
    max_global = max_parcial = numeros[0]
    for i in range(1, n):
        max_parcial = max(numeros[i], max_parcial + numeros[i])
        max_global = max(max_global, max_parcial)
    return max_global

Funções em Python

Funções são cidadãs de primeira classe, podendo ser atribuídas a variáveis, passadas como argumentos e retornadas de outras funções. Funções de alta ordem como map e filter podem ser substituídas por compreensões:

quadrados_impares = [x**2 for x in range(1, 10) if x % 2 != 0]
print(quadrados_impares)

Parâmetros incluem posicionais, variáveis (*args), de palavra-chave (**kwargs), e de palavra-chave nomeados. Funções anônimas são definidas com lambda. O escopo de variáveis segue a ordem LEGB (Local, Enclosed, Global, Built-in), com as palavras-chave global e nonlocal para modificar escopos.

Decoradores modificam o comportamento de funções ou classes. Exemplo de decorador para medir tempo de execução:

from functools import wraps
from time import time

def medir_tempo(func):
    @wraps(func)
    def envoltorio(*args, **kwargs):
        inicio = time()
        resultado = func(*args, **kwargs)
        print(f'{func.__name__} executada em {time() - inicio:.4f} segundos')
        return resultado
    return envoltorio

Decoradores com parâmetros podem ser implementados usando funções que retornam decoradores ou classes com __call__.

Programação Orientada a Objetos

Os pilares da POO são encapsulamento, herança e polimorfismo. Relações entre classes incluem é-um (herança), tem-um (associação/agregação/composição) e usa-um (dependência).

Exemplo de sistema de folha de pagamento:

from abc import ABC, abstractmethod

class Funcionario(ABC):
    def __init__(self, nome):
        self.nome = nome
    
    @abstractmethod
    def calcular_salario(self):
        pass

class Gerente(Funcionario):
    def calcular_salario(self):
        return 15000.0

class Programador(Funcionario):
    def __init__(self, nome, horas_trabalhadas=0):
        super().__init__(nome)
        self.horas_trabalhadas = horas_trabalhadas
    
    def calcular_salario(self):
        return 200.0 * self.horas_trabalhadas

class Vendedor(Funcionario):
    def __init__(self, nome, vendas=0.0):
        super().__init__(nome)
        self.vendas = vendas
    
    def calcular_salario(self):
        return 1800.0 + self.vendas * 0.05

Cópia de objetos envolve cópia rasa (referências) e cópia profunda (novos objetos). Coleta de lixo em Python usa contagem de referências, com marcação e limpeza e coleta por gerações para lidar com referências circulares. Módulo weakref permite criar referências fracas para evitar referências circulares.

Métodos e atributos mágicos permitem sobrecarga de operadores e personalização de comportamento. Mixins são classes projetadas para adicionar funiconalidades específicas sem herança múltipla complexa. Exemplo de mixin para dicionário com chave única:

class MixinSetUmaVez:
    def __setitem__(self, chave, valor):
        if chave in self:
            raise KeyError(f'Chave {chave} já definida')
        super().__setitem__(chave, valor)

class DicionarioUnico(MixinSetUmaVez, dict):
    pass

Metaprogramação usa metaclasses para customizar criação de classes. Exemplo de metaclass para padrão singleton thread-safe:

import threading

class MetaSingleton(type):
    def __init__(cls, *args, **kwargs):
        cls._instancia = None
        cls._trava = threading.Lock()
        super().__init__(*args, **kwargs)
    
    def __call__(cls, *args, **kwargs):
        if cls._instancia is None:
            with cls._trava:
                if cls._instancia is None:
                    cls._instancia = super().__call__(*args, **kwargs)
        return cls._instancia

class Presidente(metaclass=MetaSingleton):
    pass

Princípios de design orientado a objetos incluem SOLID (Responsabilidade Única, Aberto/Fechado, Substituição de Liskov, Segregação de Interface, Inversão de Dependência), junto com composição sobre herança e princípio do menor conhecimento. Padrões GoF são categorizados em criação, estrutura e comportamento.

Iteradores e Geradores

Iteradores implementam __iter__ e __next__. Geradores são criados com expressões geradoras ou a palavra-chave yield:

def gerador_fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
        yield a

class IteradorFibonacci:
    def __init__(self, n):
        self.n = n
        self.a, self.b = 0, 1
        self.indice = 0
    
    def __iter__(self):
        return self
    
    def __next__(self):
        if self.indice < self.n:
            self.a, self.b = self.b, self.a + self.b
            self.indice += 1
            return self.a
        raise StopIteration

Programação Concorrente

Python oferece três abordagens para concorrência: multithreading, multiprocessing e E/S assíncrona.

Multithreading usa a classe Thread com travas para sincronização. O GIL (Global Interpreter Lock) limita a execução paralela em CPython. Exemplo de geração de miniaturas com threads:

import glob
import os
import threading
from PIL import Image

DIRETORIO_SAIDA = 'miniaturas'

def criar_miniatura(caminho_entrada, tamanho):
    nome_arquivo = os.path.basename(caminho_entrada)
    caminho_saida = f'{DIRETORIO_SAIDA}/{nome_arquivo}_{tamanho[0]}x{tamanho[1]}.png'
    imagem = Image.open(caminho_entrada)
    imagem.thumbnail(tamanho, Image.ANTIALIAS)
    imagem.save(caminho_saida, 'PNG')

if not os.path.exists(DIRETORIO_SAIDA):
    os.makedirs(DIRETORIO_SAIDA)

for arquivo in glob.glob('imagens/*.png'):
    for tam in (32, 64, 128):
        threading.Thread(target=criar_miniatura, args=(arquivo, (tam, tam))).start()

Multiprocessing contorna o GIL para tarefas intensivas em CPU. Exemplo com pool de processos:

import concurrent.futures
import math

def eh_primo(numero):
    if numero < 2:
        return False
    for divisor in range(2, int(math.sqrt(numero)) + 1):
        if numero % divisor == 0:
            return False
    return True

numeros = [1000000007, 1000000009, 1000000021, 1000000033]
with concurrent.futures.ProcessPoolExecutor() as executor:
    resultados = executor.map(eh_primo, numeros)
    for num, primo in zip(numeros, resultados):
        print(f'{num} é primo? {primo}')

E/S assíncrona usa asyncio e await para operações não bloqueantes. Exemplo de coleta assíncrona de títulos de páginas web:

import asyncio
import aiohttp
import re

PADRAO_TITULO = re.compile(r'\<title>(?P<titulo>.*)\</titulo></title>')

async def buscar_pagina(session, url):
    async with session.get(url) as resposta:
        return await resposta.text()

async def mostrar_titulo(url):
    async with aiohttp.ClientSession() as session:
        html = await buscar_pagina(session, url)
        correspondencia = PADRAO_TITULO.search(html)
        if correspondencia:
            print(f'Título de {url}: {correspondencia.group("titulo")}')

urls = [
    'https://www.python.org/',
    'https://github.com/',
    'https://stackoverflow.com/'
]

loop = asyncio.get_event_loop()
tarefas = [mostrar_titulo(url) for url in urls]
loop.run_until_complete(asyncio.gather(*tarefas))
loop.close()

A escolha entre multithreading, multiprocessing e asyncio depende do tipo de tarefa: I/O-bound vs CPU-bound. Ferramentas como Celery e filas de mensagens (RabbitMQ, Redis) são usadas para tarefas distribuídas e assíncronas em produção.