Victor Rosales Jaimes

Programa que dada una cadena \(w\) y una expresión regular \(r\), indica si la cadena \(w\) pertenece a \(L[r]\). Para esto se usan las técnicas, denotación de expresiones regulares,así como la definición de funciones básicas entre lenguajes y expresiones regulares. Se determinara que lenguaje \(L\) genera una expresión regular \(r\).

El problema del ordenamiento en computación es muy importante, tanto que en un curso de Análisis de Algoritmos se le dedica al menos una cuarta parte del curso. En cuanto a complejidad podemos encontrar diversos algoritmos con distinta complejidad computacional en tiempo. El propósito de este análisis es mostrar de manera experimental como funciona el concepto de complejidad, la razón es que cuando el concepto es presentado a los alumnos este es muy abstracto para el entendimiento del concepto.

Se define el conjunto de Mandelbrot como \(c\in\mathbb{C}\) tal que \(\{Z_{c,n}\}\) esta acotada. Donde la sucesión \(\{Z_{c,n}\}\) esta dada por: $$ z_{c,0} = 0\hspace{1cm} z_{c,n+1} = z_{c,n}^2 + c. $$

Se construye un ordenador Lexicográfico por lineas, este esta implementado con Java y usa las clases de estructuras de datos proporcionadas por el profesor. Este proyecto fue desarrollado en el curso de Estructuras de Datos impartido por el profesor Canek Peláez. Este ordenador es capaz de ordenar uno o varios archivos y lo puede hacer en orden natural o en reversa.

El esquema de secreto compartido de Shamir hace posible que un sólo dato pueda ser ocultado de manera que, a partir de él, se generan n diferentes datos y que con, al menos \(t \le n\) cualesquiera de ellos sea posible recuperar el dato original. Es bien sabido que \(r\) puntos en el plano determinan un único polinomio de grado \(r-1\), a saber, el polinomio que interpola los \(r\) puntos. Bastan, por ejemplo, dos puntos para determinar la línea que los une, o tres puntos para encontrar la única parábola que pasa por ellos.

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene pesos en cada arista. La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen hasta el resto de los vértices que componen el grafo, el algoritmo se detiene

El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

De entre \(n\) personas, se define una celebridad como alguien quien es conocido por todos pero no conoce a nadie. El problema consiste en identificar a la celebridad, si es que existe, haciendo preguntas de la forma ¿Disculpe, usted conoce a aquella persona?. Se asume que todas las respuestas son verdaderas y que también la celebridad debe contestar.

Dada una secuencia \(x_1,\ldots,x_n\) de números reales no necesariamente positivos encontrar la subsecuencia de elementos consecutivos \(x_i,\ldots,x_j\) tal que la suma de los números de la subsecuencia sea la máxima entre todas las subsecuencias de elementos consecutivos. Notamos que el hecho de que un secuencia ya es este ordenada no implica que la secuencia sea máxima, un ejemplo de esto puede verse en la secuencia \(\{-3,-1,0,3,5\}\), lo anterior si sucede si la secuencia esta compuesta de números positivos.

Búsqueda de interpolación es una variante modificada o más bien mejorada del algoritmo de búsqueda binaria. Este algoritmo trabaja en la posición de prueba del valor requerido para buscar, la búsqueda intenta acercarse al valor real en cada paso o hasta que se encuentra el elemento de búsqueda. Para poder usar esta técnica de búsqueda es necesario que la secuencia se encuentre ordenada.

En Lógica Resolución es una regla de inferencia utilizada sobre cierto tipo de proposiciones lógicas y es especialmente utilizada para los demostradores automatizados de teoremas. Utilizando resolución se puede construir un demostrador que sea completo (por contradicción) y correcto (en inglés refutational complete and sound) para la lógica proposicional y de primer orden supuesto que un conjunto de proposiciones son insatisfacibles. Por otro lado si el conjunto de proposiciones de hecho es satisfacible, puede o no terminar en una cantidad finita de pasos una demostración por resolución, generalmente lo que sucede es que se asigna un tiempo límite para hallar si un conjunto es insatisfacible o no.

El algoritmo DPLL/Davis-Putnam-Logemann-Loveland es un algoritmo completo basado en la vuelta atrás que sirve para decidir la satisfactibilidad de las fórmulas de lógica proposicional en una forma normal conjuntiva, es decir, para resolver el problema CNF-SAT. El algoritmo de vuelta atrás (backtracking) se ejecuta eligiendo un literal, asignándole un valor de verdad a este, simplificando la fórmula y a continuación, en forma recursiva comprobando si la fórmula simplificada es satisfacible; si este es el caso la fórmula original es satisfacible; de lo contrario, la misma verificación recursiva termina asumiendo el valor de verdad contrario.

En 1982, Martelli y Montanari describieron un algoritmo en forma de un conjunto de reglas que transforman un conjunto de ecuaciones. El algoritmo se presenta en libros educativos. Es similar al algoritmo propuesto por Herbrand en su tesis. Según Baader y Snyder, un algoritmo en forma de conjunto de reglas libera los conceptos esenciales y permite demostrar la corrección de varios algoritmos prácticos al mismo tiempo.

Prolog es un lenguaje de programación lógica cuya primera versión fue desarrollada a principios de la década de 1970 por Colmerauer en la universidad de Marsella. Contrariamente a otros lenguajes de programación basados es estructuras de control y definición de funciones para calcular resultados, Prolog está orientado a la especificación de relaciones para responder consultas. En ese sentido Prolog es similar a un sistema de base de datos, aunque en el contexto de la inteligencia artificial se prefiere hablar de bases de conocimiento, enfatizando la complejidad estructural de los datos y de las deducciones que se pueden obtener de ellos.