Justificacion

301405_AUTOMATAS Y LENGUAJES FORMALES

ACTIVIDAD 2 RECONOCIMIENTO GENERAL Y DE ACTORES

Presentado por:

JAIME ALBERTO QUINTERO RAMÍREZ (94472479)

Cead Palmira

Tutor:

JESUS EMIRO VEGA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

Facultad de Ciencias Básicas, Tecnología e Ingeniería

Buga, Marzo de 2013

INTRODUCCION

Con el desarrollo de esta actividad se busca afianzar los conocimientos que se tienen sobre los conjuntos. Poniéndolos en práctica co la solución de los ejercicios planteados

Cabe resaltar que los conjuntos pueden implementarse en diversos campos como lo son los sistemas.

Con una estructura de datos ideal se comprueba si un objeto se encuentra en el conjunto, además de activarse otras operaciones útiles tales como la iteración sobre todos los objetos del conjunto, la realización de uniones o intersecciones entre dos conjuntos, o la toma del complemento de un conjunto en algún dominio limitado. Cualquier estructura de datos en cadena asociativa puede usarse para implementar un conjunto, dejando que los juegos de claves sean los elementos del conjunto, e ignorando los valores. Gracias a su parecido con las series asociativas, los conjuntos se implementan habitualmente por los mismos medios, es decir, un árbol binario de búsqueda auto-balanceable para conjuntos ordenados (con O (log n) para la mayoría de operaciones), o una tabla hash para conjuntos no ordenados (que tienen O(1) en el caso promedio, pero O (n) en el peor caso, para la mayoría de operaciones). Es posible usar una tabla de hash lineal ordenada para crear conjuntos deterministamente ordenados. Otros métodos generalizados incluyen las cadenas (array). En particular, un subconjunto de enteros 1..n puede ser implementado de manera eficaz como en una matriz de bits con n bits, que además ofrece operaciones de unión e intersección muy eficaces. El filtro Bloom implementa un conjunto por probabilidad, por medio de una muy compacta representación, pero arriesgando una pequeña probabilidad de falsos positivos en interrogantes. Sin embargo, casi ninguna de estas estructuras de datos ofrece operaciones de conjuntos como de unión o de intersección de manera fiable. Para dichas operaciones existen otras estructuras de datos de conjunto más especializadas.

JUSTIFICACION

Uno de los primeros lenguajes que soportaban conjuntos fue Pascal; muchos lenguajes lo incluyen ahora, ya sea en el núcleo del lenguaje o en una librería estándar. El Lenguaje de programación Java ofrece la interfaz Set para el soporte de conjuntos (donde lo implementa la clase HashSet usando una tabla hash), y la sub-interfaz SortedSet para dar soporte a conjuntos ordenados (implementado por la clase TreeSet por medio de un árbol de búsqueda binario). En C++, STL ofrece la clase "conjunto" para templates, que implementa a un conjunto ordenado usando un árbol de búsqueda binario; el STL de SGI ofrece la clase "hash_set", implementando conjuntos con una tabla de hash. Python tiene un tipo de conjunto incorporado, pero no un conjunto en sí.

ACTIVIDADES A DESARROLLAR:

1. Expresar en extensión el conjunto{x|x∈ N, x > 10}

2. Expresar en intención el conjunto {4, 6, 8, 12, 14, 16}.

3. ¿Cuál es el tamaño del conjunto {Ø} (esto es, cuántos elementos contiene)?

Justifique su respuesta.

El tamaño del conjunto es cero.

El conjunto carece de elementos.

4. Sean los conjuntos A = {a, b}, B = {1, 2, 3}. Calcular las siguientes operaciones:

5. Calcular los conjuntos potencia de los siguientes conjuntos:

a) {1,2,3}

b) {a,b,c,d}

c) {a,{b,c}}

d) {Ø}

e) {1,{2,3}, {4,5},2}

6. Sea R la siguiente relación de A = {1, 2, 3} en B = {a, b}. R = {(1, a), (1, b), (3, a)};

Representar R como un diagrama cartesiano, un diagrama de flechas y como una tabla binaria.

...