Buenos días estimados lectores. en esta ocasión hablaremos un poco sobre la complejidad computacional, donde se realizara una explicación sobre esta para luego hacerles referencia a un ejemplo muy interesante sobre un algoritmo para reducir la complejidad computacional en la conversión de AFNDs. A AFDs.
La complejidad computacional estudia la eficiencia de los algoritmos
estableciendo su efectividad de acuerdo al tiempo de corrida y al espacio
requerido en la computadora o almacenamiento de datos, ayudando a evaluar
la viabilidad de la implementación práctica en tiempo y costo.
Por otra parte, provee herramientas para clasificar la dificultad inherente de un
problema, de esta manera se puede conocer previamente si la búsqueda de un
algoritmo eficiente para la solución de dicho problema es posible o no.
Existen problemas que únicamente pueden resolverse utilizando un algoritmo
de tiempo exponencial o incluso, puede ser que no exista algoritmo alguno, por
lo cual, al tener este tipo de información puede optarse por la búsqueda o
aplicación de técnicas heurísticas existentes, que si bien no garantizan una
solución óptima, si pueden proporcionar una buena solución o una aproximada.
ALGORITMO PARA REDUCIR LA COMPLEJIDAD COMPUTACIONAL EN LA CONVERSIÓN DE AFNDs. A AFDs.
Al convertir un Autómata Finito No Determinístico (AFND) a un
Autómata Finito Determinístico (AFD) los algoritmos descritos en la
mayoría de la documentación presentan una complejidad computacional
del tipo exponencial (O(2n)), lo cual no es deseable. Esto se debe a las
múltiples combinaciones que se dan al hallar los posibles estados
equivalentes entre autómatas. El presente articulo propone un algoritmo
que reduce dicha complejidad.
Un problema que se presenta, cuando se realizan transformaciones de Autómatas Finitos No Deterministas (AFNDs.), a Autómatas Finitos Deterministas (AFDs.), concretamente en su equivalencia computacional, es que en dicha transformación, se presenta una alta complejidad de tipo computacional: O(2n), debido a que el algoritmo tiene en cuenta todas las posibles combinaciones de los estados del AFND, al realizar dicha transformación.
Cuando se trata de pequeños AFNDs, es decir cuando el número de estados es pequeño (no mayor que de 4), la complejidad computacional de la transformación no suele ser impactante y se puede recurrir al algoritmo propuesto en la antes mencionada bibliografía.
Lo anterior se debe, a que el algoritmos que establecen la equivalencia computacional entre AFNDs. y AFDs., basan su fundamento, en que un conjunto de estados en un AFND es equivalente a uno en el AFD.
En este artículo, proponemos un algoritmo, que reduce la complejidad en el caso promedio, en la conversión de un AFND a AFD.
Para ver el ejercicio completo de conversión de AFNDs. A AFDs usando la complejidad computacional los invitamos a visitar el siguiente link: http://www.slideshare.net/robnetti/automataimageseste
Una vez visto el ejercicio completo podemos finalizar este articulo con algunas conclusiones y recomendaciones:
En el algoritmo tradicional que consiste de la ecuaciones (6) y (7), las complejidades en el mejor y en el peor de los casos son de orden exponencial (0(2n)). El algoritmo propuesto presenta una mejora sustancial mejorando el mejor de los casos, obteniéndose una complejidad de orden lineal (O(n)) y el caso promedio se aproxima a una cuadrática (O(n2)).
En esta materia de autómatas de la universidad fermin toro, los estudiantes hemos participado en una serie de actividades muy interesantes para el aprendizaje de esta materia. Las cuales vamos a subir a este blog para el disfrute de todos!
Video: http://youtu.be/Ei2d0pbwt58
Webguest: http://www.webquestceys.com/majwq/wq/ver/7853
Mapa: http://www.slideshare.net/robnetti/mapa1111
Ejercicios: http://www.slideshare.net/robnetti/automataroberto
investigacion expositiva: http://www.slideshare.net/robnetti/automat1111
Webguest: http://www.webquestceys.com/majwq/wq/ver/7853
Mapa: http://www.slideshare.net/robnetti/mapa1111
Ejercicios: http://www.slideshare.net/robnetti/automataroberto
investigacion expositiva: http://www.slideshare.net/robnetti/automat1111
