ayuda con este trabajo de pascal por favor
Publicado por jose (3 intervenciones) el 24/10/2014 04:27:50
En teoría de grafos, un grafo bipartito es un grafo G=(N, E) cuyos vértices se pueden separar en dos conjuntos disjuntos U y V, es decir, que se cumplen las siguientes propiedades.
U U V = N
U ∩ V = Ǿ
Atendiendo a estas propiedades se tiene por definición:
Sea un grafo G, cuyo conjunto de vértices puede ser expresado como la unión disjunta de dos subconjuntos de vértices V1 y V2, de forma que cada arista de G une un vértice de V1 con otro de V2, entonces se dice que G es un grafo bipartito y se cumple que V1∩V2=0, V1UV2=V. Esta relación expresada en notación sería:
Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices, y las aristas uniendo vértices de columnas (o filas) diferentes.
Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul, y los vértices en V de verde, obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores, no es bipartito.
Un grafo bipartito con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dos subconjuntos tienen la misma cantidad de elementos o cardinalidad, decimos que el grafo bipartito G es balanceado. a continuación se presenta el trabajo en dos fases
Lea con atención el siguiente planteamiento: Caso 1:
El Estado Trujillo es una región andina ubicada al occidente de
Venezuela, está conformado por 20 municipios como se puede observar en la Fig.1.
Con los conceptos dados sobre grafos y datos del Caso 1, se pide un programa en lenguaje de programación Pascal que permita:
• Transformar el mapa en un grafo donde cada vértice representa una región y cada arista un límite entre regiones.
• ¿Cuántos colores se necesitan para colorear un mapa de forma que no haya dos regiones con frontera del mismo color?
• Determinar si el grafo bipartito es balanceado.
• Imprima los gráficos junto con la información dada en la Fig. No.1
Fase 2 Del Trabajo
El método de ordenación por burbuja se basa en comparaciones sucesivas de dos elementos consecutivos, realizando un intercambio entre los elementos hasta que queden ordenados.
Por ejemplo, si se tiene un vector de 6 elementos, para realizar la ordenación se han de seguir estos pasos:
- Se comparan los dos primeros elementos, si el segundo es superior
al primero, se dejan tal como están, pero si el primero es el más grande, se intercambian los elementos.
- A continuación se compara el segundo elemento con el tercero
aplicando los mismos criterios del paso anterior.
- De esta forma se repite la operación de comparación con todos los elementos que forman el vector. Cuando se alcance el último
elemento se ha encontrado el elemento que tiene el valor más elevado, este ha quedado situado al final del vector.
- Para encontrar el segundo elemento se repite la operación de
ordenación de todos los elementos del vector excepto con el último.
- Reiterando el proceso descrito, el vector quedará ordenado cuando solo se comparen los dos primeros elementos.
Partiendo de lo anteriormente planteado, realice lo siguiente:
Lea con atención el siguiente planteamiento: Caso 2:
a) Tomando en cuenta esta información y los datos de la Tabla No.1 del Objetivo 7, realizar un programa en Pascal que ordene los municipios en orden alfabético, aplicando el algoritmo de ordenamiento de la Burbuja.
b) Imprima el vector y nombre de los municipios.
Dada la tabla No.1 de los municipios del estado Trujillo.
Tabla No.1
Municipios del Estado Trujillo
Municipio
2 Andrés Bello
3 Boconó
4 Bolívar
6 Candelaria
8 Carache
1 Escuque
5 José Felipe Márquez Cañizales
9 Juan Vicente Campo Elías
7 La ceiba
10 Miranda
11 Monte Carmelo
12 Motatán
13 Pampán
14 Pampanito
15 Rafael Rangel
16 San Rafael de Carvajal
17 Sucre
18 Trujillo
19 Urdaneta
20 Valera
Desarrolle un programa en PASCAL, que construya una estructura tipo hashing o dispersión, para almacenar los nombres de los municipios por su posición dada en la tabla, en un archivo tipo texto. El programa se hará bajo las siguientes consideraciones:
• A través del archivo de texto, extraiga cada nombre de un municipio y ubíquelo en la estructura mencionada.
• Imprima el nombre del municipio a medida que lo inserta en la estructura y el número de la celda, para ello utilice una función de hashing,
Función hashing: consiste en la suma de las posiciones en el alfabeto de las letras (codificación ASCII) que conforman el nombre del estado. Como se indica a continuación:
N
f (nombre _ estado) = (∑ Li ) mod r ,
i =1
en donde Li es el código ASCII de cada letra que forma el nombre del jugador, r es el número de entradas de la tabla de hashing o número de buckets o slots. En este caso escoja un valor de r, el mejor será el que produce menor número de sinónimos. Las tablas de Codificación ASCII (también llamada asqui).
Ejemplo: si se va a construir la “llave” para una tabla de 200 slots( de
0 a 199), y se desea insertar el nombre Texas, de acuerdo a los códigos ASCII ( ver tabla ASCII), la construcción de la “llave” será la siguiente:
Valor = Cod(T) + Cod (e) + Cod (x) + Cod (a) + Cod (s) = 84 + 113 +
120 + + 97+115 = 1012
Valor mod r = 529 mod 199 = 131 (resto de la división entera)
Por lo tanto, la palabra Texas se insertará en una lista asociada a la celda (o slot) 131.
A continuación se presentan las tablas de caracteres ASCII
Símbolo Valor ASCII Símbolo Valor ASCII
A 65 N 78
B 66 O 79
C 67 P 80
D 68 Q 81
E 69 R 82
F 70 S 83
G 71 T 84
H 72 U 85
I 73 V 86
J 74 W 87
K 75 X 88
L 76 Y 89
M 77 Z 90
a 97 n 110
b 98 ñ 241
c 99 o 111
d 100 p 112
e 101 q 113
f 102 r 114
g 103 s 115
h 104 t 116
i 105 u 117
j 106 v 118
k 107 w 119
l 108 x 120
m 109 y 121
z 122
tabla ASCII
Nota: Para determinar el ordinal asociado a cada letra (código ASCII), se puede emplear la función ord, la cual pertenece al conjunto de funciones estándares de Pascal.
Fase 3 Del Trabajo
Elabore un procedimiento en Pascal de búsqueda, tal que, dados los nombres de los municipios, estos se busquen en la tabla de hashing e imprima la celda a la cual está asignada.
Instrucciones de como debe de quedar el trabajo
• Listado documentado del programa fuente. En el encabezado de cada procedimiento, función o sección de programa que lo requiera, debe incluir un breve comentario del proceso que se realiza o del método que aplica. Igualmente es conveniente hacerlo en la definición de las estructuras de datos y variables utilizadas.
• Listado de los resultados.
Recomendaciones
• Emplee nombres de variables, constantes, funciones y procedimientos alusivos a lo que representan.
• Utilice un diseño modular para la resolución del problema. Esta estructura aportará legibilidad y facilidad de comprensión, además evitará redundancias en los procesos. Evite variables globales en las funciones y procedimientos. Emplee parámetros en los mismos, determine cuáles son parámetros valor y cuáles parámetros variables.
• Desarrolle algoritmos eficientes.
• Elabore procedimientos de validación de la data y de detección de errores para evitar interrupciones inesperadas en la ejecución del trabajo.
Se considera logrado el objetivo si al menos se cumple con lo siguiente:
Entrega del listado documentado del programa, codificado en PASCAL, en forma modular y estructurada. En el encabezado de cada procedimiento, función o sección de programa que lo requiera y en la declaración de las estructuras de datos se incluye un breve comentario acerca del proceso, método o definición de estructura, según sea el caso.
Se elabore un programa para resolver el problema planteado en la parte 1. Las partes 2 y 3 se llevan a cabo en un sólo programa o en programas separados.
El programa corre sin restricciones. En general cada programa incluye módulos que realizan o contribuyen a alcanzar lo solicitado en las especificaciones.
Incluye las respuestas en las secciones solicitadas.
Entrega el listado de los resultados.
Esta Relación Expresada En Notacion Seria:
Figura Nro. 01
Tabla ASCII
U U V = N
U ∩ V = Ǿ
Atendiendo a estas propiedades se tiene por definición:
Sea un grafo G, cuyo conjunto de vértices puede ser expresado como la unión disjunta de dos subconjuntos de vértices V1 y V2, de forma que cada arista de G une un vértice de V1 con otro de V2, entonces se dice que G es un grafo bipartito y se cumple que V1∩V2=0, V1UV2=V. Esta relación expresada en notación sería:
Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices, y las aristas uniendo vértices de columnas (o filas) diferentes.
Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul, y los vértices en V de verde, obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores, no es bipartito.
Un grafo bipartito con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dos subconjuntos tienen la misma cantidad de elementos o cardinalidad, decimos que el grafo bipartito G es balanceado. a continuación se presenta el trabajo en dos fases
Lea con atención el siguiente planteamiento: Caso 1:
El Estado Trujillo es una región andina ubicada al occidente de
Venezuela, está conformado por 20 municipios como se puede observar en la Fig.1.
Con los conceptos dados sobre grafos y datos del Caso 1, se pide un programa en lenguaje de programación Pascal que permita:
• Transformar el mapa en un grafo donde cada vértice representa una región y cada arista un límite entre regiones.
• ¿Cuántos colores se necesitan para colorear un mapa de forma que no haya dos regiones con frontera del mismo color?
• Determinar si el grafo bipartito es balanceado.
• Imprima los gráficos junto con la información dada en la Fig. No.1
Fase 2 Del Trabajo
El método de ordenación por burbuja se basa en comparaciones sucesivas de dos elementos consecutivos, realizando un intercambio entre los elementos hasta que queden ordenados.
Por ejemplo, si se tiene un vector de 6 elementos, para realizar la ordenación se han de seguir estos pasos:
- Se comparan los dos primeros elementos, si el segundo es superior
al primero, se dejan tal como están, pero si el primero es el más grande, se intercambian los elementos.
- A continuación se compara el segundo elemento con el tercero
aplicando los mismos criterios del paso anterior.
- De esta forma se repite la operación de comparación con todos los elementos que forman el vector. Cuando se alcance el último
elemento se ha encontrado el elemento que tiene el valor más elevado, este ha quedado situado al final del vector.
- Para encontrar el segundo elemento se repite la operación de
ordenación de todos los elementos del vector excepto con el último.
- Reiterando el proceso descrito, el vector quedará ordenado cuando solo se comparen los dos primeros elementos.
Partiendo de lo anteriormente planteado, realice lo siguiente:
Lea con atención el siguiente planteamiento: Caso 2:
a) Tomando en cuenta esta información y los datos de la Tabla No.1 del Objetivo 7, realizar un programa en Pascal que ordene los municipios en orden alfabético, aplicando el algoritmo de ordenamiento de la Burbuja.
b) Imprima el vector y nombre de los municipios.
Dada la tabla No.1 de los municipios del estado Trujillo.
Tabla No.1
Municipios del Estado Trujillo
Municipio
2 Andrés Bello
3 Boconó
4 Bolívar
6 Candelaria
8 Carache
1 Escuque
5 José Felipe Márquez Cañizales
9 Juan Vicente Campo Elías
7 La ceiba
10 Miranda
11 Monte Carmelo
12 Motatán
13 Pampán
14 Pampanito
15 Rafael Rangel
16 San Rafael de Carvajal
17 Sucre
18 Trujillo
19 Urdaneta
20 Valera
Desarrolle un programa en PASCAL, que construya una estructura tipo hashing o dispersión, para almacenar los nombres de los municipios por su posición dada en la tabla, en un archivo tipo texto. El programa se hará bajo las siguientes consideraciones:
• A través del archivo de texto, extraiga cada nombre de un municipio y ubíquelo en la estructura mencionada.
• Imprima el nombre del municipio a medida que lo inserta en la estructura y el número de la celda, para ello utilice una función de hashing,
Función hashing: consiste en la suma de las posiciones en el alfabeto de las letras (codificación ASCII) que conforman el nombre del estado. Como se indica a continuación:
N
f (nombre _ estado) = (∑ Li ) mod r ,
i =1
en donde Li es el código ASCII de cada letra que forma el nombre del jugador, r es el número de entradas de la tabla de hashing o número de buckets o slots. En este caso escoja un valor de r, el mejor será el que produce menor número de sinónimos. Las tablas de Codificación ASCII (también llamada asqui).
Ejemplo: si se va a construir la “llave” para una tabla de 200 slots( de
0 a 199), y se desea insertar el nombre Texas, de acuerdo a los códigos ASCII ( ver tabla ASCII), la construcción de la “llave” será la siguiente:
Valor = Cod(T) + Cod (e) + Cod (x) + Cod (a) + Cod (s) = 84 + 113 +
120 + + 97+115 = 1012
Valor mod r = 529 mod 199 = 131 (resto de la división entera)
Por lo tanto, la palabra Texas se insertará en una lista asociada a la celda (o slot) 131.
A continuación se presentan las tablas de caracteres ASCII
Símbolo Valor ASCII Símbolo Valor ASCII
A 65 N 78
B 66 O 79
C 67 P 80
D 68 Q 81
E 69 R 82
F 70 S 83
G 71 T 84
H 72 U 85
I 73 V 86
J 74 W 87
K 75 X 88
L 76 Y 89
M 77 Z 90
a 97 n 110
b 98 ñ 241
c 99 o 111
d 100 p 112
e 101 q 113
f 102 r 114
g 103 s 115
h 104 t 116
i 105 u 117
j 106 v 118
k 107 w 119
l 108 x 120
m 109 y 121
z 122
tabla ASCII
Nota: Para determinar el ordinal asociado a cada letra (código ASCII), se puede emplear la función ord, la cual pertenece al conjunto de funciones estándares de Pascal.
Fase 3 Del Trabajo
Elabore un procedimiento en Pascal de búsqueda, tal que, dados los nombres de los municipios, estos se busquen en la tabla de hashing e imprima la celda a la cual está asignada.
Instrucciones de como debe de quedar el trabajo
• Listado documentado del programa fuente. En el encabezado de cada procedimiento, función o sección de programa que lo requiera, debe incluir un breve comentario del proceso que se realiza o del método que aplica. Igualmente es conveniente hacerlo en la definición de las estructuras de datos y variables utilizadas.
• Listado de los resultados.
Recomendaciones
• Emplee nombres de variables, constantes, funciones y procedimientos alusivos a lo que representan.
• Utilice un diseño modular para la resolución del problema. Esta estructura aportará legibilidad y facilidad de comprensión, además evitará redundancias en los procesos. Evite variables globales en las funciones y procedimientos. Emplee parámetros en los mismos, determine cuáles son parámetros valor y cuáles parámetros variables.
• Desarrolle algoritmos eficientes.
• Elabore procedimientos de validación de la data y de detección de errores para evitar interrupciones inesperadas en la ejecución del trabajo.
Se considera logrado el objetivo si al menos se cumple con lo siguiente:
Entrega del listado documentado del programa, codificado en PASCAL, en forma modular y estructurada. En el encabezado de cada procedimiento, función o sección de programa que lo requiera y en la declaración de las estructuras de datos se incluye un breve comentario acerca del proceso, método o definición de estructura, según sea el caso.
Se elabore un programa para resolver el problema planteado en la parte 1. Las partes 2 y 3 se llevan a cabo en un sólo programa o en programas separados.
El programa corre sin restricciones. En general cada programa incluye módulos que realizan o contribuyen a alcanzar lo solicitado en las especificaciones.
Incluye las respuestas en las secciones solicitadas.
Entrega el listado de los resultados.
Esta Relación Expresada En Notacion Seria:
Figura Nro. 01
Tabla ASCII
Valora esta pregunta
0
