Download Representación de una lista

Inteligencia artificial
Lista y árboles
Pierre Sergei Zuppa Azúa
Keyword
Listas
Es una estructura que se usa para
representar un conocimiento
jerárquico compuesto por elementos
del mismo tipo.
Representación de una lista
Tipo de lista
Descripción
Sencilla
Es donde los enlaces sólo te permiten accesar al nodo que
sigue y hacia delante.
Doble
En ésta, nos permite accesar al nodo siguiente, pero si se
requiere puedes regresar.
Circular
En ésta, al momento de llegar a lo que debería de ser este
valor NULL, en realidad tenemos que el área que le
corresponde el acceso al siguiente nodo, nos manda a lo que
es el inicio de la lista.
Representación
Operaciones sobre listas
•
•
•
•
•
Insertar un elemento en una lista.
Buscar un elemento en una lista.
Borrar un elemento de una lista.
Recorrer los elementos de una lista.
Borrar todos los elementos de una
lista.
Árbol
Es una estructura de datos, que puede
definirse de forma recursiva como:
– Una estructura vacía.
– Un elemento o clave de información
(nodo), más un número finito de
estructuras tipo árbol.
Es, por tanto,
secuencial.
una
estructura
no
Nomenclatura de un árbol
Nodos: son los elementos o vértices del árbol.
Nodo raíz: es el primer elemento de un árbol.
No tiene ascendiente o antecesor.
Nodo padre: es el nodo que tiene por lo menos un
hijo.
Hijo: descendiente de un nodo.
Nodo hoja o nodo terminal: nodo que no tiene ningún
descendiente.
Rama: relación que conecta un padre con un hijo.
Nomenclatura de un árbol
Ascendiente o antecesor: nodo padre de un nodo o padre de
algún nodo ancestro.
Descendientes o sucesor: hijo de un nodo o el hijo de otro
descendiente de ese nodo.
Altura o profundidad: es el máximo de los niveles de los
nodos de un árbol.
Sub-árbol: conjunto de descendientes de un nodo por una
de las ramas.
Nivel de un nodo: distancia desde la raíz. Ésta está en el
nivel cero.
Grado de un nodo: número de hijos que tiene un nodo.
Ejemplo: d tiene grado cero.
Características de un árbol
• Es una forma gráfica y analítica
de representar todos los eventos
que pueden surgir a partir de
una decisión asumida en cierto
momento.
• Nos ayuda a tomar la decisión
más acertada desde un punto de
vista
probabilístico,
ante
diferentes soluciones posibles.
• Permite desplegar visualmente
un problema y organizar el
trabajo de cálculos que deben
realizarse.
Terminología
Nodo: indica que en este punto del
proceso ocurre un evento aleatorio. Está
representado por un circulo:
Rama: muestra los distintos caminos que
se pueden emprender cuando se toma
una decisión o cuando ocurre algún
evento aleatorio. Se representa con una
línea:
a
Elaboración del diagrama de árbol
a)Identificar todas las decisiones (y
sus alternativas) a realizar y el
orden (la secuencia) en que se
deben realizar.
b)Identificar los eventos probables que
pueden ocurrir como resultado de la
toma de decisión.
c)Desarrollar el diagrama de árbol que
muestre las secuencias de las
decisiones y los eventos probables.
Ventajas y desventajas de un árbol
Ventajas
• Hace más explícito e intuitivo
el
proceso
de
toma
de
decisiones.
• Se captan mejor los diferentes
cursos de acción.
• Se puede observar la magnitud
de las inversiones que cada
curso de acción origina.
Desventajas
• La secuencia que sigue la
solución
del
problema,
depende de la probabilidad en
que acurran los eventos.
• Cuando el árbol es muy
complejo, es tedioso y tardado
hacer la estimación y la
evaluación de los eventos.
• Se requiere una serie de datos
que algunas veces pueden ser
difíciles de conseguir.
Listas en Prolog
Lista vacía: []
Lista compuesta: [<término>+f| <lista>g]
<términos>: sucesión de los primeros elementos de la lista
<lista>: lista con los elementos restantes
[a, b, c] = [a, b, c| []] = [a, b| [c]] = [a|[b, c]]
Algunas relaciones que trabajan con listas:
append(L1, L2, L3) :- La lista L3 única con la concatenación de las listas L1 y L2
member(E, L) :- E única con alguno de los elementos de la lista L
reverse(L1, L2) :- La inversa de la lista L1 unica con la lista L2
Listas en Prolog
Si se tiene la lista [a, b, c,
d], la a es la cabeza y la
cola es la lista [b, c, d].
Una lista cuya cabeza es A y
cola es B, se anota como *A |
B+
El predicado
primer_elemento(X, [X|_]),
tiene éxito si X es el primer
elemento de la lista.
Trabajar con listas en Prolog
Proporciona los dos términos constructores de la lista: [ ], la constante lista vaca; y
[X|R] el operador (función infija) concatenar por la cabeza, donde R debe ser una lista
a su vez. Para una definición más formal de lista consultar el predicado is list/1.
También se proporcionan predicados para el manejo de listas. is list(+Term): cierto
si Term es una lista.
• length(?List, ?Int): Int es el número de elementos de la lista List.
• sort(+List, -Sorted): Sorted es la lista ordenada de los elementos de
List sin duplicados.
• append(?List1, ?List2, ?List3): List3 es la concatenación de List1 y
List2.
• member(?Elem, ?List): Elem es elemento de List.
• nextto(?X, ?Y, ?List): Y está después de X en la lista List.
• delete(+List1, ?Elem, ?List2): List2 es la eliminación de todos los
elementos que unifican.
• simultaneamente.con Elem de List1.
• nth0(?Index, ?List, ?Elem): Elem es el Index -ésimo elemento de List,
comenzando por el 0.
• reverse(+List1, -List2): List2 es List1 pero con el orden de los
elementos cambiado.
Terminar un árbol en Prolog
listing.
dios_egipcio(amon).
dios_egipcio(anubis).
dios_egipcio(apis).
dios_egipcio(ra).
La orden findall realiza todo el árbol.
Longitud
Listas en Prolog
% Si queremos hallar la longitud de una lista.
% La longitud de una lista vacía es 0.
% La longitud de cualquier lista es la longitud de la cola + 1.
Búsqueda
listas en Prolog
% Si queremos determinar
si un elemento pertenece a
una lista.
% El elemento pertenece a
la lista si coincide con la
cabeza de la lista.
% El elemento pertenece a
la lista si se encuentra en la
cola de la lista.
Eliminación
listas en Prolog
% Si queremos eliminar un
elemento de la lista.
% Si X es la cabeza de la lista,
la cola T es la lista sin X.
% Si X no es la cabeza de la
lista, conservamos la cabeza
de la lista.
% como parte de la respuesta
y continuamos eliminando X de
la cola T.
Concatenar
listas en Prolog
% Si queremos concatenar dos
listas.
% Concatenar una lista vacía
con L es L.
% Concatenar X|L1 con L2 es
poner el primer
% elemento de la primera lista
(X) más la
% concatenación del resto de la
lista (L1) con L2.
Concatenación
La concatenación o conduplicación
es, en general, el acto de unir o
enlazar cosas.
MANIPULACIÓN DE SUBLISTAS
EN PROLOG
Hay (al menos) otras dos formas de cómo definir sublista, ejemplo: usando las
relaciones prefijo y sufijo. Todas estas definiciones son equivalentes. Sin
embargo, el procedimiento sublista3 es probablemente lo más cercano al estilo
de programación tradicional (no declarativo), ya que usa la técnica conocida
como "floating window".
sublista(S,L):-agregar(_,S,P),agregar(P,_,L).
sublista2(S,L):-prefijo(P,L), sufijo(S,P).
sublista3(S,L) :- prefijo(S,L).
sublista3(S,[_|T]) :- sublista3(S,T).
Ordenamiento
La ordenación o clasificación
de datos consiste en la
disposición de los mismos de
acuerdo con algún valor o
característica.
Por ejemplo, cada elemento
de una agenda telefónica
tiene un campo nombre, un
campo dirección y un campo
número telefónico.
Tipos de ordenamiento
Interno
Directos
–
–
–
Burbuja.
Selección.
Inserción.
Logarítmicos
–
–
–
–
–
Shell.
Merge.
Heap.
Quick.
Radix.
Externos
• Mezcla directa.
• Mezcla equilibrada.
Método algorítmico
Se caracteriza por tomar en
consideración todas las
alternativas o posibilidades
relativas a un problema.
Aunque los algoritmos
garanticen un nº finito de
posibilidades, en muchas
ocasiones, ese número es
elevadísimo y exige emplear
mucho tiempo. Como ventaja,
cabe destacar que si el
problema está bien planteado,
acaba encontrándose la
solución exacta. Es propio de
los ordenadores.
Métodos heurísticos
Son
estrategias
generales
de
resolución y reglas de decisión
utilizadas por los solucionadores de
problemas,
basadas
en
la
experiencia previa con problemas
similares. Estas estrategias indican
las vías o posibles enfoques a seguir
para alcanzar una solución.
Es decir, es un procedimiento para
resolver
un
problema
de
optimización bien definido mediante
una aproximación intuitiva, en la
que la estructura del problema se
utiliza de forma inteligente para
obtener una buena solución.
Tipos de conocimiento para resolver problemas
Conocimiento declarativo: por ejemplo, saber
que un kilómetro tiene mil metros.
Conocimiento
lingüístico:
palabras, frases, oraciones.
conocimiento
de
Conocimiento semántico: dominio del área
relevante al problema, por ejemplo, saber que si
Álvaro tiene 5 pesos más que Javier, esto implica
que Javier tiene menos pesos que Álvaro.
Conocimiento esquemático: conocimiento de los
tipos de problema.
Conocimiento procedimental: conocimiento del o
de los algoritmos necesarios para resolver el
problema.
Conocimiento estratégico: conocimiento de los
tipos de conocimiento y de los procedimientos
heurísticos.
Pasos del método heurístico
1. Analizar
y
definir
el
problema.
2. Definir la estrategia a seguir
para llegar a la solución y
llevarla a la práctica.
3. Definir
alternativas
de
solución al problema y
seleccionar la mejor.
4. Comprobar la pertinencia de
la solución seleccionada.
Características del planteamiento de los problemas
de razonamiento
• Expresar con claridad, de manera
que se entienda lo que se está
diciendo.
• Incluir todos los datos necesarios
para su resolución.
• Expresar
claramente
las
condiciones en las cuales se da la
situación o el hecho que se va a
resolver.
• Expresar las reglas con las cuales
se debe buscar la solución.
• Terminar con una pregunta en la
que se indique el tipo de solución
que se espera.
29
Frase
“Los programadores hablan sobre
desarrollo los fines de semana,
vacaciones y en las comidas, no por falta
de imaginación, sino porque su
imaginación revela mundos que otros no
pueden ver”
Larry O'Brien y Bruce Eckelen
"Thinking in C#"