Auxilio - Alg. Paralelos
16 views
Skip to first unread message
JULIO MASA KANAZAWA
Jul 14, 2010, 12:13:51 PM7/14/10
to 9no_seme...@googlegroups.com
Por si acaso nadie tiene la demostración del funcionamiento de una red de ordenación utilizando el teorema 0-1???
por favor estuve viendo en el libro pero no se entiende, alguien hizo en clase????
por favor estuve viendo en el libro pero no se entiende, alguien hizo en clase????
Sebastian Fernandez
Jul 14, 2010, 12:21:38 PM7/14/10
to 9no_seme...@googlegroups.com
revisa un poco este link
http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/09_sortnet_notes.pdf
pagina 3
"The Zero-One Principle"
de por ahi te sirve :)
saludos!
--
Sebastian Fernandez
http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/09_sortnet_notes.pdf
pagina 3
"The Zero-One Principle"
de por ahi te sirve :)
saludos!
El 14 de julio de 2010 12:13, JULIO MASA KANAZAWA <kanaz...@gmail.com> escribió:
Por si acaso nadie tiene la demostración del funcionamiento de una red de ordenación utilizando el teorema 0-1???
por favor estuve viendo en el libro pero no se entiende, alguien hizo en clase????
Sebastian Fernandez
Sebastian Fernandez
Jul 14, 2010, 12:31:45 PM7/14/10
to 9no_seme...@googlegroups.com
La idea es simple,
1- tenes una secuencia de N numeros (no tiene porque ser bitonica ni nada)
2- armas una red de ordenamiento que te ordene esa secuencia
3- lo que queres es "probar que tu red de ordenamiento ordena cualquier secuencia de N numeros"
para esto debieas probar entonces N! (N fatorial) posibles combinaciones de los mismos N numeros
4- lo que el teorema te dice es: "si tu red puede ordenar secuencias binarias de N bits, pude ordenar cualquier secuencia de N bits"
con lo cual solo tendrias que probar 2^N combinaciones posibles
5- y eso es lo q haces :)
EJ: si N = 3 tendriamos q probar 2^3 combinaciones y probas si tu red de ordenamiento ordena estas secuencias:
000
001
010
011
100
101
110
111
la secuencia binaria queda ordenada, si te sale 001 cuando la entrada fue 100
por ejemplo
espero no haber confundido mas, jeje
saludos!
--
Sebastian Fernandez
1- tenes una secuencia de N numeros (no tiene porque ser bitonica ni nada)
2- armas una red de ordenamiento que te ordene esa secuencia
3- lo que queres es "probar que tu red de ordenamiento ordena cualquier secuencia de N numeros"
para esto debieas probar entonces N! (N fatorial) posibles combinaciones de los mismos N numeros
4- lo que el teorema te dice es: "si tu red puede ordenar secuencias binarias de N bits, pude ordenar cualquier secuencia de N bits"
con lo cual solo tendrias que probar 2^N combinaciones posibles
5- y eso es lo q haces :)
EJ: si N = 3 tendriamos q probar 2^3 combinaciones y probas si tu red de ordenamiento ordena estas secuencias:
000
001
010
011
100
101
110
111
la secuencia binaria queda ordenada, si te sale 001 cuando la entrada fue 100
por ejemplo
espero no haber confundido mas, jeje
saludos!
El 14 de julio de 2010 12:13, JULIO MASA KANAZAWA <kanaz...@gmail.com> escribió:
Por si acaso nadie tiene la demostración del funcionamiento de una red de ordenación utilizando el teorema 0-1???
por favor estuve viendo en el libro pero no se entiende, alguien hizo en clase????
--
Sebastian Fernandez
Sebastian Fernandez
Jul 14, 2010, 12:35:25 PM7/14/10
to 9no_seme...@googlegroups.com
correcciones
--
Sebastian Fernandez
El 14 de julio de 2010 12:31, Sebastian Fernandez <sebafer...@gmail.com> escribió:
La idea es simple,
1- tenes una secuencia de N numeros (no tiene porque ser bitonica ni nada)
2- armas una red de ordenamiento que te ordene esa secuencia, de forma descendente, por ejemplo
3- lo que queres es "probar que tu red de ordenamiento ordena cualquier secuencia de N numeros"
para esto debieas probar entonces N! (N fatorial) posibles combinaciones de los mismos N numeros
4- lo que el teorema te dice es: "si tu red puede ordenar secuencias binarias de N bits, pude ordenar cualquier secuencia de N numeros
con lo cual solo tendrias que probar 2^N combinaciones posibles
5- y eso es lo q haces :)
EJ: si N = 3 tendriamos q probar 2^3 combinaciones y probas si tu red de ordenamiento ordena estas secuencias:
000
001
010
011
100
101
110
111
la secuencia binaria queda ordenada, si te sale 001 cuando la entrada fue 100
por ejemplo
espero no haber confundido mas, jeje
saludos!
El 14 de julio de 2010 12:13, JULIO MASA KANAZAWA <kanaz...@gmail.com> escribió:
Por si acaso nadie tiene la demostración del funcionamiento de una red de ordenación utilizando el teorema 0-1???por favor estuve viendo en el libro pero no se entiende, alguien hizo en clase????
--
Sebastian Fernandez
--
Sebastian Fernandez
JULIO MASA KANAZAWA
Jul 14, 2010, 1:02:20 PM7/14/10
to 9no_seme...@googlegroups.com
ahhhh ya, esa parte de probar todas las posibilidades lo que no sabia :D
en el teorema hace una reducción a absurdo utilizando n como tamaño de red,
despues de unos garabatos te dice:"de esta forma queda demostrado" :S
Gracias sebas sos lo +
en el teorema hace una reducción a absurdo utilizando n como tamaño de red,
despues de unos garabatos te dice:"de esta forma queda demostrado" :S
Gracias sebas sos lo +
Reply all
Reply to author
Forward
0 new messages