Algoritmos II ingenieria de sistemas



Descargar 98.81 Kb.
Fecha de conversión16.01.2017
Tamaño98.81 Kb.

ALGORITMOS II
INGENIERIA DE SISTEMAS
FACULTAD DE CIENCIAS BÁSICAS E INGENIERÍA


c:\users\mario.palacios\dropbox\remington\imacorp uniremington\logo uniremington uso vertical sobre blanco o tonos claros.png

El módulo de estudio de la asignatura Algoritmos II es propiedad de la Corporación Universitaria Remington. Las imágenes fueron tomadas de diferentes fuentes que se relacionan en los derechos de autor y las citas en la bibliografía. El contenido del módulo está protegido por las leyes de derechos de autor que rigen al país.

Este material tiene fines educativos y no puede usarse con propósitos económicos o comerciales.

AUTOR

José Antonio Polo

Ingeniero de sistemas de la Universidad de Antioquia Especialista en finanzas de la Corporación Universitaria Remington y estudiante de maestría en educación de la universidad Cesun (Tijuana México). Participación del tercer Congreso Colombiano de Computación – 3CCC de la universidad EAFIT Participación del primer simposio en Inteligencia Artificial de la Corporación Universitaria Remington Participación del IV Congreso Internacional de Software Libre GNU/Linux, Universidad de Manizales Participación del 5º Congreso Nacional de Redes y Telemática, Redes de Servicios Móviles Integrados, Centro de Construcción de Conocimiento Evento CCC Docente de cátedra del politécnico Jaime Isaza Cadavid Docente de cátedra del Tecnológico de Antioquia Participación del proyecto de la articulación de la media técnica del Tecnológico de Antioquia Docente de la Corporación Universitaria Remington.



Barra5111@yahoo.es
Nota: el autor certificó (de manera verbal o escrita) No haber incurrido en fraude científico, plagio o vicios de autoría; en caso contrario eximió de toda responsabilidad a la Corporación Universitaria Remington, y se declaró como el único responsable.
RESPONSABLES

Jorge Mauricio Sepúlveda Castaño

Decano de la Facultad de Ciencias Básicas e Ingeniería



jsepulveda@uniremington.edu.co
Eduardo Alfredo Castillo Builes

Vicerrector modalidad distancia y virtual



ecastillo@uniremington.edu.co
Francisco Javier Álvarez Gómez

Coordinador CUR-Virtual



falvarez@uniremington.edu.co
GRUPO DE APOYO

Personal de la Unidad CUR-Virtual

EDICIÓN Y MONTAJE



Primera versión. Febrero de 2011.

Segunda versión. Marzo de 2012

Tercera versión. noviembre de 2015


Derechos Reservados

Esta obra es publicada bajo la licencia Creative Commons.


Reconocimiento-No Comercial-Compartir Igual 2.5 Colombia.


TABLA DE CONTENIDO

Pág.


1MAPA DE LA ASIGNATURA 4

2UNIDAD 3 MANEJO DE HILERAS DE CARACTERES 6

RELACIÓN DE CONCEPTOS 6

2.1TEMA 1 DEFINICIÓN 8

2.2TEMA 2 OPERACIONES CON HILERAS 9

ASIGNACIÓN 9

FUNCIÓN LONGITUD 10

FUNCIÓN SUBHILERA 10

FUNCIÓN CONCATENAR 10

MÉTODO INSERTAR 10

MÉTODO BORRAR 11

MÉTODO REEMPLAZAR 11

FUNCIÓN POSICIÓN 11

2.3TEMA 3 EJERCICIOS DE APLICACIÓN 13

APLICACIÓN DE LA CLASE HILERA 13

EJERCICIOS ENTRENAMIENTO 19

3PISTAS DE APRENDIZAJE 20

4GLOSARIO 21



5BIBLIOGRAFÍA 22


1MAPA DE LA ASIGNATURA



2UNIDAD 3 MANEJO DE HILERAS DE CARACTERES




Programación en C - MANEJO DE CADENAS - Parte 1: Enlace

RELACIÓN DE CONCEPTOS




Hileras: Es un tipo de dato construido con base al tipo primitivo char.

Asignación: Consiste en asignarle a una variable una hilera de caracteres.

Longitud: Consiste en verificar la cantidad de caracteres de la cual se compone la hilera.

Subhilera: Parte que se toma de una hilera.

Concatenar: Consiste en unir una hilera a partir de otra.

Posición: Consiste en determinar, a partir de cual posición de una hilera x, se encuentra una hilera y; si es que se encuentra.

Insertar: Este método consiste en insertar una hilera x, a partir del carácter i, de la hilera y.

Borrar: Este método consiste, a partir de la posición i de la hilera x, borra j caracteres.

Reemplazar: Este método consiste que a partir de la posición i de la hilera x, reemplaza j caracteres por una copia de la hilera y.

2.1TEMA 1 DEFINICIÓN


Las hileras es un objeto de datos compuestos, construidos con base en el tipo primitivo char, su mayor aparición fue cuando empezaron a aparecer los procesadores de textos.

2.2TEMA 2 OPERACIONES CON HILERAS


Las operaciones que podemos hacer con cadenas son las operaciones de asignación, longitud, subhilera, concatenar, insertar, borrar, reemplazar y posición en una cadena.
Consideremos ahora las operaciones básicas que se pueden ejecutar con hileras. Definamos una clase hilera con sus operaciones:

  1. CLASE Hilera

  2. Publico

  3. entero longitud ()

  4. hilera subHilera (entero i, entero j)

  5. hilera concat (hilera s)

  6. void inserte (hileras, entero j)

  7. void borre (entero i, entero j)

  8. void replace (entero i, entero j, hilera s)

  9. entero posición (hilera s)

  10. end(Clase)


ASIGNACIÓN


En el lado izquierdo tendremos el nombre de la variable a la cual se le asigna una hilera dada. En el lado derecho se tendrá una hilera o una variable tipo hilera. Por ejemplo, si S, T, U y V son variables tipo hilera podemos tener las siguientes instrucciones:

S = “abc”

T = “def.”

U = T

V = “”

En el primer ejemplo la variable S contendrá la hilera “abc”.

En el segundo ejemplo la variable T contendrá la hilera “def”.

En el tercer ejemplo la variable U contendrá la hilera “def”.

En el cuarto ejemplo la variable V contendrá la hilera vacía.

FUNCIÓN LONGITUD


Forma general: longitud(S)

Esta función retorna el número de caracteres que tiene la hilera S. por ejemplo, si tenemos S = “mazamorra” y ejecutamos la instrucción:



n = S. longitud ()

La variable n quedara valiendo 9.


FUNCIÓN SUBHILERA


Forma general: T = S. subHilera (i, j), con 1 ≤ i ≤ i + j – 1 ≤ n

Siendo n la longitud de la hilera S.

Esta función, a partir de la posición i de la hilera S, extrae j caracteres creando una nueva hilera y dejando intacta la hilera original S. por ejemplo, si tenemos S = “mazamorra” y ejecutamos la instrucción:

T = S. subHilera (4, 5)

La variable T quedara valiendo “amorr”.

FUNCIÓN CONCATENAR


Forma general: U = S. Concat(T)

Esta función crea una copia de la hilera S y a continuación agrega una copia de la hilera T. las hileras S y T permanecen intactas. Por ejemplo, si S = “nacio” y T “nal” y ejecutamos la instrucción:



U = S. concat(T)

La variable U quedara conteniendo la hilera “nacional”.


MÉTODO INSERTAR


Forma general: S. inserte (T, i)

Este método inserta la hilera T a partir del carácter de la posición i de la hilera S. por ejemplo, si tenemos S = “nal” y T = “ciona” y ejecutamos la instrucción:



S. inserte (T, 3)

La hilera S quedara valiendo “nacional”.

Es necesario resaltar que en este caso la hilera S queda modificada mientras que la hilera T permanece intacta.

MÉTODO BORRAR


Forma general: S. borre (i, j)

Este método, a partir de la posición i de la hilera S borra j caracteres. Por ejemplo, si S = “amotinar” y ejecutamos la instrucción:



S. borre (4, 4)

La hilera S quedara valiendo “amor”.

Es bueno anotar también que la hilera S queda modificada.

MÉTODO REEMPLAZAR


Forma general: S. replace (i, j, T)

Este método, a partir de la posición i de la hilera S reemplaza j caracteres por una copia de la hilera T. por ejemplo, si la hilera S = “abcdf” y la hilera T = “xyz” y ejecutamos la instrucción:



S. replace (3, 2, T)

La hilera S quedara valiendo “abxyzef”.

Este método modifica la hilera S, mientras que la hilera T permanece intacta.

FUNCIÓN POSICIÓN


Forma general: m = S. Posición(T)

Esta función determina a partir de cual posición de la hilera S se encuentra la hilera T, si es que se encuentra la hilera T en la hilera S. en caso de no encontrar la hilera T en la hilera S retornara cero. Por ejemplo, si S = “mazamorra” y T = “amor” y ejecutamos la instrucción:



m = posición(T)

La variable m quedara valiendo 4.

Las operaciones aquí descritas nos proporcionan las facilidades para manipular hileras en cualquier lenguaje de programación. Es importante agregar que lenguajes de programación como C++ y java traen definida la clase hilera (String) en la cual se implementa una gran cantidad de variaciones correspondientes a estas operaciones.

2.3TEMA 3 EJERCICIOS DE APLICACIÓN


Con las operaciones mencionadas en el numeral anterior, se pueden realizar muchos ejemplos de aplicación, por ejemplo: cuando se tiene un texto y se solicita determinar cuál es la frecuencia de cada una de las letras del alfabeto español, es decir, cuantas veces aparece la letra “p”, cuantas veces aparece la letra “o” y así sucesivamente.

APLICACIÓN DE LA CLASE HILERA


Pasemos a considerar ejemplos de aplicación con las funciones anteriormente definidas.

Empecemos considerando un ejercicio en el cual nos solicitan determinar cuál es la frecuencia de cada una de las letras del alfabeto español en un determinado texto dado, es decir, cuantas veces se aparece la “a” cuantas veces aparece la “b” y así sucesivamente.

Llamemos texto la variable en la cual hay que hacer dicha evaluación. Para desarrollar dicho método utilizaremos una variable llamada alfabeto, que es una variable tipo hilera y que definiremos así:

alfabeto = “abcdefghijklmnñopqrstuvwxyz”

Utilizaremos un vector de 27 posiciones, que llamaremos frecuencia, en cada una de las cuales guardaremos el número de veces que se encuentre alguna letra del alfabeto definido. Es decir, a la letra “a” le corresponde la posición 1 del vector de frecuencias, a la letra “b” la posición 2, a la letra “c” la posición 3 y así sucesivamente.

Nuestro método consistirá en recorrer los caracteres de la variable texto, buscando cada carácter en la variable alfabeto utilizando la función posición; cuando la encuentre sumaremos 1 a la posición correspondiente a esa letra en el vector de frecuencia.

Nuestro método es:



  1. void frecuencia Letras (hilera alfabeto)

  2. entero m, i, j, n

  3. hilera car

  4. m = alfabeto. longitude ()

  5. for (i = 1; i <= m; i++) do

  6. frecuencia[i] =0

  7. end(for)

  8. n = longitud ()

  9. for (i = 1; 1 <= n; i++) do

  10. car = subHilera (i, 1)

  11. j = alfabeto. posicion(car)

  12. if (j!= 0) then

  13. frecuencia[j] = frecuencia[j] + 1

  14. end(if)

  15. end(for)

  16. for (i = 1; i <= m; i++) do

  17. letra = alfabeto. SubHilera (i, 1)

  18. write (letra, frecuencia[i])

  19. end(for)

  20. end(Método)

Consideremos ahora un método en el cual nos interesa determinar la frecuencia de cada palabra que aparezca en un texto. Para desarrollar dicho método debemos, primero que todo, identificar cada una de las palabras del texto. Para lograr esta identificación hay que definir cuáles caracteres se utilizan como separadores de palabras. Estos caracteres pueden ser cualquier símbolo diferente de letra, es decir, la coma, el punto, el punto y coma, los dos puntos, el espacio en blanco, etc.

Nuestro método manejara las siguientes variables:



VARIABLES

CARACTERÍSTICAS

TEXTO

Variable en la cual se halla almacenado el texto a procesar.

PALABRAS

Variables tipo vector en la cual almacenaremos cada palabra que se identifique en el texto.

FRECUENCIA

Variable tipo vector en la cual almacenaremos el número de veces que se encuentre cada palabra del texto. Una palabra que se encuentre en la posición i del vector palabra, en la posición i del vector frecuencia se hallara el número de veces que se ha encontrado.

PALABRAHALLADA

Variable en la cual almacenaremos cada palabra que se identifique en el texto.

K

Variable para contar cuantas palabras diferentes hay en el texto. La inicializamos en 1. El total de las palabras diferentes encontradas será k – 1.

N

Variable que guarda el número de caracteres en el texto.

ALFABETO

Es una hilera enviada como parámetros, la cual contiene los símbolos con los cuales se construyen las palabras.

Nuestro

método es el siguiente:



  1. void frecuencia Palabras (hilera alfabeto)

  2. entero i, k, j, p, n, frecuencia [1000]

  3. hilera car, palabras [1000]

  4. k = 1

  5. for (i = 1; i <= 1000; i++) do

  6. frecuencia[i] = 0

  7. end(for)

  8. n = longitud ()

  9. i = 1

  10. while i <= n do

  11. car = subHilera (i, 1)

  12. p = alfabeto. posicion(car)

  13. while (i < n and p == 0) do

  14. i = i + 1

  15. car = subHilera (i, 1)

  16. p = alfabeto. posicion(car)

  17. end(while)

  18. j = i

  19. while (i < n and p != 0) do

  20. i = i + 1

  21. car = subHilera (i, 1)

  22. p = alfabeto. posicion(car)

  23. end(while)

  24. palabra Hallada = subHilera (j, i - j)

  25. palabras[k] = palabra Hallada

  26. j = 1

  27. while (palabras[j] != palabra Hallada) do

  28. j = j + 1

  29. end(while)

  30. if (j == k) then

  31. frecuencia[k] = 1

  32. k = k + 1

  33. else

  34. frecuencia[j] = frecuencia[j] + 1

  35. end(if)

  36. end(while)

  37. k = k – 1

  38. for (i = 1; i <= k; i++) do

  39. write(palabras[i], frecuencia[i])

  40. end(for)

  41. end(Método)

En la instrucción 2 y 3 se definen las variables con las cuales se va a trabajar.

En las instrucciones 5 a 7 se inicializan los contadores de palabras en 0.

En las instrucciones 8 se determina la longitud del texto a analizar (el que invoco el método).

En la instrucción 9 se inicializa la variable i en 1. Utilizamos la variable i para recorrer el texto, carácter por carácter, e ir identificando las diferentes palabras en él.

Las instrucciones 10 a 36 conforman el ciclo principal del método.

En las instrucciones 11 a 17 se omiten los caracteres que no conforman una palabra valida. Los caracteres que conforman una palabra valida son los que pertenecen al alfabeto. Cada carácter del texto se busca en la hilera alfabeto (instrucciones 12 y 16): si no lo encuentra significa que no conforma palabra y por lo tanto se desecha. Del ciclo de las instrucciones 13 a 17 se sale cuando encuentre un carácter que pertenezca al alfabeto. Esto significa que a partir de esa posición comienza una palabra. Dicha posición la guardaremos en una variable que llamamos j (instrucción 18).

En el ciclo de las instrucciones 19 a 23 se determinan hasta cual posición llega una palabra de este ciclo se sale cuando encuentre un carácter que no pertenezca al alfabeto; por consiguiente, la palabra será la subhilera desde la posición j hasta la posición i – 1, la cual extrae con la instrucción 24.

En la instrucción 25 se almacena la palabra hallada en la posición k del vector palabras. Con el fin de determinar si la palabra almacenada en la posición k del vector es primera vez que aparece o ya estaba, la buscamos en el vector de palabras (instrucciones 26 a 29) con la certeza de que la encontraremos: si se encuentra en la posición k significa que es la primera vez que aparece y por lo tanto le asignamos 1 al contador de esa palabra (instrucción 31) e incrementamos la variable k en 1; si encontró la palabra en una posición diferente a la posición k significa que dicha palabra ya se había encontrado y por lo tanto incrementamos su respectivo contador en 1 (instrucciones 34).

Por último, en las instrucciones 37 a 40 se describen las diferentes palabras encontradas con su respectivo contador.

Planteemos ahora un logaritmo que considero interesante: reemplazar una palabra por otra en un texto dado.

Utilizaremos tres variables:


VARIABLES

CARACTERÍSTICAS

TEXTO

Variable que contiene el texto donde hay que hacer el reemplazo.

VIEJA

Variable que contiene la hilera que hay que reemplazar.

NUEVA

Variable que contiene la hilera que reemplazara la hilera vieja.

Para entender el desarrollo de este método debemos entender lo siguiente: si tenemos un texto S = “aabcdabcde” y T = “abc” y ejecutamos la instrucción

m = S. Posición(T)

La variable m queda valiendo 2. Esto significa que a partir de la posición 2 de la hilera S se encontró la hilera T, es decir, nuestro método retorna el sitio donde encuentra la primera ocurrencia de la hilera que se está buscando. Fíjese que en nuestra hilera S la hilera “abc” se halla en la posición 2 y en la 6.

Si ejecutamos la siguiente instrucción (fíjese que se está buscando la hilera T a partir de la posición 5 de S):

m = S. subHilera (5, 6). posición(T) (formula 1)

La variable m también queda valiendo 2. ¿Por qué? La razón es que la hilera T la buscara en la hilera S. subHilera (5, 6), la cual es: “babcde”.

La pregunta es: ¿está realmente la segunda ocurrencia de la hilera T en la posición 2 de S? la respuesta es no.

Si planteamos una utilización de la función posición como en la fórmula 1 y queremos determinar en cual posición de S comienza la subhilera T, al resultado obtenido habrá que sumarle i – 1, siendo i el primer parámetro de la función subHilera. En nuestro caso i = 5.

Llamemos posini la variable a partir de la cual se inicia la búsqueda de una hilera en una subhilera obtenida con la función subhilera.

Nuestro método es:



  1. void reemplazarViejaPorNueva(hilera vieja, hilera nueva)

  2. v = vieja. Longitud()

  3. n = nueva. Longitud ()

  4. t = longitud ()

  5. posini = 1

  6. sw = 1

  7. while (sw == 1) do

  8. p = subHilera (posini, t – posini + 1)

  9. posvieja = p. posición(vieja)

  10. if (posvieja > 0) then

  11. posreal = posvieja + posini – 1

  12. replace (posreal, v, nueva)

  13. posini = posreal + n + 1

  14. t = longitud ()

  15. if (posini > t + v 1) then

  16. sw = 0

  17. end(if)

  18. else

  19. sw = 0

  20. end(if)

  21. end(while)

  22. end(Método)


EJERCICIOS ENTRENAMIENTO


Pautas para desarrollar los siguientes ejercicios: Para desarrollar estos ejercicios debe tener en cuenta, todas las funciones y métodos vistos en el tema. Recuerda que, puedes utilizar una estructura tipo vector o una estructura lista ligada; si lo requiere, para dar solución a los problemas.

  1. Elabore un método para determinar si una hilera dada constituye un palíndromo o no. Un palíndromo es una hilera que se lee igual de izquierda a derecha que de derecha a izquierda; por ejemplo: radar, reconocer, Abba. Su método debe retornar verdadero si cumple la condición, falso de lo contrario.

  2. Elabore un método que determine si una palabra tiene más vocales que consonantes o no. Su método debe retornar verdadero si cumple la condición; de lo contrario, debe retornar falso.

  3. Elabore un método que invierta todos los caracteres de una hilera dada. Por ejemplo, si la hilera es “amor”, al ejecutar su método debe quedar la hilera “roma”.

  4. Elabore un método que determine si una palabra tiene las cincos vocales o no. Su método debe retornar verdadero si cumple la condición; de lo contrario, debe retornar falso.


3PISTAS DE APRENDIZAJE


Recuerde que, a la hora de intercambiar datos dentro de un vector de registro, primero debe guardar el contenido en una celda a dentro de una variable auxiliar, para no perder lo que hay en a; luego a la celda a le lleva lo que tiene la celda b; y por último, a la celda b le lleva lo que guardó en la variable auxiliar. Así, por ejemplo:

aux = vec[i] vec[i] = vec[k] vec[k] = aux



Recuerde que los parámetros por referencia son aquellas variables que se modificarán dentro de los métodos y volverán al programa principal con su valor modificado.

Recuerde que la información que se guarda en archivos, es una información que permanece en el tiempo.

No olvide que los archivos se deben de abrir y también se deben cerrar.

Tenga en cuenta los siguientes puntos en el manejo dinámico de memoria:

El puntero es una dirección de memoria en la RAM.

Un nodo es un espacio de memoria.

Un nodo simple, está compuesto por una parte de dato y otra parte de liga.



Recuerde que al pedir un nodo se hace con la instrucción new(x) y para liberar el espacio de memoria se hace con free(x).

No olvide que las pilas y las colas, no tienen representación propia a nivel de programación, que para hacerlo se apoyan en vectores y listas ligadas.

Tenga en cuenta que cuando se busca el contador de frecuencias de un algoritmo, y en éste hay una instrucción que se ejecuta n*n veces, lo representamos como n2; y si existe una instrucción que se ejecuta n*n*n veces, ésta instrucción la representamos como n3.

Recuerde que, en la multiplicación, tener 2*n es lo mismo que tener 2n.

Igualmente, con los logaritmos: n*log2n es lo mismo que nlog2n.


4GLOSARIO


Factorial: Se llama factorial de n al producto de todos los números naturales desde 1 hasta n.

Frecuencia: Repetición mayor o menor de un acto o de un suceso.

Parámetro: Variable que, en una familia de elementos, sirve para identificar cada uno de ellos mediante su valor numérico

Void: Significa vacío, esto indica que la función no devuelve nada si no que realiza ciertas acciones.

Pila: conjunto de uno o más elementos que se apilan.

Nodo simple: espacio de memoria que tiene una dirección y que se encuentra dividido en dos partes, una parte de dato y una parte de liga.

Nodo doble: espacio de memoria que tiene una dirección y que se encuentra dividido en tres partes una parte de liga izquierda, una parte de liga derecha y una parte de datos.

Evaluación a priori: consiste en medir la eficiencia de un algoritmo antes de decodificarse en algún lenguaje

5BIBLIOGRAFÍA

Joyanes Aguilar, L. (1996). Fundamentos de programación: Algoritmos y estructura de datos. McGraw Hill/Interamericana de España S.A.


Oviedo Regino, E. M. (2015). Lógica de programación orientada a objeto, primera edición. ECOE ediciones: Bogotá.

Villalobos S., J. A., & Casallas G., R. (2006). Fundamentos de programación, aprendizaje activo basado en casos primera edición. Bogotá: Pearson educación de México S.A. de C.V.

Cairo, O., & Guardati Buemo, S. (1998). Estructuras de datos. McGraw-Hill Interamericano de México S.A.
Roberto Flórez Rueda. (2010). Algoritmia II, primera edición. Medellín Colombia.
Programación en Castellano. (s.f.). Recuperado el 9 de Junio de 2011, de http://www.programacion.com/articulo/introduccion_a_la_programacion_205/7
Universidad Nacional de Colombia sede Bogotá. (s.f.). Recuperado el 8 de Abril de 2011, de http://www.virtual.unal.edu.co/cursos/ingenieria/2001839/docs_curso/contenido.html

Canaria, D. d. (s.f.). Grupo de Estructuras de Datos y Lingüística Computacional. Recuperado el 6 de Junio de 2011, de http://www.gedlc.ulpgc.es/docencia/NGA/subprogramas.html


Granada, U. d. (s.f.). www.ugr.es. Recuperado el 9 de Junio de 2011, de
http://elvex.ugr.es/decsai/c/apuntes/vectores.pdf
TECNOLÓGICO. (s.f.). Obtenido de http://www.mitecnologico.com/:
http://www.mitecnologico.com/Main/ArreglosVectoresYMatrices
Universidad Tecnológica de Pereira. (s.f.). Recuperado el 6 de Junio de 2011, de http://www.utp.edu.co/~chami17/sn.htm
Vieyra, G. E. (31 de Agosto de 2000). Facultad de Ciencias Físico-Matemáticas UMSNH. Recuperado el 8 de Junio de 2011, de http://www.fismat.umich.mx/~elizalde/curso/node110.html
Wikipedia. (s.f.). Recuperado el 8 de Junio de 2011, de
http://es.wikipedia.org/wiki/Sistema_de_numeraci%C3%B3n


La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal