SSTORE5 - Loja de acessórios de celulares e informática

 Tenho uma dica para você que gosta de tecnologia. Acessórios de computadores, notebooks, celulares e tablets com frete grátis para toda Salvador, garantia e preço baixo. Se você acessar a loja, diga que viu a propaganda no meu blog e ganhe mais 10% de desconto acumulativo ao desconto de inauguração da loja. São até 40% de desconto. Tem HD, SSD, SDCARD, Pendrives, Carregadores de celulares, cabos usb, fones de ouvido bluetooth e com fio, kits de teclado e mouse etc. Click no link aqui em baixo e conheça.

https://sstore5.lojavirtualnuvem.com.br

Emprego das PDU's corretas no dia-a-dia do engenheiro de redes

No dia-a-dia de profissional de redes trabalhamos com tipos de "pacotes" de diferentes protocolos, que atuam em diferentes camadas do modelo de referência OSI da ISO. Por exemplo, quando trabalhamos com protocolo ethernet, estamos trabalhando com um protocolo da camada 2 do modelo OSI, e assim, chamamos de frame ethernet. Cada camada por onde os dados trafegam na rede possui uma unidade própria chamada de PDU ou protocol data unit que genericamente dizemos ser um pacote. Porém, no ambiente de tratamento de falhas ou de desenho de redes, cada PDU possui o seu próprio nome, a saber:

#camada física: bit

#camada de enlace: frame ou quadro

#camada de rede: pacote

 #camada de transporte: datagrama ou segmento 

#camadas superiores: dados ou mensagens 

Portanto, um browser requisita ou envia dados por ser inerente a camada de aplicação, um aplicativo de e-mail ou chat, envia e recebe mensagens pelo mesmo motivo. Temos frames ethernet ou frame relay ou em outro protocolo link layer. Já os protocolos de roteamento e roteados como OSPF e IP enviam pacotes, enquanto que TCP e UDP tem segmentos ou datagramas. 

Agora você pode usar a PDU correta ao tratar incidentes de rede, e de quebra domina mais um skill para o CCNA.

Até a próxima!

Divisão e Conquista e Algorítimo Merge-Sort parte 2

Vimos que o número total de elementos a serem intercalados neste passo é r-p+1 e que este também é o tempo levado pelo procedimento MERGE. agora o algorítimo sugerido a seguir faz este procedimento de organizar de forma crescente os subconjuntos de cartas que já estão ordenadas.

MERGE(A, p, q, r)

1    n1= q - p + 1

2    n2= r - q 

3    sejam L[1..n1 + 1] e R[1.. n2 + 1] novos arranjos

4    for i = 1 to n1

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

6    for j = 1 to n2

7        R[j] = A[q + j]

8    L[n1 + 1] = z

9    R[n2 + 1] = z

10    i = 1

11    j = 1

12     for     k = p to r

13        if L[i] <= R[j]

14            then  A[k] = L[i]

15                    i = i + 1

16            else A[k] = R[j]

17                    j = j + 1

    

O algorítimo acima funciona assim: linhas 1 e 2 calculam as extensões dos subarranjos a serem organizados. A linha 3 cria mais dois Arranjos que recebem os L e R. Na linha 4 e 5 copia o Arranjo A[ p .. q]  em L[1 .. n1] e as 6 e 7 faz o mesmo para A[ q + 1 .. r] em  R[1 .. n2]. As linhas 8 e 9 possuem uma nuance interessante. Aplica-se aqui uma carta de nome z que é um marcador indicando uma carta de valor infinito que já não precisa ser ordenada. Estas cartas são colocadas nas extremidades dos arranjos L e R. De 10 a 17 os r - p + 1 passos básicos são executados. 

No próximo post vamos fazer a análise da corretude deste algorítimo e depois implementar o MERGE-SORT de fato, introduzindo a recursividade. Até lá!

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

Divisão e Conquista e algorítimo Merge-Sort part1

Até aqui, no algorítimo Isertion-Sort usamos uma técnica de projeto de algorítimo chamada incremental, e provamos sua funcionalidade usando a técnica de invariante do laço. Para o algorítimo Merge-Sort usaremos uma técnica chamada de Divisão e Conquista. Esta técnica usa no geral, a recursividade, um método em que o algorítimo chama a si mesmo durante a solução de um problema. A divisão e conquista consiste em dividir o problema em instancias cada vez menores a ponto de ele se tornar bem simples. Após isso, o algorítimo recorre recursivamente a si mesmo pela solução destes pequenos problemas resultantes. No fim, ele combina as mini-soluções em uma solução grande para o problema original. A seguir, veja os três passos para a aplicação da técnica da divisão e conquista:

Dividir: o problema é dividido em subproblemas cada vez menores até se tornarem simples de resolver

Conquista: O algorítimo resolve o problema recursivamente, ou se o problema é pequeno o bastante, resolve direto.

Combinar: as soluções dos subproblemas são combinadas para formar a solução do problema original.

O algorítimo Merge-Sort segue à risca este paradigma. Ele Divide a sequencia a ser ordenada de n elementos em subsequências de n/2 cada, executando o passo da DIVISÃO. Depois segue ordenando as subsequencias recursivamente utilizando a intercalação, o que configura o passo da CONQUISTA. Por último o passo da COMBINAÇÃO que é conseguida intercalando as subsequências de forma a gerar a resposta ao problema original.

A recursividade deixa de existir quando a sequencia tiver cumprimento 1(ou seja, ordenada por si só). O passo mais importante no Merge-Sort é o da combinação onde recorremos ao processo MERGE(A,p,q,r) em que A é um arranjo e p,q,r são índices de enumeração onde p=<q<r partindo da premissa que A[p...q] e A[q+1...r] já estão ordenados. À partir disso, forma-se um único sub-arranjo ordenado que ficará no lugar de A[p...r]. Este procedimento leva um tempo teta(n) onde n= r-p+1. 

No próximo post, o algoritmo MERGE. Até lá!

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

Ordem de crescimento

Você percebeu que algumas abordagens abstrativas foram usadas para simplificar a análise do Insertio-Sort. Os custos reais foram substituídos por custos abstratos definidos pelas constantes ci. Depois até mesmo estas constantes foram desprezadas porque elas nos davam mais detalhes do que, de fato, precisávamos. Então expressamos o tempo de pior caso como an²+bn+c para constantes a, b e c que dependem dos custos abstratos ci. Porém, ao ignorarmos inclusive este custo abstrato, facilitamos ainda mais a estimativa T(n). Mais uma abstração simplificadora é feita aqui, e definimos assim o que chamamos de taxa de crescimento ou ordem de crescimento. Neste caso, consideramos apenas o primeiro termo an² ou seja, o termo mais significativo, pois os termos de ordem mais baixa são insignificantes para grandes valores. Ignoramos a constante inicial pois não pesa nos cálculos de crescimento. Com toda esta abstração da matemática envolvida, afirmamos que a ordem de crescimento do algorítimo de ordenação por inserção, tem um tempo de execução teta de n ao quadrado e se representa ø(n²). 

ps.: entenda esse simbolo como a letra teta. Meu notebook não tem. 

No futuro, vamos estudar essa notação com mais cuidado. No memento, queremos apenas entender que para comparar a eficiência de um algorítimo com outro, usamos o tempo de execução como parâmetro. Assim, se um algorítimo tem o tempo de execução na ordem ø(n²) e o outro ø(n), então, o segundo algorítimo tem melhor eficiência. Essa ideia será usada quando terminarmos de analisar a complexidade do algorítimo Merge-Sort para definirmos o mais eficiente na tarefa de ordenação.

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

 

Complexidade de pior caso Insertion-Sort - Parte2

O pior caso resulta de quando o arranjo A está totalmente invertido ou em ordem decrescente. Neste caso a linha 4 será executada tanto quanto for o comprimento do arranjo A menos um, ou seja, j vezes porque neste caso, A[i] > k levando a execução das linhas 5 e 6 j - 1 vezes. Disto resulta o somatório de j=2 até n(j) = [n(n + 1)/2]-1 para a linha 4 e j=2 até n(j-1) = n(n-1)/2 para as linhas 5 e 6. Substituindo na nossa fórmula encontrada no post passado e ignorando a constante que é a mesma e sabemos agora não alterará o que queremos saber, que é complexidade da função, temos:

T(n)= n + (n-1) + (n-1) + [n(n+1)/2]-1 + [n(n-1)/2] + [n(n-1)/2 + (n-1) = 3n^2 + 7/2n - 4 

que é uma função quadrática ou do segundo grau. Assim, a complexidade de pior caso deste algorítimo é de quadrática. A complexidade do caso médio não nos interessa a esta análise e normalmente não é utilizada. No próximo post, evoluímos desta fórmula para uma notação mais simples, a ordem de crescimento da função.

1-            for j = 2 to A.comprimento                                    c1  n

2-                k = A[ j ]                                                             c2 (n-1)

3-                i = j - 1                                                                c3 (n-1)

4-                while i > 0 e A[ i ]> k                                         c4 [n(n+1)/2]-1

5-                        A[ i + 1] = A[ i ]                                         c5 [n(n-1)/2]

6-                         i = i - 1                                                       c6 [n(n-1)/2]

7-                A[ i + 1 ] = k                                                       c7 (n-1)

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

 

Ordenação Insertion-Sort parte 2 - complexidade de melhor caso

Medimos a complexidade na unidade tempo de execução na maioria das vezes. Em algorítimos como o Insertion-Sort esse tempo de dois fatores: O tamanho da entrada e a ordenação desta entrada. Para ordenar 3 números exige-se um tempo menor do que para ordenar 100. Da mesma maneira, a ordenação destes mesmos números em ordem decrescente leva mais tempo do que se apenas uma parte estiver desordenada. Na análise a seguir, admitamos a constante c em cada linha do pseudo-código como constante de tempo em função da quantidade n de vezes em que esta linha é executada. Daí somamos as resultantes para determinar o tempo de execução. Esta fórmula encontrada será usada para definir uma notação simples para comparar a eficiência de um algorítimo com outro:

linha do pseudo-code                                 constante c de Tempo e número n de vezes da execução

1-            for j = 2 to A.comprimento                                    c1  n

2-                k = A[ j ]                                                             c2 (n-1)

3-                i = j - 1                                                                c3 (n-1)

4-                while i > 0 e A[ i ]> k                                         c4 [n(n+1)/2]-1

5-                        A[ i + 1] = A[ i ]                                         c5 [n(n-1)/2]

6-                         i = i - 1                                                       c6 [n(n-1)/2]

7-                A[ i + 1 ] = k                                                       c7 (n-1)

Associamos ao c o número da linha por razões didáticas. A soma destas linhas é igual ao tempo de execução do algorítimo T(n). 

T(n)= c1n + c2(n-1) + c3(n-1) + c4[n(n+1)/2]-1 + c5[n(n-1)/2] + c6[n(n-1)/2 + c7(n-1) 

percebe-se que o tempo de ordenação fica amarrado ao tamanho da entrada n e eventualmente à sua ordenação. Observe que para uma entrada hipoteticamente totalmente ordenada resulta no que chamamos de melhor caso. Vemos que na linha 4 o valor A[i] será <= k e neste caso nunca entraremos no laço, por consequência, esta linha será executada (n-1) vezes e as linhas 5 e 6 não serão executadas. Portanto, T(n)= c1 + c2(n-1) + c3(n-1) + c4(n-1) + c7(n-1)=

= (c1 + c2 + c3 + c4 + c7)n - (c2 + c3 + c4 + c7)  o que nada mais é que uma função de primeiro grau an+b para duas constantes a e b. Em resumo, o tempo de execução do melhor caso é T(n)=an+b.

A seguir, próximo post, análise do pior caso

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.