Algorítimo de ordenação Insertion-Sort

Seguindo o assunto da análise de complexidade de algorítimos, vamos começar analisando um problema clássico que é o de ordenar números naturais de um determinado arranjo de entrada em um arranjo semelhante, entretanto, ordenado de forma crescente. Existem várias abordagens clássicas que solucionam esse problema, mas, precisamos aqui de apenas duas para poder analisar as suas complexidades e estabelecer o "melhor" neste caso.  Inicialmente vamos ver o algorítimo que faz isso por inserção. Ele se chama Insertion-Sort. O problema a ser resolvido é: dado um arranjo A[ a1, a2, a3 ... an ] organizar o arranjo A de forma que A[a1 < a2  < a3 < .... < an]. Segue o pseudo-código de um dos algorítimos que se propõem a realizar esta tarefa:

1-            for j = 2 to A.comprimento

2-                k = A[ j ]

3-                i = j - 1

4-                while i > 0 e A[ i ]> k

5-                        A[ i + 1] = A[ i ]

6-                         i = i - 1

7-                A[ i + 1 ] = k

Este algorítimo começa com o índice j assumindo o valor 2 inicialmente, uma vez que a primeira posição no array já está ordenada. A variável k guarda o valor da posição que está sendo ordenada. O valor do índice i é empurrado uma posição de cada vez para a direita desde que ele seja maior que 0 e seu valor no arranjo maior que a varável k o que implica ser maior que j já que nesta altura da execução k = j. 

fig.:           i  j 

           1,2,3,4,5

      A [5|4|7|9|2]

A corretude (funcionamento correto) deste algorítimo pode ser comprovada aplicando uma técnica semelhante a indução matemática chamada de invariante de laço (loop invariant) com a qual demonstramos o funcionamento do algorítimo. Os passos da invariante de laço são três:

1- Inicialização: Onde a propriedade é verdadeira antes da primeira iteração

2- Manutenção: Se é verdadeiro antes da primeira iteração, será verdadeiro antes da próxima iteração

3- Término: Quando o loop acaba, a invariante nos fornece o resultado do loop, uma propriedade útil.

Observe no algorítimo que a primeira propriedade está comprovada pois se j = 1, o arranjo 1 até j está ordenado pois só tem um componente que é ele mesmo. A manutenção também é verdade por hipótese, uma vez que é verdade antes da primeira iteração. Agora, executando j a partir do índice 2 mostramos que o loop funciona quando ele retorna um valor útil indicando o término com sucesso. A invariante de laço é usada para provar algorítimos iterativos, porém, quando tratamos de algorítimos recursivos, como o próximo que veremos, o merge-Sort, usamos de fato, a indução matemática para mostrar que a função recursiva funciona. No próximo post, continuamos a análise verificando a complexidade do mesmo.

Algorítimos, Cormen, et al, 2012 3ed. capítulo 2.

O que é análise de complexidade de um algorítimo?

Propomos um algorítimo com a finalidade de resolver problemas do mundo real. Porém, não é raro haver várias propostas de algorítimos para resolver o mesmo problema. E aí neste caso, qual o melhor algorítimo? Então buscamos mensurar a quantidade de recursos que um algorítimo precisa para funcionar. Recursos de processamento, memória e às vezes, largura de banda são os que primeiro nos vêm à mente. No entanto, quando analisamos um algorítimo é muito importante analisa-lo levando em conta o tempo de computação. No modelo de computação genérico temos instruções pré-definidas como instruções de soma, subtração, divisão, multiplicação, desvio condicional, carregamento, cópia e muitas outras. Cada instrução dessa leva um tempo constante para ser realizada. Mas, há algumas tarefas que precisam ser construídas, como por exemplo a ordenação de números naturais. Para isso precisamos construir um algorítimo que realize a tarefa com as operações que a máquina já contempla. Dessa forma, vários modos de realizar a mesma tarefa surgem, e analisar a complexidade de cada solução se torna necessário para eleger a mais aplicável aos recursos disponíveis. No próximo post trarei um problema de ordenação e uma solução para ele. A partir daí, iremos analisar esta proposta e determinar a sua complexidade. Depois vamos verificar outra proposta, com uma abordagem diferente, analisar sua complexidade, e inferir qual o mais eficiente. Inicialmente, o faremos de uma forma generalista, e depois usando ferramentas luxuosas de medida de complexidade, tratando o algorítimo como um modelo matemático de solução de problemas.

Algorítimos, Cormen, et al, 2012 3ed. capítulo 2.  

Redes Centradas na Informação - Uma nova abordagem para a internet

A pilha de protocolos TCP/IP é uma das maiores invenções da humanidade. Ela é o principal pilar sustentador da internet, ou seja, a internet do modo como conhecemos hoje só é possível por causa destes protocolos. Com sua capacidade indiscutivelmente incrível de rotear pacotes entre redes atribuída ao IP, seus protocolos de transporte que satisfazem tanto aplicações que exigem confirmação, como as que não possuem esta exigência, este protocolo atende bravamente demandas importantes de dados, vídeo e voz, mesmo sendo projetado numa época em que algumas dessas demandas não existiam ou tinham uma magnitude imensamente menor. Por outro lado, estas mesmas demandas crescentes, vem clamando por ajustes cada vez mais exaustivos para essa pilha de protocolos idosa. Além da escassez de endereços cuidada paliativamente pelo NAT, a dificuldade de mobilidade, necessidade de sistemas de conversão e resolução, esquema de segurança frágil, detre outros, trazem à tona a necessidade de se pensar em substituir esta arquitetura.

O paradigma ICN, Information Centric Network, principalmente, em sua implementação mais conhecida a NDN, named-data network é uma das abordagens mais promissoras. Saiba mais em https://named-data.net

Identificando a Classe do endereço IP pelo primeiro octeto

As faixas de endereços IPv4 são divididas em classes. A classe do endereço ajudou muito a seccionalizar o uso destes endereços. Claro que hoje em dia esse conceito não assume a importância que assumia antigamente, e provavelmente, a importância das classe A, B e C não detém tanta relevância. Porém, as classes D e E ainda identificam ranges de endereço de uso especial ainda muito aplicáveis e de grande relevância. Abaixo uma tabela com os ranges em decimal e suas classes:

Classe    Range de Endereços                         

A           0.0.0.1 - 126.255.255.255

B           128.0.0.0 - 191.255.255.255

C           192.0.0.0 - 223.255.255.255

D           224.0.0.0 - 234.255.255.255   multicast

E            240.0.0.0 - 255.255.255.254  reservado para testes IETF  

Uma forma rápida de identificar estes ranges é considerando estes números em binário. Existe uma regra chamada regra do primeiro octeto com a qual podemos identificar qual a classe do endereço facilmente:

Na classe A o primeiro bit é o 0

Na classe B os primeiros dois bits são 10

Na classe C os primeiros três bits são 110

Na classe D os primeiros quatro bits são 1110

Na classe E os primeiros cinco bits são 11110

Como o NAT direciona pacotes para o host correto na rede interna?

O protocolo TCP/IP é inquestionavelmente a pilha de protocolos mais usada no mundo. Essa maravilhosa invenção tornou possível a internet do modo como a conhecemos. De fato, escalonável, confiável e robusto este vovô parece imbatível ao passar dos anos. Porém, ele precisou de alguns remendos em sua trajetória. Devido aos 32 bits de endereçamento, ele é limitado no seu número de dispositivos endereçáveis. Muitas ações foram adotadas para poder retardar a exaustão completa do número de endereços. A separação de endereços públicos e privados foi uma delas. E é sobre isso que de que se trata o NAT. Network Address Translate é um artifício para que muitas máquinas em uma LAN usando endereços privados possam acessar a internet através de poucos ou até mesmo um único endereço público de WAN. No modo mais tradicional, um único endereço publico fornecido dinamicamente pela operadora pode carregar solicitações de vários hosts de uma rede privada. Isso é chamado de NAT overload ou Port Address Translate. Desse modo, por exemplo, uma rede privada com 14 hosts em um range 192.168.0.0/28 pode acessar a internet saindo por um endereço público apenas, digamos 200.2.2.1. Mas, daí surge uma questão: se todos os hosts estão acessando a internet pelo mesmo IP privado, como o roteador com NAT sabe de quem é determinado pacote de resposta? A solução está nas portas. Não é apenas a camada de transporte que usa portas. Além das portas típicas UDP/TCP, temos as portas lógicas do IP. Ou seja, quando um pacote sai para a internet através de um roteador NAT, ele registra a porta pela qual o dado será encaminhado como resposta, e daí, o nome Port Address Translate. Veja a tabela a seguir: 

R1# show ip nat translations
Pro Inside global           Inside local            Outside local         Outside global

udp 200.2.2.1:53427  192.168.0.6:53427      74.200.84.4:53        74.200.84.4:53

udp 200.2.2.1:53427  192.168.0.6:53427      195.170.0.1:53        195.170.0.1:53

tcp 200.2.2.1:53638   192.168.0.6:53638      64.233.189.99:80    64.233.189.99:80

tcp 200.2.2.1:57585   192.168.0.7:57585      69.65.106.48:110    69.65.106.48:110

tcp 200.2.2.1:57586   192.168.0.7:57586      69.65.106.48:110    69.65.106.48:110

Na exibição do comando acima vemos o host 192.168.0.6 usar a porta 53638 para acessar um serviço na internet através do IP público 200.2.2.1 que é o endereço de WAN do roteador onde está aplicado a NAT overload. Na mesma rede privada o host 192.168.0.7 usa a porta 57585 para acessar pelo mesmo IP público outro serviço na internet. Quando o pacote retorna, o host de destino é identificado à partir desta porta, assim, um único endereço válido na internet é usado por vários hosts não válidos para tráfego.

Dominando o inglês do CCNA 2.

Seguem mais algumas palavras que compõem o vocabulário majoritário dos exames CCNA. 5 minutos.
advertise	propagar
afford	proporciona
affords	oferece
against	contra
agreement	concordar, de acordo
also	tambem
althoug	embora
amounts	muitos
appears	aparece
arrives	chega, alcança
behavior	comportamento
better	melhor que
borrow	empresta
bound	compelir
broader	amplo
carry	carrega
comes	vem
convey	transmitir
cope	lidar
copper	cobre
covers	cobrir
descouraged	desencorajado
duty	dever
each	cada
ensure	garantir
environment	ambiente
fee	taxa
few	pouco
gather	recolher
greatly	grandemente
however	contudo
improve	melhorar
incur	provável
intented	pretendido
issues	questão, problema
kept	guardado
least	menos
led	conduzido
matter	não importa
means	meios
might	pode
often	frequente
overall	geralmente
paid	pago
procedural	processo
reclaim	recuperar
relies	confiável
relinquishes	renunciar
several	muitos, vários
streamlined	simplificado
taken	ocupado
thus	portanto
treatment	tratamento
undergo	submeter
wasted	desperdício
were	foi, era
whose	cujo

Dominando o inglês do CCNA

O exame de certificação CCNA é uma prova considerada difícil tecnicamente porque envolve muitas questões teóricas. Na verdade, ser reprovado em uma primeira tentativa é muito comum. Para muitos no entanto, o conhecimento técnico não é o único obstáculo. Como a prova atualmente não existe em português - isso mesmo! Já tivemos exames CCNA em português, mas, o português das provas mais atrapalhavam do que ajudavam, então, os candidatos acabavam optando por fazer em inglês mesmo, isto, quando não faziam em português e se davam mal. Fato é que saber inglês é ferramenta necessária para passar no exame. Se você tem dificuldade com inglês, mas, pelo menos tem aquele famoso basicão de pronomes, artigos e verbo To be, boa notícia! Você pode passar no exame mesmo assim. Porque eu tenho tanta certeza disso? Porque eu também tenho dificuldades com o idioma, mas, passei no CCNA em inglês. Dica importante: estude em português e em inglês. Estude exemplos de questões em inglês e em português. Depois de um tempo, estude só em inglês. Primeiro vamos entender que não é preciso uma tradução literal para sacar o âmago da questão que você está resolvendo. Para isso, vou passar nos próximos posts uma gama de palavras e expressões mais encontradas na literatura do exame, ou seja, um vocabulário de inglês técnico para o CCNA. Dividirei em postagens para seguir com a filosofia de 5 minutos, obedecendo o lema CISCO de pouco+pouco+pouco=muito. Também, iremos analisar algumas questões para você entender qual é a dica. 

Obs.: 1- não irei colocar o vocabulário em ordem alfabética porque dá trabalho - risos, e brincadeiras à parte não importa para o nosso objetivo. 2- não discutirei regras gramaticais (nem teria como), estas são dicas práticas de entendimento. 3- Colocarei as ideias no contexto do CCNA. 4- Não preciso dizer que não sou professor de inglês, longe disso, apenas coloco aqui uma técnica útil na compreensão das questões do EXAME. 5- O vocabulário que estou colocando aqui é a íntegra das minhas anotações no material de estudo.

But (mas), However (no entanto, contudo), Otherwise (senão), Although (embora), Unless ( a não ser que), Instead (em vez ), Against (contra), Rather (antes, em vez), Otherwise (de outra forma), On the other hand ( por outro lado), Among (entre uma coisa e outra): todas estas palavras, na maioria, conjunções adversativas, indicam um pensamento contraposto, um argumento adverso.  

And so on ( por aí vai), Beyond (além), Thus (assim), Therefore (portanto), Such (tais), Whose (cujo), So (então): estas são palavras explicativas e conclusivas, ajudam a endossar o pensamento.

Whath/Which (o que/qual), How (como), When(Quando), While(enquanto). Normalmente as questões se inicial com alguma destas palavras. Fica a dica!

That (aquele), This (isto), Them(eles), There (há)

Improve (melhorar), Increase (almentar), Decrease (diminuir)Lower (mais baixo), Slower (mais lento), Faster (mais rápido), Issue (questão, problema), Either (ideia de opção), Whether | if (condicional), Behind (atrás), Belong (ideia de pertencer), Become (ideia de se tornar), Behavior (comportamento), Approach (Abordagem), Statement (sentença ou texto), Do (fazer, auxilia verbos em perguntas), Make (fazer), Perform | Play (fazer, executar), Can (pode), Want (Quer). Perceba que estas palavras irão aparecer muito nas questões.

Agora vamos aos exemplos:

How can you manually configure a switch so that it is selected as the root Switch? 

Como voce pode configurar um switch manualmente como ROOT Switch? - É uma questão de spanning-tree. Observe que você não precisa traduzir tudo porque os termos "configure, manually e Root switch" são intuitivos. Algumas palavras em inglês chamadas de cognatos tem o mesmo sentido em português, outras nem vale a pena traduzir, porque já fazem parte do nosso leque de T.I como switch por exemplo. 

A. increase the priority number (aumenta o valor do "priority number") 

B. lower the port priority number (baixa o "priority number" da porta)

C. lower the priority number (baixa o "priority number" )

D. increase the port priority number (aumenta o "priority number" da porta)

Observe que "priority number" nem precisa traduzir, porque os livros em português irão trazer este termo, e você provavelmente já chama assim. 

Answer: C aqui você deduz o que é answer (resposta)

Percebeu como é fácil? Próximo post trago mais dicas e mais vocabulário.