Donar $20 Donar $50 Donar $100 Donar mensualmente
 


Enviar respuesta 
 
Calificación:
  • 2 votos - 5 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
[Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
Autor Mensaje
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #1
[Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos Dudas y recomendaciones Matemática Discreta
Hola!

Me surgió esta duda:

Si me dan el recorrido el posorden de un árbol que no sea una operación algebraica, por ejemplo: d h k l i e b f j g c a. ¿Cómo lo reconstruyo? Si fuese una operación algebraica, es muy fácil reconstruirlo pensandolo como una calculadora en polaca inversa, pero esto me cagó.

El ejemplo es éste arbol:


Archivo(s) adjuntos Imagen(es)
   

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
(Este mensaje fue modificado por última vez en: 01-08-2010 16:40 por Lean.)
01-08-2010 16:39
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
gonnza Sin conexión
User Verde

*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 17.112
Agradecimientos dados: 763
Agradecimientos: 732 en 317 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #2
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
el recorrido en posorden si no recuerdo se basa en tener en cuenta esto:
"hijo izquierdo, hijo derecho, raiz". Es decir, nombras primero al hijo izquierdo, luego al derecho, y luego a la raiz.
EN tu ejemplo:

Tenes la raiz a, entonces buscas el hijo izquierdo "b", pero este a su vez tiene hijos, asique no lo podes nombrar.
Buscas su hijo izquierdo, y es "d" asique lo nombras. Siguiendo el algoritmo, viene el hijo derecho de "b", que es "e". Pero este tiene hijos; no lo podes nombrar, asique buscas su hijo derecho. Este es "h", asique lo nombras.
Por ahora tenes : d h
Buscas el hijo derecho de "e", siendo este "i", pero como tiene hijos, buscas el hijo izquierdo. Este es "k", lo nombras, y el hijo derecho es "l". Tambien lo nombras.
Como nombraste los 2 hijos, podes nombrar al padre, que es "i".
Hasta ahora tenes : D H K L I

Como nombraste los 2 hijos de "e" (el izquierdo h y el derecho i) podes nombrarlo. Entonces nombras a "e". Del mismo modo, nombraste los 2 hijos de "b", asique lo nombras.
Ahora tenes: D H K L I E B
A todo esto ya nombraste al "hijo izquierdo" de la raiz "a" (que resulto ser todo ese subarbol) asique ahora buscas el hijo derecho de "a"
Este pasa a ser C, pero "c" tiene hijos, asique primero debes nombrar su hijo izquierdo y luego el derecho.
Nombras asi a su hijo izquierdo "f" y luego su hijo derecho, pero este tambien tiene hijos ! "g" tiene hijos, asique debes nombrar a su hijo izquierdo y luego al derecho. Como hay un solo hijo, lo nombras. Nombras asi a "j" y luego a "g".
Ahora tenes: D H K L I E B F J G
como nombraste los 2 hijos de "c" lo podes nombrar. Asique nombras "c"
Ya tenes los 2 hijos (el izquierdo y derecho) de la raiz "a" asique la nombras.
Y te queda el recorrido: D H K L I E B F J G C A

creo que era asi =P
Una explicacion general seria asi:
La notacion consiste en nombrar al hijo izquierdo, hijo derecho, padre. Si uno de los hijos es raiz de un sub arbol, lo apartas (consideras solo ese subarbol) y aplicas nuevamente la tecnica "hijo izquierdo, hijo derecho, padre". Y hubiese un hijo que a su vez es raiz de un subarbol, seguis aplicando. Considera que no podes nombrar esas "raices" de esos "subarboles" hasta no haber nombrado sus hijos izquierdos y derechos.

Espero que te sirva thumbup3

[Imagen: v34BEFt.gif]
(Este mensaje fue modificado por última vez en: 01-08-2010 17:43 por gonnza.)
01-08-2010 17:37
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #3
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
Esta buena la generalización, pero la duda en realidad era cómo reconstruir el arbol a partir del recorrido

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
01-08-2010 17:48
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
gonnza Sin conexión
User Verde

*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 17.112
Agradecimientos dados: 763
Agradecimientos: 732 en 317 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #4
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
la puta, eso pasa por leer mal xD
dudo que tomen algo asi; necesitas algun dato mas como saber cuales son hijos y cuales no..
Porque si no no sabes donde "partir" para aplicar "este es hijo derecho, este izquierdo, este padre"
en una algebraica justamente es facil, porque sabes que los operadores son padres siempre (nunca hijos) y ahi aplicas para recuperar el arbol

[Imagen: v34BEFt.gif]
(Este mensaje fue modificado por última vez en: 01-08-2010 17:52 por gonnza.)
01-08-2010 17:48
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #5
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
Listo, esa es la respuesta uqe necesitaba, gracias!

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
01-08-2010 17:54
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Anirus Sin conexión
Super Moderador
Sin estado :)
*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.162
Agradecimientos dados: 77
Agradecimientos: 194 en 69 posts
Registro en: Nov 2009
Mensaje: #6
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
Me da la impresión que para ese tipo de ejercicios hay varias respuestas, ya que el que sea n-ario significa que n es la máxima cantidad de hijos que pueden alcanzar los elementos del árbol, en ningun momento te indica cuantos hijos debe tener cada elemento (ya que tampoco es regular), asi que hay muchos árboles que cumplan con la condición de no sobrepasar los n-hijos.
Mirando los finales no encontré ningun ejercicio como el que pusiste, todos son con operaciones. Lo más parecido que vi es el ejercicio 52 de la página 282 del libro, pero ahi te dice cuantos hijos debe tener cada letra.
(Este mensaje fue modificado por última vez en: 01-08-2010 18:01 por Anirus.)
01-08-2010 17:57
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #7
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
Claro, justamente, en esa página te dice cuántos hijos debe tener cada letra, entonces ya sabes cuáles son padres y cuales son hijos. Al igual que con las operaciones algebraicas, uno sabría cuáles son los padres y cuáles son los hijos (los padres son las operaciones, los hijos los números).

Está interesante, nunca se tomó, aunque lo podrían tomar porque no es nada del otro mundo si te dan la cantidad de hijos.

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
01-08-2010 18:01
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Anirus Sin conexión
Super Moderador
Sin estado :)
*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.162
Agradecimientos dados: 77
Agradecimientos: 194 en 69 posts
Registro en: Nov 2009
Mensaje: #8
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
Y si no te la dan, es dibujo libre =P
01-08-2010 18:03
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #9
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
Claro.. porque hay muchos (infinitos? no creo) arboles posibles con ese recorrido.

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
01-08-2010 18:04
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
gonnza Sin conexión
User Verde

*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 17.112
Agradecimientos dados: 763
Agradecimientos: 732 en 317 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #10
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
claro jaja
a lo sumo lo unico con certeza que podes sacar es que "a" va a ser la raiz =P

[Imagen: v34BEFt.gif]
01-08-2010 18:05
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #11
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
sisi jaja.. esta interesante el tema, si algún dia me interesan los grafos (nunca) estaría bueno probar cuántos posibles arboles binarios con ese recorrido habrían

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
01-08-2010 18:07
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
gonnza Sin conexión
User Verde

*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 17.112
Agradecimientos dados: 763
Agradecimientos: 732 en 317 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #12
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
jaja, yo AME discreta jajajaja =P
si la profesora no se cambiaba de turno, iba de cabeza como ayudante jajajaa xD

[Imagen: v34BEFt.gif]
01-08-2010 18:08
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #13
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
Bueno, aprovecho el thread para poner otra cosa.

En mayo pusieron este ejercicio:

[Imagen: captureang.jpg]

Es obvio que sí, que es posible recorrerlo. El tema es que en la respuesta justifica diciendo sólo se puede recorrer en simétrico si es binario. ¿Porqué? No se puede usar para árboles ternarios por ejemplo? (no se, imaginemonos la suma con 3 hijos, sumarías los 3 hijos entre sí).

saludos

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
01-08-2010 19:59
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
gonnza Sin conexión
User Verde

*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 17.112
Agradecimientos dados: 763
Agradecimientos: 732 en 317 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #14
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
no, porque seria una operacion en la calculadora no realizable =D
vos lo pensas en tu cabeza, con lo que sabes de suma "claro, sumo los 2 primeros, y el resultado con el 3ro" pero si representas eso en un arbol te da algo asi como este dibujo:
[Imagen: dlasyzfa9qpcqahklodh.jpg]
que es binario

Eso seria para tu ejemplo particular; para el del ejercicio, son operaciones binarias (el +, - * y /) osea que usan 2 operandos; osea que el arbol no puede tener 3 hijos porque implica 3 operandos, lo cual es imposible para esos operadores
aclaro qeu conteste todo sin recordar cual era el orden posterior y el simetrico jaja
no confundas el que haya 3 numeros para sumar con la cantidad de operandos: el + es operacion binaria, osea que requiere 2 operandos.
Si sumas 3 numeros haces 2 veces la operacion, y su representacion sera como el dibujo q te hice =P
no podes hacer 3+ 5 + 7 (osea, sumar los 3 numeros de una), sino que haces (3+5)+7 (primero 3+5 y luego el resutlado +7)
Como la suma es asociativa a izquierda, por eso al hacer 3+5+7 es lo mismo que (3+5)+7 (tambiene s lo mismo si pongo 3+(5+7) porque es conmutativa =P, pero bueno, suponete que no fuese conmutativa)
mm nose si respondi tu pregunta jajaj
se me mezcla AM2 con discreta =P

[Imagen: v34BEFt.gif]
(Este mensaje fue modificado por última vez en: 01-08-2010 20:11 por gonnza.)
01-08-2010 20:07
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Lean Sin conexión
Secretario de la SAE
Sin estado :(
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 404
Agradecimientos dados: 0
Agradecimientos: 11 en 5 posts
Registro en: Mar 2010
Mensaje: #15
RE: [Matemática discreta] Recorrido en postorden de árboles n-arios no reg no algebraicos
Si, me olvidé que son operaciones binarias, esa es la justificación de porqué no se puede recorrer algo con 3 hijos en usual.

62.9 requests/sec - 371.1 kB/second - 5.9 kB/request
78 requests currently being processed, 0 idle workers
01-08-2010 20:12
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)



    This forum uses Lukasz Tkacz MyBB addons.