ESTE PROGRAMA ES DE UN AUTOMATA QUE AL INICIAR SOLO ACEPTA UNA LETRA O UN NUMERO, DESPUES UN SIMBOLO + O *, Y ASI SUCESIVAMENTE, PERO NO SE ACEPTA INICIAR CON + O *, Y TAMPOCO PUEDE TERMINAR EN ELLOS, Y NO SE PUEDEN REPETIR NINGUN CARACTER NI UNA SOLA VEZ CONSECUTIVA.
package tarea_1;
import javax.swing.JOptionPane;
public class tarea_1
{
public static void main(String[] args)
{
int tabla[][] = new int [5][5];
tabla [0][0] = 1; tabla [0][1] = 1; tabla [0][2] = 4; tabla [0][3] = 4; tabla [0][4] = 4;
tabla [1][0] = 4; tabla [1][1] = 4; tabla [1][2] = 2; tabla [1][3] = 2; tabla [1][4] = 1;
tabla [2][0] = 3; tabla [2][1] = 3; tabla [2][2] = 4; tabla [2][3] = 4; tabla [2][4] = 4;
tabla [3][0] = 4; tabla [3][1] = 4; tabla [3][2] = 2; tabla [3][3] = 2; tabla [3][4] = 3;
tabla [4][0] = 4; tabla [4][1] = 4; tabla [4][2] = 4; tabla [4][3] = 4; tabla [4][4] = 4;
String palabra;
palabra = JOptionPane.showInputDialog(null, "Introduzca la palabra:");
int estado = 0, i;
for ( i = 0; palabra.length() > i; i++ )
{
if(palabra.charAt(i) >= 'a' && palabra.charAt(i) <= 'z') { estado = tabla[estado][0]; } else if(palabra.charAt(i) >= '0' && palabra.charAt(i) <= '9')
{
estado = tabla[estado][1];
}
else if(palabra.charAt(i) == '+')
{
estado = tabla[estado][2];
}
else if(palabra.charAt(i) == '*')
{
estado = tabla[estado][3];
}
else
{
estado = 4;
break;
}
}
if(estado == 4)
{
JOptionPane.showMessageDialog(null, "La Palabra '" + palabra + "' no es aceptada.");
}
else
{
JOptionPane.showMessageDialog(null, "La Palabra '" + palabra + "' es aceptada.");
}
}
}
jueves, 15 de octubre de 2009
domingo, 30 de agosto de 2009
ALGORITMOS COMPUTACIONALES
COMPLEJIDAD DE LOS ALGORITMOS COMPUTACIONALES
La complejidad de los algoritmos nos representa o dice el tiempo de ejecución
de cialquier programa en base a los 'n' datos de entrada. Por lo tanto la com-
plejidad de cualquier algorito se expresa en los siguientes términos:
T(n) Funcion de la complejidad la cual se interpreta de la siguiente manera:
El tiempo de ejecución está dado por los n datos de entrada
TIPOS DE COMPLEJIDAD
Los problemas de decisión se clasifican en conjuntos de complejidad comparable
llamados clases de complejidad.
La clase de complejidad P es el conjunto de los problemas de decisión que pueden
ser resueltos en una máquina determinista en tiempo polinómico, lo que corresponde
intuitivamente a problemas que pueden ser resueltos aún en el peor de sus casos.
La clase de complejidad NP es el conjunto de los problemas de decisión que pueden
ser resueltos por una máquina no determinista en tiempo polinómico. Esta clase contiene
muchos problemas que se desean resolver en la práctica, incluyendo el problema de
satisfacibilidad booleana y el problema del viajante, un camino Hamiltoniano para
recorrer todos los vértices una sola vez. Todos los problemas de esta clase tienen
la propiedad de que su solución puede ser verificada efectivamente.
COMO MEDIR LA COMPLEJIDAD
Una medida útil para conocer el tiempo de ejecución de un programa dependiendo de su
tamaño (N) es lo que llamaremos a partir de ahora T(N). Para un programa del tipo
S1; for(i=0;i
Siendo S1 y S2 un conjunto de sentencias válidas tenemos que su función T(N) tendría la forma
T(N) = T(S1) + N*T(S2)
Cualquier fórmula de T(N) hace referencia a N o/y a una serie de parámetros
constantes. Dado que la potencia computacional aumenta cada año hay que analizar
los algoritmos dejando de lado estos dos factores (N y parámetros constantes) haciendo
que nuestro análisis sea independiente de la máquina empleada.
Para hacer esto se suele calcular el comportamiento cuando N tiende a infinito,
es decir, su comportamiento asintótico. Se suele en estos caso no hablar de una función
que nos da el tiempo dado el tamaño del problema sino que se suele definir un conjunto
de funciones que nos dan este comportamiento y se afirma que estas funciones son del
Orden de f(n) siendo esta una función representativa de todas ellas. Y se denota el
orden por O(f(n)). Para caracterizar formalmente esta definición tenemos que:
O(f(n))= {g: ENTERO -> REAL+ tales que
existen las constantes k y N0 tales que
para todo N > N0, g(N) <= k*f(N) }
en otras palabras O(f(n)) está formado por todas las funciones que crecen a un ritmo
menor o igual a f(n). Es decir f(n) es la cota superior para este conjunto de funciones g(n).
O(f(n)) define un orden con todas sus propiedades, escogemos un representante de este
orden y así tendremos:
O(1) orden constante
O(log n) orden logarítmico
O(n) orden lineal
O(n log n)
O(n2) orden cuadrático
O(na) orden polinomial (a > 2)
O(an) orden exponencial (a > 2)
O(n!) orden factorial
Esto nos dará pues un indicador de la bondad de un algoritmo, cuanto menor sea el orden mejor.
www.estructuradedatos.galeon.com/complejidadalgo.html
La complejidad de los algoritmos nos representa o dice el tiempo de ejecución
de cialquier programa en base a los 'n' datos de entrada. Por lo tanto la com-
plejidad de cualquier algorito se expresa en los siguientes términos:
T(n) Funcion de la complejidad la cual se interpreta de la siguiente manera:
El tiempo de ejecución está dado por los n datos de entrada
TIPOS DE COMPLEJIDAD
Los problemas de decisión se clasifican en conjuntos de complejidad comparable
llamados clases de complejidad.
La clase de complejidad P es el conjunto de los problemas de decisión que pueden
ser resueltos en una máquina determinista en tiempo polinómico, lo que corresponde
intuitivamente a problemas que pueden ser resueltos aún en el peor de sus casos.
La clase de complejidad NP es el conjunto de los problemas de decisión que pueden
ser resueltos por una máquina no determinista en tiempo polinómico. Esta clase contiene
muchos problemas que se desean resolver en la práctica, incluyendo el problema de
satisfacibilidad booleana y el problema del viajante, un camino Hamiltoniano para
recorrer todos los vértices una sola vez. Todos los problemas de esta clase tienen
la propiedad de que su solución puede ser verificada efectivamente.
COMO MEDIR LA COMPLEJIDAD
Una medida útil para conocer el tiempo de ejecución de un programa dependiendo de su
tamaño (N) es lo que llamaremos a partir de ahora T(N). Para un programa del tipo
S1; for(i=0;i
Siendo S1 y S2 un conjunto de sentencias válidas tenemos que su función T(N) tendría la forma
T(N) = T(S1) + N*T(S2)
Cualquier fórmula de T(N) hace referencia a N o/y a una serie de parámetros
constantes. Dado que la potencia computacional aumenta cada año hay que analizar
los algoritmos dejando de lado estos dos factores (N y parámetros constantes) haciendo
que nuestro análisis sea independiente de la máquina empleada.
Para hacer esto se suele calcular el comportamiento cuando N tiende a infinito,
es decir, su comportamiento asintótico. Se suele en estos caso no hablar de una función
que nos da el tiempo dado el tamaño del problema sino que se suele definir un conjunto
de funciones que nos dan este comportamiento y se afirma que estas funciones son del
Orden de f(n) siendo esta una función representativa de todas ellas. Y se denota el
orden por O(f(n)). Para caracterizar formalmente esta definición tenemos que:
O(f(n))= {g: ENTERO -> REAL+ tales que
existen las constantes k y N0 tales que
para todo N > N0, g(N) <= k*f(N) }
en otras palabras O(f(n)) está formado por todas las funciones que crecen a un ritmo
menor o igual a f(n). Es decir f(n) es la cota superior para este conjunto de funciones g(n).
O(f(n)) define un orden con todas sus propiedades, escogemos un representante de este
orden y así tendremos:
O(1) orden constante
O(log n) orden logarítmico
O(n) orden lineal
O(n log n)
O(n2) orden cuadrático
O(na) orden polinomial (a > 2)
O(an) orden exponencial (a > 2)
O(n!) orden factorial
Esto nos dará pues un indicador de la bondad de un algoritmo, cuanto menor sea el orden mejor.
www.estructuradedatos.galeon.com/complejidadalgo.html
Suscribirse a:
Entradas (Atom)