Supercomp_Projeto_2024.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_RogNPH3CUzH"
      },
      "source": [
        "# Projeto SuperComputação 2024.1\n",
        "\n",
        "## Otimização de Rotas de Veículos (_Vehicle Routing Problem_ - VRP)\n",
        "\n",
        "**Objetivo:**\n",
        "\n",
        "Desenvolver uma aplicação em C++ que otimize as rotas de uma frota de veículos destinados à entrega de produtos a diversos clientes, buscando minimizar o custo total das rotas.\n",
        "\n",
        "\n",
        "**Descrição:**\n",
        "\n",
        "Você está encarregado de criar uma solução computacional para o problema de Otimização de Rotas de Veículos (VRP) para uma empresa de logística. A empresa possui uma frota de veículos que são usados para entregar produtos a uma série de clientes. Cada veículo tem uma capacidade de carga máxima, e cada cliente tem uma demanda específica que deve ser atendida. O objetivo é determinar as rotas ótimas para os veículos, de forma que todos os clientes sejam atendidos, respeitando as restrições de capacidade dos veículos, e minimizando o custo total das entregas.\n",
        "\n",
        "\n",
        "**Restrições e Requisitos:**\n",
        "1. **Capacidade dos Veículos:** Cada veículo tem uma capacidade máxima de carga que não pode ser excedida.\n",
        "2. **Demanda dos Clientes:** Cada cliente tem uma demanda específica que deve ser completamente atendida por um único veículo.\n",
        "3. **Custo da Rota:** Cada rota possui um custo, que simboliza o cômputo agregado da distância percorrida, do tempo de entrega, e do consumo de combustível. O objetivo é minimizar o custo total.\n",
        "4. **Número máximo de visitas por rota:** Cada rota pode visitar um número máximo de cidades.\n",
        "5. **Ponto de Partida e Chegada:** Todos os veículos começam e terminam suas rotas no depósito da empresa.\n",
        "\n",
        "\n",
        "**Desafios Computacionais:**\n",
        "\n",
        "- O VRP é um problema NP-difícil, o que significa que sua complexidade computacional cresce exponencialmente com o aumento do número de clientes e veículos.\n",
        "- A busca exaustiva por todas as possíveis combinações de rotas torna-se impraticável para instâncias maiores do problema.\n",
        "\n",
        "\n",
        "**Composição da Solução:**\n",
        "1. Implementação de um algoritmo de _busca global_ para o problema (força bruta);\n",
        "2. Implementação de alguma solução aproximada (_heurística_ ou _busca local_);\n",
        "3. Implementação de 2 soluções paralelizadas, sendo:\n",
        "\n",
        "  a. _Paralelização com Threads OpenMP_: Utilizar threads e a biblioteca OpenMP para paralelizar o algoritmo desenvolvido, com o objetivo de reduzir o tempo de execução. Analisar e implementar a paralelização de componentes do algoritmo que possam se beneficiar da execução concorrente, como a geração de soluções iniciais ou a busca local.\n",
        "\n",
        "  b. _Paralelização e Distribuição do Processamento com MPI_: Implementar uma versão do algoritmo que utilize a interface de passagem de mensagens MPI para distribuir o processo de busca de soluções em múltiplos processos, possivelmente executando em diferentes nós de um cluster. A estratégia deve permitir a exploração paralela do espaço de soluções e a troca eficiente de informações entre os processos.\n",
        "\n",
        "\n",
        "\n",
        "**Entregáveis:**\n",
        "\n",
        "1. **Código Fonte:** Código fonte em C++ comentado e organizado.\n",
        "2. **Relatório:** Um relatório descrevendo a abordagem utilizada, incluindo descrição das heurísticas e métodos de busca local, bem como as estratégias de paralelização adotadas.\n",
        "3. **Análise de Desempenho:** Uma análise de desempenho da solução proposta, incluindo tempos de execução e qualidade das soluções encontradas, com base em instâncias de teste de diferentes tamanhos.\n",
        "4. **Instruções de Uso:** Breve documentação sobre como compilar e executar a aplicação, incluindo exemplos de uso.\n",
        "\n",
        "\n",
        "**DICA**:\n",
        "Não deixe de estudar os exemplos deste link https://vrpy.readthedocs.io/en/master/examples.html, para entender como gerar a avaliar soluções para o problema. Compare sua solução com a solução desta biblioteca!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LKBT7FdpGXv5"
      },
      "source": [
        "### GERAÇÃO DE INSTÂNCIAS DO PROBLEMA\n",
        "\n",
        "Execute o código abaixo algumas vezes gerando instâncias de tamanhos e complexidades distintas. Você deve experimentar alterações de:\n",
        "- **num_nos**: número de cidades a serem visitados;\n",
        "- **probabilidade**: a probabilidade de ser criada uma rota direta entre 2 cidades;\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {
        "id": "jo54M0TVqJjV"
      },
      "outputs": [],
      "source": [
        "import random\n",
        "# from networkx import set_node_attributes\n",
        "\n",
        "def gerar_dicionario_demandas(N):\n",
        "    \"\"\"\n",
        "    Gera um dicionário onde a chave é um int de 1 até N e o valor é um inteiro aleatório de 1 até 10.\n",
        "\n",
        "    :param N: Número máximo para as chaves do dicionário.\n",
        "    :return: Dicionário com chaves de 1 até N e valores inteiros aleatórios de 1 até 10.\n",
        "    \"\"\"\n",
        "    return {i: random.randint(1, 10) for i in range(1, N)}\n",
        "\n",
        "\n",
        "def gerar_entradas_grafo(num_nos, max_peso=100, probabilidade=0.25):\n",
        "    \"\"\"\n",
        "    Gera um grafo para o problema de otimização de rotas de veículos.\n",
        "\n",
        "    :param num_nos: Número de nós no grafo, incluindo o depósito.\n",
        "    :param max_peso: Peso máximo para as arestas do grafo.\n",
        "    :param probabilidade: Probabilidade de criar uma rota entre duas cidades.\n",
        "    :return: Um dicionário representando o grafo onde as chaves são tuplas representando as arestas (nó1, nó2)\n",
        "             e os valores são os pesos dessas arestas.\n",
        "    \"\"\"\n",
        "    grafo = {}\n",
        "    # Gerar pesos para arestas entre o depósito e outros nós\n",
        "    for i in range(1, num_nos):\n",
        "        grafo[(0, i)] = random.randint(1, max_peso)\n",
        "        grafo[(i, 0)] = grafo[(0, i)]  # Assume que a distância de volta ao depósito é a mesma\n",
        "\n",
        "    # Gerar pesos para arestas entre todos os outros pares de nós\n",
        "    for i in range(1, num_nos+1):\n",
        "        for j in range(i+1, num_nos):\n",
        "            if random.random() > (1 - probabilidade):  # Verifica a probabilidade\n",
        "                peso = random.randint(1, max_peso)\n",
        "                grafo[(i, j)] = peso\n",
        "\n",
        "    return grafo\n",
        "\n",
        "############################################\n",
        "#             Exemplo de uso\n",
        "############################################\n",
        "num_nos = 12                                  # Número total de nós incluindo o depósito\n",
        "demandas = gerar_dicionario_demandas(num_nos)  # Gera as demandas para cada nó\n",
        "grafo = gerar_entradas_grafo(num_nos)          # Gera o grafo que representa os locais e custos entre eles\n",
        "\n",
        "# Salva o grafo em um arquivo TXT\n",
        "with open('grafo.txt', 'w') as arquivo:\n",
        "  arquivo.write(str(num_nos) + \"\\n\")    # Número de nós, incluindo depósito\n",
        "  for local, demanda in demandas.items():\n",
        "    linha = f\"{local} {demanda}\\n\"      # Par LOCAL DEMANDA\n",
        "    arquivo.write(linha)\n",
        "\n",
        "  arquivo.write(str(len(grafo)) + \"\\n\") # Número de arestas\n",
        "  for aresta, peso in grafo.items():\n",
        "    linha = f\"{aresta[0]} {aresta[1]} {peso}\\n\" # Trio: ORIGEM DESTINO CUSTO\n",
        "    arquivo.write(linha)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CqegkP6mGomB"
      },
      "source": []
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### GERAÇÃO DE SOLUÇÕES\n",
        "\n",
        "Instale a biblioteca [VRPy](https://vrpy.readthedocs.io/en/latest/getting_started.html) para resolver problemas de otimização de rotas.\n",
        "\n",
        "Para cada instância do problema gerada, execute este código para gerar a solução esperada.\n",
        "\n",
        "Não deixe de estudar a documentação da biblioteca! Especialmente este link: https://vrpy.readthedocs.io/en/latest/examples.html#a-simple-example\n",
        "\n",
        "Aqui você pode gerar soluções diferentes alterando:\n",
        "- **load_capacity**: a quantidade e capacidade de veículos;\n",
        "- **num_stops**: o número máximo de paradas numa rota;"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {
        "id": "FkYttRbFvY48"
      },
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "INFO:vrpy.vrp:new upper bound : max num stops = 4\n",
            "INFO:vrpy.vrp:Clarke & Wright solution found with value 444 and 6 vehicles\n",
            "INFO:vrpy.vrp:Greedy solution found with value 536 and 7 vehicles\n"
          ]
        },
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "INFO:vrpy.vrp:iteration 0, 444.0\n",
            "INFO:vrpy.master_solve_pulp:total cost = 444.0\n"
          ]
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "No negative cost cycle has been found and elementary set to true.\n",
            "Consider setting elementary to false.\n",
            "No negative cost cycle has been found and elementary set to true.\n",
            "Consider setting elementary to false.\n",
            "No negative cost cycle has been found and elementary set to true.\n",
            "Consider setting elementary to false.\n",
            "No negative cost cycle has been found and elementary set to true.\n",
            "Consider setting elementary to false.\n",
            "No negative cost cycle has been found and elementary set to true.\n",
            "Consider setting elementary to false.\n",
            "No negative cost cycle has been found and elementary set to true.\n",
            "Consider setting elementary to false.\n",
            "No negative cost cycle has been found and elementary set to true.\n",
            "Consider setting elementary to false.\n",
            "No negative cost cycle has been found and elementary set to true.\n",
            "Consider setting elementary to false.\n",
            "No negative cost cycle has been found and elementary set to true.\n",
            "Consider setting elementary to false.\n",
            "No negative cost cycle has been found and elementary set to true.\n",
            "Consider setting elementary to false.\n"
          ]
        }
      ],
      "source": [
        "from networkx import DiGraph, set_node_attributes\n",
        "from vrpy import VehicleRoutingProblem\n",
        "\n",
        "\n",
        "def ler_arquivo_grafo(caminho_arquivo):\n",
        "    with open(caminho_arquivo, 'r') as arquivo:\n",
        "        # Lê o número de nós\n",
        "        N = int(arquivo.readline().strip())-1\n",
        "\n",
        "        # Lê as demandas dos nós\n",
        "        demandas = {}\n",
        "        for _ in range(N):\n",
        "            linha = arquivo.readline().strip().split()\n",
        "            id_no, demanda = int(linha[0]), int(linha[1])\n",
        "            demandas[id_no] = demanda\n",
        "\n",
        "        # Lê o número de arestas\n",
        "        K = int(arquivo.readline().strip())\n",
        "\n",
        "        # Lê as arestas\n",
        "        arestas = []\n",
        "        for _ in range(K):\n",
        "            linha = arquivo.readline().strip().split()\n",
        "            origem, destino, peso = int(linha[0]), int(linha[1]), int(linha[2])\n",
        "            arestas.append((origem, destino, peso))\n",
        "\n",
        "    return demandas, arestas\n",
        "\n",
        "############################################\n",
        "#             Usando a funcao\n",
        "############################################\n",
        "caminho_arquivo = 'grafo.txt'\n",
        "demandas, arestas = ler_arquivo_grafo(caminho_arquivo)\n",
        "\n",
        "G = DiGraph()\n",
        "for inicio, fim, custo in arestas:\n",
        "    if inicio==0: inicio=\"Source\"\n",
        "    if fim==0: fim=\"Sink\"\n",
        "    G.add_edge(inicio, fim, cost=custo)\n",
        "\n",
        "set_node_attributes(G, values=demandas, name=\"demand\")\n",
        "\n",
        "prob = VehicleRoutingProblem(G, load_capacity=10)  # Pode alterar a capacidade\n",
        "prob.num_stops = 5                                 # Pode alterar o número máximo de paradas\n",
        "prob.solve()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "gXaAfAXPJ7dD",
        "outputId": "399b39c4-7e6c-4e61-cb80-db037d933ef0"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "{1: ['Source', 2, 'Sink'],\n",
              " 2: ['Source', 1, 4, 'Sink'],\n",
              " 3: ['Source', 5, 'Sink'],\n",
              " 4: ['Source', 6, 'Sink'],\n",
              " 5: ['Source', 7, 'Sink'],\n",
              " 6: ['Source', 3, 'Sink']}"
            ]
          },
          "execution_count": 11,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "prob.best_routes"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 181,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TNB2OIKwxhwt",
        "outputId": "7185e6f1-4a3c-4f99-8a2b-adc385d9ece9"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "408"
            ]
          },
          "execution_count": 181,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "prob.best_value"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 182,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "t2OYDBTR00dd",
        "outputId": "9d84d408-0f0c-465a-f7c1-edc1eb17ffa3"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "{1: 70, 2: 92, 3: 80, 4: 92, 5: 74}"
            ]
          },
          "execution_count": 182,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "prob.best_routes_cost"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 170,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HI4JEITxeK6S",
        "outputId": "b74ed50f-5bfb-4884-b5c0-c0ff4f03f2cf"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "{1: 4, 2: 8, 3: 3, 4: 12}"
            ]
          },
          "execution_count": 170,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "prob.best_routes_load"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FaeepKU7eMHy"
      },
      "source": [
        " ### 1. Algoritmo de busca global\n",
        "\n",
        "Dado o pseudo-código abaixo, implemente-o em C++ e compare (com um gráfico) seu tempo de execução em função de diferentes tamanhos de entrada. Note que ele NÃO ESTÁ COMPLETO!\n",
        "\n",
        "```cpp\n",
        "Função ResolverVRPComDemanda(Locais, Demanda, C):\n",
        "    // Locais: Lista de locais para entrega (excluindo o depósito)\n",
        "    // Demanda: Dicionário mapeando cada local à sua demanda\n",
        "    // C: Capacidade do veículo\n",
        "    \n",
        "    MelhorRota = NULL\n",
        "    MenorCusto = INFINITO\n",
        "\n",
        "    // Gera todas as combinações possíveis de rotas considerando a capacidade do veículo\n",
        "    Combinações = GerarTodasAsCombinações(Locais)\n",
        "    \n",
        "    Para cada combinação em Combinações faça:\n",
        "        Se VerificarCapacidade(combinação, Demanda, C) então:\n",
        "            CustoAtual = CalcularCusto(combinação)\n",
        "            Se CustoAtual < MenorCusto então:\n",
        "                MenorCusto = CustoAtual\n",
        "                MelhorRota = combinação\n",
        "                \n",
        "    Retornar MelhorRota, MenorCusto\n",
        "\n",
        "Função GerarTodasAsCombinações(Locais):\n",
        "    // Gera todas as permutações possíveis de locais e agrupa em rotas válidas conforme a capacidade\n",
        "    // Esta função é bastante complexa, pois precisa considerar todas as subdivisões possíveis dos locais em rotas que atendam à capacidade do veículo\n",
        "    // Retorna uma lista de combinações válidas\n",
        "    Retornar combinações\n",
        "\n",
        "Função VerificarCapacidade(Rota, Demanda, C):\n",
        "    // Verifica se a demanda total da rota não excede a capacidade do veículo\n",
        "    CargaTotal = 0\n",
        "    Para cada local em Rota faça:\n",
        "        CargaTotal += Demanda[local]\n",
        "    Se CargaTotal > C então:\n",
        "        Retornar Falso\n",
        "    Senão:\n",
        "        Retornar Verdadeiro\n",
        "\n",
        "Função CalcularCusto(Rota):\n",
        "    // Calcula o custo de uma rota com base na distância, tempo ou outro critério\n",
        "    // O custo pode depender de fatores como a distância total percorrida, o número de veículos necessários, entre outros\n",
        "    Retornar custo\n",
        "\n",
        "// Início do programa\n",
        "// Define os locais, suas demandas e a capacidade do veículo\n",
        "Locais = [...]\n",
        "Demanda = {...}\n",
        "Capacidade = C\n",
        "\n",
        "MelhorRota, MenorCusto = ResolverVRPComDemanda(Locais, Demanda, Capacidade)\n",
        "Exibir \"A melhor rota é:\", MelhorRota, \"com custo total de:\", MenorCusto\n",
        "```"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XIk4qF-6fHRz"
      },
      "source": [
        "### 2. Solução aproximada\n",
        "\n",
        "Para problemas complexos as heurísticas são ferramentas essenciais, pois oferecem soluções aproximadas em tempo razoável, especialmente quando o problema é grande demais para abordagens de força bruta ou métodos exatos. Heurísticas não garantem a melhor solução possível, mas frequentemente encontram soluções muito boas com um esforço computacional significativamente menor.\n",
        "\n",
        "Algumas das heurísticas e métodos meta-heurísticos mais comuns para o VRP incluem:\n",
        "\n",
        "  - _Heurística de Inserção Mais Próxima_: Começa com uma rota contendo apenas o depósito e, em seguida, iterativamente insere o cliente mais próximo em sua posição de menor custo até que todos os clientes sejam incluídos. Esta abordagem é simples e relativamente rápida, mas pode não encontrar a melhor solução possível.\n",
        "  - _Heurística de Clarke e Wright (Economias)_: Uma das heurísticas mais conhecidas para o VRP, que começa com cada cliente em sua própria rota e, em seguida, progressivamente mescla rotas que resultam nas maiores \"economias\", ou seja, reduções no custo total da rota. Essa abordagem tenta equilibrar o custo de visitar cada cliente com o custo de conectar rotas.\n",
        "  - _Algoritmos Genéticos_: Uma classe de métodos de busca e otimização baseados nos princípios de seleção natural e genética. Eles usam operações como seleção, cruzamento e mutação para evoluir uma população de soluções ao longo do tempo, em busca da melhor solução possível.\n",
        "\n",
        "Implemente uma das heurísticas citadas, ou elabore outra solução aproximada, que dê uma solução em tempo razoável para o problema. Aqui, além de implementar o algoritmo, é importante que você descreva brevemente sua estratégia de solução no relatório.\n",
        "\n",
        "Mesmo cortes mais simples do espaço de busca estão valendo, por exemplo, considerando que há um limite máximo de visitas em cada rota, podemos de cara cortar as combinações de cidades que ultrapassam esse limite. Podemos, ainda, estabelecer um limite mínimo, para evitar rotas pequenas.\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "BEnrOY1vgldz"
      },
      "outputs": [],
      "source": []
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "pkIDN06q05n0"
      },
      "outputs": [],
      "source": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hF8_McxIgkCT"
      },
      "source": [
        "### 3. Soluções paralelizadas\n",
        "\n",
        "Na abordagem de força bruta para a resolução do problema de otimização de rotas de veículos, a parte mais custosa computacionalmente é a geração e avaliação de todas as permutações possíveis das cidades (ou pontos de entrega).\n",
        "\n",
        "Esta é também a parte que oferece maior potencial para paralelização. Mas existem outras?\n",
        "\n",
        "Nesta etapa do projeto você deve realizar 2 implementações paralelas da sua solução, sendo:\n",
        "\n",
        "- 1 solução baseada em \"paralelização local\", ou seja, usar threads para extrair o máximo de proveito da máquina que rodará o programa;\n",
        "- 1 solução baseada em \"paralelização global\", ou seja, construir uma solução que paraleliza a execução em múltiplas máquinas de um cluster, acelerando ainda mais a execução. Note que seu programa de paralelização global deve também fazer uso de paralelização local. Em outras palavras, você particionará o problema e alocará cada parte em uma máquina; em cada máquina você usará os recursos presentes (cores) para paralelizar ainda mais!\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "hhH6fmmZsZu_"
      },
      "outputs": [],
      "source": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MeWSTHogsaDW"
      },
      "source": [
        "**_NOTA_**: Compare todas as suas soluções em termos de tempo de execução. Para a mesma entrada, execute-a com cada uma das 4 implementações e compare os tempos de execução."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "eQ0W-cj-saZZ"
      },
      "outputs": [],
      "source": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dkgjDSkDshlu"
      },
      "source": [
        "## Critérios de avaliação\n",
        "\n",
        "A correção do projeto levará em conta:\n",
        "\n",
        "+ [Até 1 pontos] **Organização geral**\n",
        "  - Organização do código fonte e/ou do notebook que centraliza seus códigos. Se a entrega for via jupyter notebook, ele deve conter células markdown que guiem a apreciação do trabalho. Caso seu código esteja organizado em arquivos \".cpp\", \".py\", etc, submeta também um relatório em PDF descrevendo seu trabalho;\n",
        "\n",
        "+ [Até 4 pontos] **Implementações**\n",
        "  - Sua entrega deve conter ao menos 3 implementações (uma para cada solução: exaustiva, OpenMP e MPI). Soluções extras nestas vertentes são encorajadas e serão valorizadas;\n",
        "  - A parte de MPI deve ser obrigatoriamente executada no cluster. Portanto, submeta também os arquivos de configuração dos executáveis em batch;\n",
        "  - Esperamos códigos seguindo as boas práticas de implementação e devidamente comentados;\n",
        "\n",
        "+ [Até 3 pontos] **Avaliação de resultados**\n",
        "  - Comparações das abordagens com tamanhos diferentes de grafos;\n",
        "  - Clareza na comunicação dos resultados. Ex: gráficos e/ou pequenos textos que descrevem os resultados obtidos;\n",
        "  - Justificativas: é esperado que a execução paralela seja mais rápida que a sequencial, assim como uma heurística seja mais rápida que a abordagem exaustiva. Caso seus resultados diferem do esperado, argumente potenciais causas;\n",
        "\n",
        "+ [Até 1 ponto] **Extras**\n",
        "  - A rubrica não cita o máximo de implementações a ser feita. Caso você opte por fazer algo além das 4 solicitadas, daremos até 1 ponto extra na nota do trabalho pelo esforço;\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ASag0Dj8swqY"
      },
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}