P1 Flashcards
(90 cards)
1
Q
Test de Turing
A
Un juez se situa en una habitación con una persona y una máquina. Manteniendo una conversación con ambas debe determinar cuál es la máquina y cuál la persona
2
Q
Primer programa capaz de pasar el test de Touring
A
Eliza
3
Q
Cuál es la diferencia entre la IA fuerte y la IA débil
A
La IA fuerte entiende realmente,mientras que la IA débil simula entender
4
Q
¿Qué es un estado en un espacio de búsqueda?
A
Es la descripción del estado real del mundo en el que se encuentra el agente de búsqueda.
5
Q
¿Qué es el estado inicial?
A
Es el estado en el que comienza el agente de búsqueda.
6
Q
¿Qué es el estado objetivo?
A
Es el estado alcanzado en el que se detiene la búsqueda y se presenta la solución.
7
Q
¿Qué es el espacio de estados?
A
Es el conjunto de todos los estados posibles.
8
Q
¿Qué es una acción en el contexto de búsqueda?
A
Es una operación que genera una transición entre un estado y otro.
9
Q
¿Qué es una solución en un problema de búsqueda?
A
Es el camino desde el estado inicial hasta el estado objetivo.
10
Q
¿Qué es la función de coste?
A
Asigna un coste a cada acción; es necesaria si se quiere una solución de coste óptimo.
11
Q
¿Cuándo es un algoritmo de búsqueda completo?
A
Cuando encuentra una solución para todo problema que tiene solución.
12
Q
¿Cuándo es un algoritmo de búsqueda óptimo?
A
Cuando encuentra siempre la solución de menor coste.
13
Q
¿Qué representa b?
A
Factor de ramificación constante
14
Q
¿Qué representa b(x)?
A
Factor de ramificación no constante
15
Q
¿Qué representa d?
A
Profundidad
16
Q
¿Qué representa n?
A
Cantidad de estados
17
Q
n=\sum_{i=0}^{d}b_i
A
Cómo se obtiene la cantidad de estados de un árbol
18
Q
¿Qué es BFS?
A
Es la búsqueda en anchura,que explora todos los nodos en un nivel antes de pasar al siguiente.
19
Q
¿Qué es DFS?
A
Es la búsqueda en profundidad,que explora un camino hasta el final antes de retroceder y explorar otras ramas.
20
Q
Tiempo y memoria de BFS
A
Tiempo exponencial y memoria exponencial
21
Q
Tiempo y memoria de DFS
A
Tiempo exponencial y memoria lineal
22
Q
DFS no es aplicable sí ___
A
Tenemos ciclos en el grafo de búsqueda
23
Q
Factor de ramificación efectivo b_e
A
b_e= {total de acciones posibles (sin contar estado final)}/{cantidad de acciones}
24
Q
¿Cuándo usamos DFS iterativo en lugar de solo DFS?
A
Cuando existen ciclos en el grafo de búsqueda
25
¿Qué es un problema de satisfacción de restricciones (CSP)?
Es un problema donde se busca una asignación de valores a un conjunto de variables que satisface un conjunto de restricciones.
26
¿Cómo se define un CSP?
Con la terna (V,D,R),donde V son las variables,D son los dominios y R son las restricciones.
27
¿Cómo se representa una variable en un grafo de CSP?
Con un nodo
28
¿Cómo se representa una restricción en un grafo de CSP?
Con una arista
29
¿Qué es una restricción unaria?
Es una restricción que afecta solo a una variable.
30
¿Qué es una restricción binaria?
Es una restricción que involucra a dos variables.
31
¿Qué es el algoritmo de backtracking progresivo?
Es un algoritmo que genera asignaciones parciales y verifica si cumplen las restricciones hasta encontrar una solución completa.
32
Procedimiento de BFS
1. Visita un nodo
2. Genera todos sus hijos
3. Comprueba si es la solución
4. Si el nodo es la solución, se termina el algoritmo
5. Si no es la solución se va al siguiente (primero todos los nodos de un nivel antes de ir al siguiente)
33
Procedimiento DFS
1. Visita un nodo
2. Si el nodo es el estado final termina
3. Sino, genera todos sus descendientes y repite el proceso para el primero
4. Si ya no hay más descendientes, repite el proceso para todos los hermanos hoja
34
Cómo explora los nodos el backtracking progresivo
En profundidad
35
Anverso
Reverso
36
¿Qué es el algoritmo de búsqueda del primero mejor?
Es un algoritmo de búsqueda heurística que utiliza una función de evaluación para seleccionar el siguiente nodo a explorar en función de cuál parece más prometedor, basándose solo en la heurística (h(n)). No garantiza el camino óptimo.
37
¿Qué función de evaluación utiliza el primero mejor?
f(n) = h(n), donde h(n) es la heurística, una estimación del costo desde el nodo actual hasta el objetivo.
38
¿Cuál es la principal desventaja del algoritmo primero mejor?
Puede no encontrar el camino óptimo, ya que se guía solo por la heurística, ignorando el costo acumulado del camino recorrido (g(n)).
39
¿Qué es el algoritmo A*?
Es un algoritmo de búsqueda heurística que utiliza tanto el costo acumulado del camino (g(n)) como la heurística (h(n)) para encontrar el camino óptimo.
40
¿Qué función de evaluación utiliza el algoritmo A*?
f(n) = g(n) + h(n), donde g(n) es el costo desde el nodo inicial hasta el nodo actual, y h(n) es la heurística, estimación del costo restante hasta el objetivo.
41
¿Qué garantiza que A* encuentre el camino óptimo?
Si la heurística es admisible (nunca sobreestima el costo real) y consistente, A* garantiza encontrar el camino más corto.
42
¿Qué es una heurística?
Es una función que estima el costo de alcanzar el objetivo desde el estado actual. En algoritmos de búsqueda, se usa para guiar la exploración hacia la meta.
43
¿Qué es una heurística admisible?
Es una heurística que nunca sobreestima el costo real de alcanzar el objetivo, es decir, siempre es menor o igual al costo real.
44
¿Qué significa que una heurística sea consistente?
Una heurística es consistente si, para cualquier nodo n y cualquier sucesor n' generado por una acción, se cumple que h(n) <= costo(n, n') + h(n'). Esto asegura que A* siga un camino óptimo.
45
¿Qué es el algoritmo Minimax?
Es un algoritmo de toma de decisiones para juegos de adversarios que busca maximizar la ganancia de un jugador mientras minimiza la del otro, explorando todas las jugadas posibles.
46
¿Cuál es el objetivo del algoritmo Minimax?
El objetivo es que el jugador maximizador tome la mejor decisión posible, suponiendo que el jugador minimizador también juega de manera óptima.
47
¿Qué representan los nodos en el árbol de Minimax?
Los nodos representan los estados del juego en un punto dado, y las hojas se valoran con una función de utilidad.
48
¿Cómo decide el jugador maximizador en el algoritmo Minimax?
El jugador maximizador elige la jugada que maximiza su ganancia, evaluando los valores de los nodos hijos.
49
¿Cómo decide el jugador minimizador en el algoritmo Minimax?
El jugador minimizador elige la jugada que minimiza la ganancia del jugador maximizador, seleccionando el valor mínimo entre los nodos hijos.
50
¿Qué es la poda alfa-beta?
Es una optimización del algoritmo Minimax que reduce la cantidad de nodos evaluados, podando ramas que no afectarán la decisión final.
51
¿Qué es el valor alfa en la poda alfa-beta?
Es el valor máximo que el jugador maximizador puede garantizarse hasta ese punto.
52
¿Qué es el valor beta en la poda alfa-beta?
Es el valor mínimo que el jugador minimizador puede garantizarse hasta ese punto.
53
¿Cuándo ocurre la poda en el algoritmo alfa-beta?
Ocurre cuando se determina que una rama del árbol no influirá en la decisión final, permitiendo omitir su evaluación.
54
¿Cómo optimiza la poda alfa-beta al algoritmo Minimax?
Al podar ramas innecesarias, reduce la cantidad de nodos evaluados, haciendo más eficiente la búsqueda sin cambiar el resultado final.
55
Un problema es observable
Cuando en todo momento se sabe el estado del agente.
56
Un problema es discreto
Cuando la cantidad de acciones y estados son finitos. El problema se presenta en pasos separados.
57
Un problema es determinista
Cuando dado un estado inicial y una serie de acciones, el estado final es siempre el mismo
58
Trabajo realizado por BFS
`N(bef, d)=({bef^d+1}-1)/(bef-1)`
59
¿Qué es la búsqueda local en optimización?
Es una técnica utilizada para encontrar una solución óptima mediante la evaluación de soluciones vecinas cercanas hasta que no se observe una mejora significativa.
60
¿Cuál es el objetivo de la búsqueda local?
Optimizar una solución inicial mediante la exploración de su vecindad en el espacio de soluciones para mejorar el resultado.
61
¿Qué es la optimización?
Es el proceso de encontrar la mejor solución o el máximo rendimiento posible en un conjunto de opciones dadas.
62
¿Qué significa vecindad en el contexto de la búsqueda local?
La vecindad se refiere a las soluciones cercanas en el espacio de búsqueda que pueden alcanzarse mediante pequeños cambios en la solución actual.
63
¿Qué es la ascensión de colinas?
Es una técnica de búsqueda local en la cual se mueve hacia soluciones vecinas que mejoran el valor de la función objetivo hasta llegar a un máximo local.
64
¿Cuál es la principal limitación de la ascensión de colinas?
Puede quedar atrapada en máximos locales, lo que impide alcanzar la solución global óptima.
65
¿Qué tipo de problemas son ideales para la ascensión de colinas?
Problemas en los que la solución óptima se puede alcanzar con una serie de mejoras locales sucesivas.
66
¿Cómo se evita quedar atrapado en máximos locales en la ascensión de colinas?
Utilizando técnicas como el recocido simulado o el uso de múltiples reinicios aleatorios para intentar encontrar mejores soluciones globales.
67
¿Qué es el recocido simulado?
Es un método de optimización inspirado en el proceso de enfriamiento de metales, donde se permite que el sistema explore soluciones peores en las primeras etapas para evitar quedar atrapado en óptimos locales.
68
¿En qué se basa el recocido simulado?
Se basa en un proceso de enfriamiento que disminuye la probabilidad de aceptar soluciones peores a medida que avanza el tiempo, dirigiendo la búsqueda hacia soluciones óptimas.
69
¿Qué rol tiene la temperatura en el recocido simulado?
Controla la probabilidad de aceptar soluciones peores; a mayor temperatura, hay una mayor probabilidad de aceptar soluciones subóptimas, disminuyendo gradualmente.
70
¿Cuál es la función objetivo en el recocido simulado?
Es la función que mide la calidad de las soluciones y guía el proceso de optimización hacia una solución óptima.
71
¿Cómo se reduce la temperatura en el recocido simulado?
A través de un programa de enfriamiento, donde la temperatura disminuye gradualmente en cada iteración, lo que reduce la probabilidad de aceptar soluciones peores.
72
¿Cuáles son las aplicaciones del recocido simulado?
Optimización en problemas de gran escala como el diseño de circuitos, planificación de rutas y resolución de problemas combinatorios complejos.
73
¿Cómo se diferencia la ascensión de colinas del recocido simulado?
La ascensión de colinas solo acepta mejoras en la solución, mientras que el recocido simulado permite aceptar soluciones peores para evitar quedar atrapado en óptimos locales.
74
¿Qué es el algoritmo de enfriamiento en el recocido simulado?
Es el proceso que controla cómo disminuye la temperatura en cada iteración, afectando la exploración y explotación de la función objetivo.
75
¿Por qué se considera el recocido simulado un método probabilístico?
Porque introduce aleatoriedad en la aceptación de soluciones, permitiendo escapar de óptimos locales mediante la aceptación de soluciones peores con cierta probabilidad.
76
¿Qué es un algoritmo genético?
Un algoritmo de búsqueda que simula la evolución biológica.
77
¿Cuál es el primer paso en un algoritmo genético?
Inicialización.
78
¿Qué etapa en un algoritmo genético mide la aptitud de cada individuo?
Evaluación.
79
¿Qué método de selección asigna probabilidad de selección proporcional a la aptitud del individuo?
Selección por ruleta.
80
¿Qué método de selección escoge al mejor de un grupo aleatorio de individuos?
Selección por torneo determinista.
81
¿Qué método de selección escoge un individuo con base en la probabilidad de su aptitud pero sin ser determinista?
Selección por torneo probabilista.
82
¿Qué tipo de cruce implica elegir un solo punto en los padres para combinar sus genes?
Cruce de un punto.
83
¿Qué tipo de cruce implica elegir dos puntos en los padres para combinar sus genes?
Cruce de dos puntos.
84
¿Qué tipo de cruce mezcla aleatoriamente los genes de los dos padres?
Cruce uniforme.
85
¿Qué es la mutación en un algoritmo genético?
Modificación aleatoria en uno o varios genes de un individuo para diversificar la población.
86
¿Qué reemplazamiento elige aleatoriamente a los individuos que serán reemplazados?
Reemplazamiento aleatorio.
87
¿Qué reemplazamiento reemplaza a los padres con sus descendientes?
Reemplazamiento de los padres.
88
¿Qué reemplazamiento selecciona individuos similares en aptitud para reemplazarlos?
Reemplazamiento de individuos similares.
89
¿Qué reemplazamiento selecciona a los individuos de menor aptitud para reemplazarlos?
Reemplazamiento de los peores.
90
¿Qué indica el criterio de finalización en un algoritmo genético?
Cuándo termina el proceso, como al alcanzar una solución óptima o llegar a un número máximo de generaciones.
