<h2>O que é um algoritmo?</h2>
Um algoritmo é uma especificação precisa e sem ambiguidades de uma sequência de passos computacionais que podem ser realizados mecanicamente[^1]. A partir disso, podemos pensar em uma função que recebe um valor ou um conjunto de valores de entrada e retorna um valor ou conjunto de valores em sua saída.
Um algoritmo pode ser correto e incorreto. Ele é correto quando, dados seus parâmetros de entrada, sua saída for correta e, portanto, resolve o problema computacional para qual foi desenvolvido. Um algoritmo incorreto, por sua vez, pode parar com uma saída incorreta ou mesmo não parar para algumas instâncias de entrada. Ainda assim, alguns algoritmos incorretos ainda podem ter aplicações úteis.
Podem haver diferentes algoritmos que resolvem um mesmo problema, alguns mais eficientes, isto é, mais velozes do que outros. Mas, nem todo problema possui uma solução eficiente. Tais problemas são conhecidos como <abbr title="Tempo polinomial não-determinístico">NP</abbr>-completos.
Problemas <abbr title="Tempo polinomial não-determinístico">NP</abbr>-completos são muito interessantes: mesmo que nenhum algoritmo eficiente tenha sido encontrado para esta classe de problemas, não se provou que que não é possível encontrar um algoritmo eficiente (da classe P, que pode ser resolvido em tempo polinomial) para tal problema. Além disso, se houver um algoritmo eficiente para resolver um problema NP-completo, significa que existe um algoritmo eficiente para todos os problemas <abbr title="tempo polinomial não-determinístico">NP</abbr>-completos.
<Alert title="P vs. NP">
P vs. NP é uma questão fundamental em ciência da computação, especificamente no campo da teoria da complexidade computacional. Ela diz respeito à relação entre duas classes de problemas. A classe P consiste em problemas de decisão (problemas com resposta sim ou não) que podem ser resolvidos rapidamente (em tempo polinomial) por um computador determinístico, o que significa que o tempo necessário para resolver o problema cresce a uma taxa gerenciável à medida que o tamanho da entrada aumenta. Por outro lado, a classe NP consiste em problemas de decisão para os quais, se uma solução for fornecida, ela pode ser verificada rapidamente (também em tempo polinomial) por um computador determinístico.

A questão crucial, &quot;P é igual a NP?&quot;, pergunta se todo problema cuja solução pode ser verificada rapidamente (NP) também pode ser resolvido rapidamente (P). Isso é profundo porque, se P fosse igual a NP, significaria que todos os problemas que podemos verificar rapidamente também podem ser resolvidos rapidamente. Isso tem implicações vastas para vários campos, incluindo criptografia, otimização e design de algoritmos.
</Alert>
<h2>Complexidade de algoritmos</h2>
Quando falamos de algoritmos, na maior parte do tempo estamos interessados na taxa de crescimento de tempo e espaço requeridos para resolver instâncias cada vez maiores de determinados problemas. Se estamos interessados no tempo que determinado algoritmo leva para executar sua função, estamos interessados um sua complexidade temporal. E o comportamento do limite da complexidade temporal do nosso algoritmo em relação ao aumento das instâncias do problema é chamado de complexidade assintótica temporal. E é esse complexidade assintótica que que determina o tamanho do problema que pode ser resolvido por algoritmos[^2].
Se um algoritmo leva um tempo <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">cn^2</annotation></semantics></math>cn2 para uma constante <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math>c para processar um entrada de tamanho <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n, dizemos que a complexidade do algoritmo é da ordem de <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">n^2</annotation></semantics></math>n2, ou, em notação Bachmann–Landau (também chamada de notação assintótica e notação Big O), o algoritmo tem a complexidade <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>O(n2).
Para termos uma melhor ideia do que isso significa em relação ao tempo de execução do nosso algoritmo, considere que uma unidade de tempo no computador em que executamos o nosso algoritmo é de 1 milissegundo. Agora, queremos saber qual o tamanho máximo da entrada que o nosso algoritmo pode processar dentro de um determinado limite de tempo (um segundo, um hora e um dia). Observe, na tabela abaixo, o quanto a complexidade do algoritmo interfere no tamanho máximo da entrada que ele pode tratar, dado o limite de tempo:
<table>
<thead>
<tr>
<th>Complexidade de tempo</th>
<th>1 segundo</th>
<th>1 minuto</th>
<th>1 hora</th>
</tr>
</thead>
<tbody><tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n</td>
<td>1000</td>
<td>60000</td>
<td>360000</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mn>2</mn></msub><mi>n</mi></mrow><annotation encoding="application/x-tex">n \log_2 n</annotation></semantics></math>nlog2​n</td>
<td>140</td>
<td>4895</td>
<td>204095</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">n^2</annotation></semantics></math>n2</td>
<td>31</td>
<td>244</td>
<td>1897</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mn>3</mn></msup></mrow><annotation encoding="application/x-tex">n^3</annotation></semantics></math>n3</td>
<td>10</td>
<td>39</td>
<td>153</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mi>n</mi></msup></mrow><annotation encoding="application/x-tex">2^n</annotation></semantics></math>2n</td>
<td>9</td>
<td>15</td>
<td>21</td>
</tr>
</tbody></table>
Ainda que possamos construir computadores mais rápidos, o aumento na velocidade de execução dos algoritmos menos eficientes não seria tão significativo, de modo que que devemos buscar sempre o algoritmo de melhor eficiência para tratar determinado problema.
[^1]: AHO, Alfred V.; ULLMAN, Jeffrey D. Foundations of Computer Science. Stanford, 1994.
[^2]: AHO, Alfred V.; HOPCROFT, John E.; ULLMAN, Jeffrey D. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

Introdução à algoritmos

O protocolo de internet é, como o próprio nome já diz, um protocolo que define como blocos de dados (chamados datagramas) serão transmitidos entre computadores na internet. Cada computador da rede possui, pelo menos um endereço com o qual é identificado na rede. Este endereço é chamado de endereço de IP.
<Alert title="Mas, o que é um protocolo?" mb="md" color="blue">De maneira sucinta, um protocolo é uma definição do formato e da ordem das mensagens trocadas entre duas ou mais entidades, que são, no nosso caso, computadores. Um protocolo define o que deve ser feito quando uma mensagem é enviada ou recebida, e também o que deve ser feito quando um evento ocorre.</Alert>
O protocolo de internet foi definido, pela primeira vez, no artigo &quot;A Protocol for Packet Network Intercommunication&quot; em maio de 1974, publicado pelo <a href="https://www.ieee.org/">IEEE</a>, escrito por Vinton Cerf e Robert Kahn.
O IP não requer uma conexão contínua entre os pontos de comunicação, ou seja, o computador que envia os dados não verifica se a mensagem foi recebida. Cada pacote trafegado na rede é tratado de maneira totalmente independente, sem relação com outros pacotes. Para verificar se os pacotes chegaram corretamente ao destino e rearranjá-los na ordem correta, utiliza-se o TCP (Transmission Control Protocol - Protocolo de Controle de Transmissão). Sua utilização é tão comum em conjunto com o IP, que nos referimos aos dois protocolos, ao mesmo tempo, como TCP/IP. É bom salientar the o TCP não é o único protocolo da internet.
<h2>Roteamento</h2>
Quando enviamos ou recebemos algum dado através da internet, este dado é dividido em pequenas partes chamadas de pacotes, que contém o endereço único do remetente e do destinatário (chamado endereço de IP). Estes pequenos pacotes são enviados a um gateway, que nada mais é do que um computador que conecta duas ou mais redes através de diferentes protocolos. Este gateway verifica se pode encontrar o endereço do destinatário em sua rede. Se não conseguir, encaminha o pacote para o gateway mais próximo, até que o endereço do destinatário seja encontrado (ou retorne um erro, caso o endereço esteja errado ou fora do ar).
Você pode ver o caminho que os pacotes traçam, entre os roteadores da rede, até o destino, com o comando <a href="https://www.ibm.com/docs/pt-br/power8?topic=commands-traceroute-command"><code>traceroute</code></a> - ou <a href="https://learn.microsoft.com/en-us/windows-server/administration/windows-commands/tracert"><code>tracert</code></a>, caso esteja no Windows ou ainda, usando o <code>traceroute</code> online do <a href="https://registro.br/tecnologia/ferramentas/traceroute/">Registro.br</a>:
<pre><code class="highlited-code-wrapper langbash"><div class="highlited-code" data-language="bash">traceroute google.com
traceroute to google.com (142.251.129.46), 64 hops max, 52 byte packets
 1 192.168.0.1 (192.168.0.1) 7.353 ms 3.096 ms 1.902 ms
 2 100.65.0.1 (100.65.0.1) 8.703 ms 5.352 ms 6.726 ms
 3 45.190.209.1 (45.190.209.1) 6.509 ms 2.820 ms 4.341 ms
 4 172.16.90.1 (172.16.90.1) 9.714 ms 5.157 ms 5.715 ms
 5 172.17.16.41 (172.17.16.41) 9.328 ms 5.390 ms 4.412 ms
 6 172.17.1.74 (172.17.1.74) 8.665 ms 7.749 ms 10.623 ms
 7 142.250.166.121 (142.250.166.121) 9.529 ms 5.825 ms 6.133 ms
 8 * * *
 9 142.251.61.70 (142.251.61.70) 6.626 ms
 172.253.69.202 (172.253.69.202) 5.531 ms
 172.253.73.190 (172.253.73.190) 7.071 ms
10 74.125.243.12 (74.125.243.12) 9.858 ms
 gru06s72-in-f14.1e100.net (142.251.129.46) 7.649 ms
 142.251.76.13 (142.251.76.13) 6.488 ms</div>
</code></pre>Como cada pacote é enviado de maneira independente, eles podem chegar ao destinatário através de gateways distintos, e em uma ordem diferente da que foram enviados. É trabalho de outro protocolo, o TCP, de reagrupar estes pacotes na ordem correta e verificar se os dados não foram corrompidos.
Outros protocolos comumente utilizados em conjunto com o IP são:
<ul>
<li>UDP (User Datagram Protocol): provê um processo de comunicação de baixa latência, largamente utilizado em buscas de DNS e VoIP (Voice Over IP - voz sobre IP);</li>
<li>HTTP (Hyper Text Transfer Protocol): especifica o protocolo de comunicação que habilita os navegadores a exibirem conteúdo;</li>
<li>FTP (File Transfer Protocol): especifica o protocolo de gerenciamento de arquivos em cliente conectados.</li>
</ul>
<h2>Camadas de protocolos</h2>
A internet é composta por uma série de protocolos que se comunicam entre si, e que são organizados em camadas. Cada camada é responsável por uma tarefa específica, e cada camada pode ser implementada de maneira diferente, desde que mantenha a compatibilidade com as camadas superiores e inferiores.
<figure>
 <pre>
Aplicação
Transporte
Rede
Enlace
Físico
 </pre>
 <figcaption>
 A pilha de cinco camadas de protocolos da Internet.
 </figcaption>
</figure>

Uma camada de protocolo pode ser implementada com software ou hardware ou uma combinação dos dois.
<h3>Camada de aplicação</h3>
A camada de aplicação é a camada mais próxima do usuário, fornecendo-lhe os mais diversos tipos de serviços, como e-mail, transferência de arquivos, chat, etc.
Os pacotes trafegados nessa camada são chamados de mensagens.
<h3>Camada de transporte</h3>
A camada de transporte fornece serviços de transporte da camada de aplicação entre diferentes pontos da aplicação. Dois protocolos são utilizados nesta camada: TCP e UDP. O TCP fornece um serviço de transmissão confiável, isto é, este protocolo garante que o destinatário está disponível na rede, divide a mensagens em pequenos pacotes para enviá-las, verifica se as mensagens não foram corrompidas no trajeto e as reconstrói no destino. O UDP fornece um serviço de transmissão não confiável, no sentido que não garante que o destinatário está disponível na rede, não divide a mensagem em pacotes, não verifica se as mensagens não foram corrompidas no trajeto e não as reconstrói no destino. Normalmente, o UDP é utilizado para serviços de streaming, como vídeo e áudio, onde a perda de alguns pacotes não é crítica. Os pacotes trafegados nesta camada são chamados de segmentos.
<h3>Camada de rede</h3>
A camada de rede fornece serviços de roteamento entre diferentes pontos de rede, de modo a movimentar os pacotes de um ponto a outro. Aqui, além do protocolo IP,
utilizam-se vários outros protocolos de roteamento. Os pacotes trafegados nesta camada são chamados de datagramas.
<h3>Camada de enlace</h3>
A camada de enlace fornece serviços de transmissão de dados entre dispositivos de rede conectados por um meio de transmissão. A camada de rede depende dos serviços
desta camada para mover os pacotes de um nó a outro da rede. Os pacotes trafegados nesta camada são chamados de frames.
<h3>Camada física</h3>
O trabalho desta camada consiste em moves os bits individuais dentro de um frame de um nó para o outro. Os protocolos utilizados nesta camada
dependem do meio de transmissão (fibra ótica, cabo coaxial, cabo de par trançado, etc.).
<hr>
Referências
<ul>
<li><a href="https://www.techtarget.com/searchunifiedcommunications/definition/Internet-Protocol">Internet Protocol (IP)</a>;</li>
<li><a href="https://www.rfc-editor.org/rfc/rfc791">RFC 791 - Internet Protocol</a>;</li>
<li><a href="https://www.rfc-editor.org/rfc/rfc3439">RFC 3439 - Some Internet Architectural Guidelines and Philosophy</a>;</li>
<li><a href="http://web.stanford.edu/class/msande91si/www-spr04/readings/week1/InternetWhitepaper.htm">How Does the Internet Work?</a>;</li>
<li><a href="https://www.rfc-editor.org/rfc/rfc1393">Traceroute Using an IP Option</a></li>
<li><a href="http://gaia.cs.umass.edu/kurose_ross/online_lectures.htm">Computer Networking: A Top-Down Approach (2020, J.F. Kurose, K.W. Ross, Pearson)</a>.</li>
</ul>

Douglas Moura

Douglas Moura

#Iniciantes

Introdução à algoritmos

O protocolo da internet (IP)