Cormen РPrograma̤̣o Din̢mica

Cormen РPrograma̤̣o Din̢mica РLinha de Montagem

Uma DSL que fornece os dados para o algoritmo de linha de montagem (o objetivo maior foi praticar ruby e implementação de DSL’s)

Cormen – Programação Dinâmica
(mude de doc para rtf ou rb qdo for abrir)

[]’s,
Vinicius AC

Cormen Exercício 2.3.7 – V. 2

Busca soma num conjunto ( Cormen Exercício 2.3.7 (Outra implementação)

Implementação que usa dois índices para percorrer o arranjo ordenado. Um índice percorre o arranho em ordem crescente e o outro em ordem decrescente. Os pares com a soma desejada vão sendo armazenados até que os índices se cruzem.

Caso existam pares adequados, estes serão retornados num array de pares(array com dois elementos(uma imitação de tupla(vou dormir ))). Fornece também a quantidade de pares encontrados.

Cormen Exercício 2.3.7 – Verifica se existem elementos cuja soma é S (v.2) (mude de doc para .rb ou .rtf qdo for abrir)

Cormen Exercício 2.3.7

Busca soma num conjunto ( Cormen Exercício 2.3.7

Só por causa de Maurício, vou copiar o enunciado. O coitado deve tá sofrendo muito no IMPA com blibliotecas gigantes e firefox’s velhos (a propósito, não me odeie por isto, mas…. parabéns pelo dez, fiquei feliz em saber). Bom…. chega de papo furado.

2.3-7 РDescreva um algoritmo de tempo O (n lg n) que, dado um conjunto S de n inteiros e outro inteiro x, determine se existem ou ṇo dois elementos em S cuja soma seja exatamente x.

Versão corrigida com a ajuda dos comentários de Mauricio (comento logo abaixo)

Respostas aos comentários de Mauricio

(Parte 1 do comentário) Vc está certo. Foi pq antes eu tava colocando um s2 = GeraS2(s1).sort! porque o merge precisa de dois arrays ordenados. Aí tirei o .sort! e deixei o (n log n). Realmente, deveria ordenar no GeraS2, como estou fazendo agora.

(Parte 2 do comentário) Vc tb está certo. (droga)
Teoricamente não precisa de nenhum uniq, já que as entradas devem ser conjuntos de números, não arranjos.

(Parte 3 do comentário)
“3) A descrição do título faz ele parecer … números. É isso?” >> Essa o enunciado respondeu.
(continuando … )
Vou *tentar* implementar do jeito que vc sugeriu(opção dois ponteiros). Realmente é bem mais simples. Vou fazer de forma que verifique num *arranjo*, se existe a soma procurada, quantas vezes ela ocorre e através de que elementos. (vai ser o próximo POST do blog)

(Parte 4 do comentário)
Interessante mesmo, porque toda vez que coloquei antes índices de arrays fora da faixa nos loops deu erro. Também tava com muito sono, quando fiz.
O resultado de uma análise sem tanto sono é:
arr[x] == nil , para todo x > arr.length-1 (olha eu aprendendo ruby )
então a última comparação tava dando sempre false, por isso não prejudicava o resultado. Mas vou consertar assim mesmo, claro.
Eu verifico length >= 2 pra saber se tem dois ou mais elementos repetidos. Se sim, existe a soma procurada.

Cormen Exercício 2.3.7 – Verifica se existe ao menos dois elementos cuja soma é S (mude de doc para rtf ou rb qdo for abrir)

Cormen Exercício 2.3.2

Merge-Sort ( Cormen Exercício 2.3.2)

Cormen Exercício 2.2.2

Selection-Sort ( Cormen Exercício 2.2.2 )

Cormen Merge-Sort

Merge-Sort com Sentinelas ( Cormen )

Cormen Exercício 2.3.1

Merge-Sort (Cormen Exercício 2.3.1)

P

Cormen Exercício 2.1.2

Insertion-Sort (Cormen Exercício 2.1.2)

KMP Moficado

Modifique o algoritmo KMP para encontrar o maior prefixo de B que casa cm uma subcadeia de A. Em outras palavras, você não precisa casar todo B, mas o maior prefixo possível. 

Algoritmo KMP_modificado(A,B)

Entrada: A, B -> cadeias a serem analisadas

Saída: a posição onde começa a seqüência

Inicio

ini := 0;     i;=1;    j := 1;   casamax := 1;           casamaxpos := 1;    

tamB := Tamanho(B);    tamA := Tamanho(A);

proximo = next(B, tamB);

Enquanto (i < tamA) e (ini = 0) faça

Inicio

      If A[i] = B[j]

then

i := i + 1;

j := j + 1;

if (j > casamax)

then

      casamax := j;

      casamaxpos := i;

endIf

else

j := proximo[j] + 1;

if (j = 0)  then  i:= i+1;   j:= j+1;

            endIf

            if (j = tamB + 1) then ini := I – tamB;

endEnquanto

if (ini <> i – tamB) then ini := casamaxpos – casamax;

RetornoDoAlgoritmo := ini;

fimAlgoritmo

 

Algoritmo next(B,m)

entrada: B->string de tamanho m

saída: array next

Inicio

next(1) := -1;

next(2) := 0;

Para i :=3 até m faça

      j:= next(i-1)+1;

      Enquanto Bi-1 <> Bj e j>0 faça

           j := next(j) + 1;

           next(i) :=    j;

      endEnquanto

endPara

RetornoDoAlgoritmo := next;

end

Leila, Prova, Questão4, 2004/1(eu acho)

UFS – PAA – Leila
Questão 4 da 3º prova de 2004 (/1, eu acho).

Compute o produto da matrizes A e B dadas a seguir segundo:

(a) o algoritmo de Winograd

(b) o algoritmo de Strassen

 

A =
[ 2 , 4 ]
[ 6 , 8 ]

B =
[1 , 0]
[3 , 2]

 

(a)

Winograd

A1 = a11*a12 = 8 B1 = b11*b21 = 3

A2 = a21*a22 = 48 B2 = b12*b22 = 0

 

C l,c = ((1º da linha l )+(nº da coluna c))*( (nº da linha l )+(1º da coluna c)) – Al – Bc

 

C 1,1 = (2+3)(4+1) - 8 – 3

C 1,2 = (2+2)(4+0) - 8 – 0 

C 2,1 = (6+3)(8+1) – 48 – 3 

C 2,2 = (6+2)(8+0) – 48 – 0

C =
[14 ,   8]
[30 , 16]

 

 

 

 

 

(b)

Strassen

[ 2 , 4, 0, 0 ] [1]

[ 6 , 8, 0, 0 ] [3]

[ 0 , 0, 2 , 4 ] [0]

[ 0 , 0, 6 , 8 ] [2]

…………..

affffffffffffffffffffffffffffff…. é trabalho demais escrever A,B,C,D,E,F,G, alfa, beta, gama, teta, …

cê é doido!

Pra que decorar as regras de Strassen? Pedir isso é muita falta de bom senso.