Teoría de la computación

UNIVERSIDAD NACIONAL SAN ANTONIO ABAD DEL CUSCO

FACULTAD DE INGENIERÍA ELÉCTRICA, ELECTRÓNICA, INFORMÁTICA Y MECÁNICA

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

Teoría de la Computación

[pic 1]

TAREA 01:

Presentado por:

• Sotomayor Castro, Irma Esther

Docente:

Ing. Hector Eduardo Ugarte Rojas

CUSCO - PERÚ

2022

RESPONDER CONCISAMENTE:

1. Lista y explica al menos 5 algoritmos que resuelvan el problema de ordenamiento (Sorting algorithms).

Primero, indicar que los algoritmos de ordenamiento, como su nombre lo dice, nos permiten ordenar datos o información, basándose en algún criterio de ordenamiento.

Algunos de los algoritmos de ordenamiento son:

• Ordenamiento de burbuja (bubble sort). Que funciona comparando el elemento que será ordenado con el siguiente elemento de la lista e intercambiándose si no están en el orden correcto, para lo cual se debe revisar varias veces la lista hasta que ya no sea necesario más intercambios.

[pic 2]

• Ordenamiento por inserción (Insertion sort).Es una manera de ordenamiento natural. Consiste en que primero se tiene un sólo elemento (éste es un conjunto ordenado); cuando hay n elementos ordenados de menor a mayor, se toma el elemento n-+1 y se compara con todos los elementos ya ordenados y se detiene en dos casos: cuando se encuentra un elemento menor; es decir, todos los elementos mayores fueron desplazados una posición a la derecha; o cuando ya no se encuentran elementos, porque todos los elementos han sido desplazados y este elemento es el menor o más pequeño. Es en este punto donde se inserta el elemento k+1 y se desplaza los demás elementos.

[pic 3]

• Ordenamiento por cuentas (courting sort). Con este algoritmo se cuenta el número de elementos de cada clase para ordenarlos, se elige el valor mínimo y máximo de la lista como intervalo, dentro del cual se realiza el ordenamiento. Este algoritmo solo se utiliza para ordenar elementos “contables” (números enteros).

[pic 4]

• Ordenamiento por mezcla (merge sort).Este es un algoritmo de ordenamiento externo, que se basa en la técnica del divide y vencerás.

Su funcionamiento es de la siguiente manera:

1. Si la lista es de 0 o 1 elemento, significa que está ordenada. Otro caso: Si la lista tiene más de 1 elemento:
2. Se divide a la mitad la lista desordenada; es decir obtenemos 2 sublistas.

1. Se ordena cada sublista de manera recursiva (llamando nuevamente al método merge sort).
2. Y finalmente se mezclan las dos sublistas en una sola.

[pic 5]

• Ordenamiento con árbol binario. Este algoritmo ordena los elementos utilizando un árbol binario de búsqueda, es decir cumple la condición de que cada nodo tiene a lo sumo dos hijos. Consiste en construir poco a poco el árbol binario insertando cada uno de los elementos de la lista, los cuales quedarán ordenados. Finalmente, al recorrer el árbol en orden, se obtiene la lista de elementos ya ordenados.

[pic 6]

1. Explica el problema de optimización y planificación llamado “Problema de programación de clases universitarias” (University Class Scheduling Problem UCSP).

El problema de programación de clases universitarias es un problema que surge en muchas instituciones educativas públicas y privadas. Este problema puede ser clasificado de acuerdo al tipo de horario que se desea generar, así se encuentra problemas de programación de horarios de exámenes, de asignaturas, de asignación de docentes y/o asignación de espacios; buscando programar, de manera planificada, las asignaturas que se ofrecen, teniendo en cuenta las restricciones asociadas a los docentes, periodos, plan de estudio, tipo de asignatura, días hábiles, entre otros.

1. Explica qué es el Modelo RDF (Resource Description Framework) y en donde se usa.

Es un modelo conceptual que se utiliza para brindar información descriptiva sobre los recursos que se encuentran en la web semántica, que en el caso de las aplicaciones informáticas utilizan información estructurada distribuida por toda la web.

Los esquemas RDF (objetos específicos de la categoría del modelo de datos RDF) son diagramas Entidad Relación - ER. En la terminología del diseño orientado a objetos, los recursos corresponden con objetos y las propiedades corresponden con objetos específicos y variables de una categoría; donde:

• Los recursos son todas las cosas descritas por expresiones RDF. Ejem. Un recurso puede ser una página web completa o parte de una página web. También puede ser una colección completa de páginas, etc.
• Las propiedades son los aspectos específicos, características, relación o atributo que es utilizado para describir un recurso. Donde cada propiedad tiene un significado específico que define sus valores permitidos, el tipo de

recursos que puede describir y sus relaciones con otras propiedades.

Es así que, un recurso específico junto a una propiedad y su valor (el valor de la propiedad para dicho recurso) es una sentencia.

Ejemplo:

Dada la sentencia:

Ora Lassila es el creador [autor] del recurso

http://www.w3.org/Home/Lassila.

Aquí podemos ver que:

El recurso es: http://www.w3.org/Home/Lassila.

La propiedad es: Creator

El objeto es: “Ora Lassaila”

En este documento, gráficamente podríamos representar una sentencia RDF usando gráficos etiquetados, donde los nodos representan los recursos (en óvalos) y las propiedades se representan mediante arcos. Los nodos que representan cadenas de

...