buscaminas
Páginas: 2 (460 palabras)
Publicado: 27 de febrero de 2014
Buscaminas
Christian Pichardo
12 de mayo del 2010
Esquema
1 Introducci´n
o
¿Qu´ es el buscaminas?
e
¿C´mo se juega?
o
An´lisis por bloque y multibloque
a
1 Suerte
1 Clases decomplejidad
Algunos ejemplos
Algunas definiciones
SAT
1 De regreso al buscaminas
El Problema de consistencia del buscaminas
1 Bibliograf´
ıa
1 Pizzas
1989
Robert Donner
Despejar uncampo de minas sin destapar ninguna
Tiempo
Las casillas con n´mero indican cu´ntas minas hay en las ocho
u
a
casillas vecinas
Se marcan con banderitas las minas
Situaci´n inicial
o Situaci´n inicial
o
Principiante:
10
≈ 0,12345
9∗9
Intermedio:
40
= 0,15625
16 ∗ 16
Experto:
99
= 0,20625
16 ∗ 30
Desarrollo
A, B y C minas
D y E no pueden tener
F depende de D Suerte
No siempre es suficiente
Ejemplo 1
¿13 =
√
169?
Ejemplo 2
{10, 4, 5, 7, −23, 2, 35, 76}
Ejemplo 3
400 alumnos
Dormitorio para 100 por parejas
Lista de prohibidos Algoritmo
Procedimiento para resolver un problema en el que cada paso
est´ programado
a
Tiempo de ejecuci´n
o
N´mero de operaciones necesarias para obtener la respuesta
u
Clasede complejidad P
Un problema es de clase P si puede ser resuelto usando un
algoritmo cuyo tiempo de ejecuci´n crece menos r´pido que una
o
a
potencia fija del n´mero de s´
u
ımbolosrequeridos para especificar los
datos iniciales. De otro modo, el problema es no-P.
Clase de complejidad NP
Un problema es de clase NP si la pregunta ¿Es x la soluci´n al
o
problema? puede serverificada en tiempo polinomial.
(Nondeterministic polynomial)
Clase de complejidad NP-completo
Un problema es NP-completo si es NP y cualquier problema NP
puede transformarse polin´micamente en ´l.o
e
Transformaci´n polin´mica
o
o
Es una manera de relacionar dos problemas de decisi´n, de manera
o
que la existencia de un algoritmo que resuelve el primer problema,
garantiza...
Christian Pichardo
12 de mayo del 2010
Esquema
1 Introducci´n
o
¿Qu´ es el buscaminas?
e
¿C´mo se juega?
o
An´lisis por bloque y multibloque
a
1 Suerte
1 Clases decomplejidad
Algunos ejemplos
Algunas definiciones
SAT
1 De regreso al buscaminas
El Problema de consistencia del buscaminas
1 Bibliograf´
ıa
1 Pizzas
1989
Robert Donner
Despejar uncampo de minas sin destapar ninguna
Tiempo
Las casillas con n´mero indican cu´ntas minas hay en las ocho
u
a
casillas vecinas
Se marcan con banderitas las minas
Situaci´n inicial
o Situaci´n inicial
o
Principiante:
10
≈ 0,12345
9∗9
Intermedio:
40
= 0,15625
16 ∗ 16
Experto:
99
= 0,20625
16 ∗ 30
Desarrollo
A, B y C minas
D y E no pueden tener
F depende de D Suerte
No siempre es suficiente
Ejemplo 1
¿13 =
√
169?
Ejemplo 2
{10, 4, 5, 7, −23, 2, 35, 76}
Ejemplo 3
400 alumnos
Dormitorio para 100 por parejas
Lista de prohibidos Algoritmo
Procedimiento para resolver un problema en el que cada paso
est´ programado
a
Tiempo de ejecuci´n
o
N´mero de operaciones necesarias para obtener la respuesta
u
Clasede complejidad P
Un problema es de clase P si puede ser resuelto usando un
algoritmo cuyo tiempo de ejecuci´n crece menos r´pido que una
o
a
potencia fija del n´mero de s´
u
ımbolosrequeridos para especificar los
datos iniciales. De otro modo, el problema es no-P.
Clase de complejidad NP
Un problema es de clase NP si la pregunta ¿Es x la soluci´n al
o
problema? puede serverificada en tiempo polinomial.
(Nondeterministic polynomial)
Clase de complejidad NP-completo
Un problema es NP-completo si es NP y cualquier problema NP
puede transformarse polin´micamente en ´l.o
e
Transformaci´n polin´mica
o
o
Es una manera de relacionar dos problemas de decisi´n, de manera
o
que la existencia de un algoritmo que resuelve el primer problema,
garantiza...
Leer documento completo
Regístrate para leer el documento completo.