Videoaulas: Algoritmos e Programação de Computadores 2

1. Tipos mutáveis e não mutáveis em Python

Em Python, cada objeto armazenado na memória possui um tipo e um valor: o tipo informa ao interpretador como lidar com os bits e o valor representa os dados atuais. Tipos como int, float, bool, str, tuple e complex são imutáveis, ou seja, qualquer alteração supõe a criação de um novo objeto; já list, dict e set são mutáveis e permitem modificações in-place.

A atribuição e a passagem de objetos usam referências à mesma posição na memória, o que faz com que funções que mexem em listas ou dicionários também alterem o chamador; o mesmo não acontece com os tipos imutáveis, que preservam o valor original.

Exemplo: `lista = [1, 2]; clone = lista; clone.append(3)` faz com que `lista` veja o 3, mas `tupla = (1, 2); nova = tupla + (3,)` gera um novo objeto sem alterar a tupla original.

2. Arquivos

Arquivos texto e binários atendem finalidades diferentes: texto armazena caracteres codificados (UTF-8, ASCII etc.) e binário guarda bytes puros. Python abre arquivos com `open()` usando modos como 'r', 'w', 'rb', 'wb' e aceita argumentos de codificação; o uso de `with` garante que o arquivo seja fechado automaticamente.

Exemplo: `with open('dados.txt', 'w', encoding='utf-8') as f: f.write('Olá')` escreve caracteres legíveis, enquanto `with open('imagem.png', 'rb') as f: blob = f.read()` obtém bytes para manipular binários.

3. Programação Orientada a Objetos I

Uma classe define um molde abstrato e um objeto é sua instância concreta; o encapsulamento agrupa atributos (estado) e métodos (comportamento), permitindo controlar como o estado interno é acessado ou modificado.

Exemplo: `class Ponte:` com atributos `x` e `y` e métodos como `get()` e `move(dx, dy)` representa o estado e permite movimentação sem expor diretamente as variáveis internas.

4. Programação Orientada a Objetos II

Ao evoluir o modelo OO revisita-se herança, interface e representação pública. Instâncias podem customizar `__repr__` e `@property` para garantir que os objetos apresentem uma interface consistente mesmo quando o estado muda.

Exemplo: `ponte = Ponte(10, 20)` e um `__repr__` que retorna `Ponte(x=10, y=20)` facilita debugar e exibe claramente o conteúdo da instância.

5. Recursão I

Funções recursivas chamam a si mesmas e precisam de uma condição de base para interromper a chamada. Esse padrão é eficiente para percorrer listas ou definir funções matemáticas, como o fatorial, usando a própria definição do problema.

Exemplo: `def imprime(lista): if not lista: return print(lista[0]) imprime(lista[1:])` e `def fatorial(n): return 1 if n <= 1 else n * fatorial(n - 1)` mostram a base e a chamada recursiva.

6. Recursão II

Recursão usa a pilha de chamadas enquanto iteração usa laços explícitos; por isso, recursões profundas precisam de cuidados com memória. Memoização registra resultados já calculados para evitar recomputar subproblemas repetidos, acelerando o tempo de execução.

Exemplo: `memo = {0: 0, 1: 1}; def fib(n): if n in memo: return memo[n] memo[n] = fib(n - 1) + fib(n - 2) return memo[n]` reduz o tempo de Fibonacci de exponencial para linear.

7. Pilhas

Uma pilha (LIFO) aceita `push` e `pop`; o último dado inserido é o primeiro removido, sendo útil para operações reversíveis ou para rastrear a ordem de chamadas. Python usa listas com esses métodos para implementar pilhas de forma simples.

Exemplo: para converter o decimal 13 em binário, empilhe `n % 2` enquanto faz `n //= 2` e, depois, desempilhe para ler o número em ordem reversa.

8. Filas

Filas seguem o princípio FIFO: o primeiro elemento inserido é o primeiro a sair. Operações típicas são `enqueue` e `dequeue`; exercícios com duas filas (prioritária e normal) mostram como separar atendimento urgente e ordinário.

Exemplo: com `collections.deque`, mantenha `prioritaria` e `normal`, atendendo sempre a fila prioritária antes de esvaziar a normal, usando `append()` para inserir e `popleft()` para remover.

9. Lista

Listas sequenciais usam blocos contíguos enquanto listas encadeadas usam nós e ponteiros; a alocação estática reserva espaço fixo e a dinâmica cresce conforme necessário. Listas ordenadas facilitam buscas e inserções em posições corretas.

Exemplo: `lista = [1, 3, 5]` é uma lista dinâmica e está ordenada; `class Node:` com atributos `value` e `next` constrói uma lista encadeada para inserir elementos em ordem sem necessidade de realocar todo o vetor.

10. Árvores

Árvores são estruturas com nós, raiz, folhas e altura. Árvores binárias limitam a dois filhos, e árvores binárias de busca (BST) organizam valores para realizar buscas logarítmicas quando balanceadas.

Exemplo: ao buscar 42 em uma BST, compare com a raiz e desça pela esquerda ou direita conforme o valor, percorrendo poucos nós até encontrar ou concluir que o elemento não está presente.

11. Algoritmos clássicos de ordenação I

Bubble sort e insertion sort percorrem vetores e fazem trocas simples. Bubble repete varreduras para empurrar o maior valor ao final, enquanto insertion insere cada elemento na sublista ordenada. Ambos têm complexidade O(n²) e são estáveis.

Exemplo: `bubble_sort([3, 1, 4])` passa várias vezes pelo vetor até que nenhuma troca seja necessária.

12. Algoritmos clássicos de ordenação II

Merge sort usa divide e conquista: divide o vetor em metades, ordena recursivamente e mescla usando vetor auxiliar. Quick sort escolhe um pivô e particiona os elementos em menores e maiores, depois ordena cada parte.

Exemplo: `merge_sort([7, 2, 5])` divide em [7] e [2, 5], enquanto `quick_sort([7, 2, 5])` escolhe um pivô e move valores menores à esquerda.

13. Algoritmos clássicos de ordenação III

Heap sort utiliza um heap binário especializado (max-heap ou min-heap) para ordenar: primeiro transforma o vetor em heap, depois remove o maior elemento repetidamente e reconstrói o heap.

Exemplo: `import heapq; heap = nums[:] ; heapq.heapify(heap); while heap: ordenada.append(heapq.heappop(heap))`.

14. Conceitos fundamentais da web

A Internet é a infraestrutura global de redes; a Web é o conjunto de serviços acessados via HTTP. Clientes (browsers) pedem conteúdo a servidores. URLs são compostas por scheme, host e path.

Exemplo: na URL `https://portal.ufrj.br/cursos`, `https` é o scheme, `portal.ufrj.br` é o host e `/cursos` é o path.

15. HTML e JSON

HTML apresenta conteúdo em elementos, tags e atributos (como `div class="card"`). JSON, por sua vez, define a troca de dados em pares chave-valor, sendo muito usado em APIs.

Exemplo: uma página pode ter div class="perfil" e receber dados como `{"nome":"Ana","idade":22}`.

16. Python WWW API

urllib permite fazer requisições HTTP, lendo bytes e decodificando em texto. É comum buscar o HTML de uma página e aplicar parsers simples para extrair títulos ou links.

Exemplo: `with urllib.request.urlopen(url) as resposta: html = resposta.read().decode('utf-8')`.

17. Testes Automatizados

O módulo unittest organiza testes unitários em classes: cada método `test_` verifica um comportamento esperado, e o motor de verificação relata falhas e acertos.

Exemplo: `class TestSoma(unittest.TestCase): def test_valores(self): self.assertEqual(soma(2, 3), 5)`.

18. GIT e GitHub

Git controla versões criando commits com mensagens descritivas; branches isolam trabalho e pull requests facilitam revisão. GitHub hospeda repositórios remotos, sincronizados com push/pull.

Exemplo: `git add .`, `git commit -m "Corrige bug"`, `git push origin main` e a criação de `feature/docs` para desenvolver sem afetar a main.