Hoje, dia 169 do nosso curso de ciência da computação, dedicamos a aula a uma revisão geral dos principais tópicos que cobrimos até agora. Foi uma oportunidade de consolidar o conhecimento e identificar pontos que precisam de mais atenção. Abaixo, organizo um resumo dos temas discutidos.

1. Sistemas Operacionais

Revisitamos os conceitos de processos e threads, os estados de um processo e as operações de escalonamento. Os principais algoritmos de escalonamento vistos foram FIFO (First In, First Out), Round Robin (com quantum de tempo) e SJF (Shortest Job First). Discutimos as vantagens e desvantagens de cada um em cenários interativos e por lotes.

Em gerência de memória, destacamos a diferença entre paginação e segmentação. A paginação divide a memória em páginas de tamanho fixo, eliminando a fragmentação externa. A segmentação divide em segmentos lógicos (código, dados, pilha) mas pode causar fragmentação externa. Vimos também o conceito de memória virtual, swapping e os algoritmos de substituição de páginas como FIFO, LRU e Ótimo.

Por fim, discutimos sistemas de arquivos: organização em diretórios, alocação contígua, encadeada e indexada, e as permissões de acesso em sistemas Unix.

2. Redes de Computadores

Em redes, fizemos uma revisão do modelo OSI e da pilha TCP/IP, camada por camada. No nível de rede, focamos no endereçamento IPv4: endereços classe A, B, C e CIDR (Classless Inter-Domain Routing). Vimos como calcular a máscara de sub-rede e o endereço de rede e broadcast.

Abordamos roteamento estático (configurado manualmente) e dinâmico com protocolos como RIP e OSPF. Também discutimos protocolos da camada de transporte: TCP (orientado à conexão, confiável) e UDP (não confiável, rápido). Revisamos o funcionamento do ARP para resolução de endereços IP para MAC, e a importância do DNS para tradução de nomes de domínio.

3. Estruturas de Dados

Revisamos as estruturas lineares fundamentais: arrays (acesso aleatório O(1), inserção/remoção O(n)), listas encadeadas (inserção/remoção O(1) na cabeça, busca O(n)), pilhas (LIFO) e filas (FIFO). Comparamos suas implementações e complexidades.

Em árvores, vimos árvores binárias e suas propriedades. Percorremos árvores em pré-ordem, em-ordem e pós-ordem. Introduzimos árvores de busca binária (BST) com operações de inserção, busca e remoção. Por fim, falamos sobre árvores balanceadas como AVL e Red-Black, que garantem altura O(log n).

4. Algoritmos

Revimos algoritmos de busca: busca linear O(n) e busca binária O(log n) (aplicável a arrays ordenados). Na ordenação, comparamos Bubble Sort (O(n²)), Insertion Sort (O(n²) mas eficiente para quase ordenado), Merge Sort (O(n log n), estável) e Quick Sort (O(n log n) médio, O(n²) pior caso, com escolha de pivô).

Discutimos a notação Big-O e como analisar a complexidade de tempo e espaço. Também abordamos algoritmos de busca em grafos: DFS (busca em profundidade) e BFS (busca em largura), com aplicações em conectividade e caminhos mínimos (não ponderados).

Resumo dos Pontos Principais

  • Escalonamento de processos: FIFO (simples, mas não adequado para interativos), Round Robin (justo, com quantum definido), SJF (menor tempo primeiro, ótimo para tempo médio de espera).
  • Paginação vs Segmentação: paginação usa páginas fixas, sem fragmentação externa; segmentação usa segmentos lógicos, pode ter fragmentação externa.
  • Endereçamento IP: IPv4 32 bits, notação decimal; CIDR permite sub-redes mais flexíveis (/24, /16, etc.).
  • Complexidade de algoritmos: busca binária O(log n), Merge Sort O(n log n), Bubble Sort O(n²).
  • Árvore de busca binária: busca O(h), onde h é a altura; árvores balanceadas mantêm h ≈ log n.

Perguntas Frequentes

1. Qual a diferença entre paginação e segmentação?

Paginação divide a memória em páginas de tamanho fixo (ex.: 4 KB) e não requer que o programa esteja contiguamente na memória física. A segmentação divide o programa em segmentos de tamanho variável (código, dados, pilha), baseados na lógica do programa, mas pode causar fragmentação externa. Sistemas modernos frequentemente combinam ambos (segmentação com paginação).

2. O que é uma máscara de sub-rede e como calcular o endereço de rede?

A máscara de sub-rede é um número de 32 bits que indica quais bits do endereço IP pertencem à rede (bits 1) e quais ao host (bits 0). Para calcular o endereço de rede, aplica-se o operador AND binário entre o IP e a máscara. Por exemplo, IP 192.168.1.15 com máscara 255.255.255.0 resulta em rede 192.168.1.0.

3. Por que o Merge Sort é preferível ao Bubble Sort em listas grandes?

Merge Sort possui complexidade O(n log n) no pior caso, enquanto Bubble Sort é O(n²). Para listas grandes, O(n log n) cresce muito mais devagar, tornando o Merge Sort significativamente mais rápido. Além disso, Merge Sort é estável e tem comportamento previsível, embora exija memória auxiliar O(n).

4. Qual a utilidade da busca em profundidade (DFS) em grafos?

DFS é usada para percorrer ou buscar nós em um grafo, explorando o máximo possível de cada ramo antes de retroceder. Aplicações incluem detecção de ciclos, ordenação topológica, componentes fortemente conexos e resolução de labirintos. Sua complexidade é O(V+E) para grafos representados por listas de adjacência.

Essa revisão nos ajudou a conectar os diversos tópicos e preparar para os próximos desafios. Continuaremos aprofundando cada área nas próximas aulas.