Fundamentos de Algoritmos y Estructuras de Datos

Materia: 27/08/2011

Definición de Problema

Problema: Situación anómala que requiere solución.

Ejemplo 1: Neumático Pinchado

Situación: Una persona viaja en su auto de Santiago a Viña, y en la mitad del camino pincha una rueda. (Problema principal)

Consideraciones:

• Es de día
• Tipo de camino
• Lleva herramientas
• Lleva rueda de repuesto

Pseudoalgoritmo: Secuencia de Pasos

Pseudoalgoritmo: Secuencia de pasos entendibles por todos.

1. Detener el vehículo.
2. Encender las luces de emergencia.
3. Bajarse del vehículo.
4. Verificar la falla.
5. Colocar el triángulo de seguridad.
6. Sacar herramientas y la rueda de repuesto.
7. Soltar los pernos.
8. Levantar el vehículo.
9. Sacar el neumático pinchado.
10. Poner el neumático bueno.
11. Poner los pernos.
12. Bajar el vehículo.
13. Apretar los pernos.

Ejemplo 2: Gotera en Casa

Situación: Un señor está sentado en el salón de su casa viendo la televisión. Afuera llueve intensamente.

Consideraciones:

• Hay una gotera en el techo del salón.
• La televisión no se ve bien.
• El suelo está mojado.
• El programa de televisión no es entretenido.

Pasos Lógicos:

1. Levantarse del sillón.
2. Ponerse los zapatos.
3. Verificar dónde está la gotera.
4. Buscar un balde.
5. Poner el balde en la gotera.
6. Buscar paños.
7. Secar el suelo.

Diagrama de Flujo: Símbolos Fundamentales

I

Inicio / Fin

Conector

Conector

Proceso / Paso / Instrucción

Proceso / Paso / Instrucción

Lectura / Salida de Datos

Lectura / Salida de Datos

Si / No

Decisión

Conector Fuera de Página

Conector Fuera de Página

Diagrama del Problema de la Gotera

(Representación visual de un diagrama de flujo con decisiones ‘Si’ y ‘No’ no incluida en el texto original, solo mención.)

Algoritmos Básicos y Variables

Algoritmo para Sumar Dos Números

Problema: Sumar dos números y entregar el resultado.

1. Inicio
2. Definir N1, N2, N3 (Variables)
3. Pedir Valor N1
4. Pedir Valor N2
5. Sumar N3 = N1 + N2
6. Mostrar N3
7. Fin

Variables: Tipos de Datos

• Numérico Entero: (Ej.: 10, 20, 30, 40)
• Alfanumérico: (Ej.: “Contenido”, “Juan”, “1”, “%”)
• Constante: (Ej.: IVA = 19%)
• Numérico con Decimales: (Ej.: 10.1, 1.2)

Conceptos Fundamentales

Dato

Símbolo que no tiene significado por sí mismo.

Información

Conjunto de datos procesados.

Diagrama de Contexto

Diagrama general de una situación puntual.

(Representación de suma de datos: 5, 10 + 5+10 = 15)

Algoritmo para Determinar Mayoría de Edad

Problema: De acuerdo a la edad de una persona, determinar si es mayor o menor de edad.

1. Inicio
2. Definir Variable Edad
3. Leer Edad
4. Si Edad >= 18
5. Mostrar “Mayor de 18”
6. Si no
7. Mostrar “Menor de Edad”
8. Fin SI
9. Término

(Símbolos de diagrama de flujo: Imprimir, Desplegar, Mostrar, Salida de Datos; Si/No)

Almacenamiento y Gestión de Datos

Conceptos de Almacenamiento

Dato

Unidad mínima de información (se almacena).

Campo

Espacio para almacenar un tipo específico de dato (se almacena).

Registro

Conjunto de varios campos relacionados.

Tabla / Planilla

Colección de registros.

Archivo

Colección de registros, identificado con un nombre. Puede ser sin clave de acceso o con clave de acceso.

Ejemplo de Registros en un Archivo

La capacidad de un archivo depende de la capacidad del HDD.

01/09/2011

Ejemplo 1: Cálculo de Salario

Problema: Dada la cantidad de horas de un trabajador y el valor por hora, calcular su salario e imprimir.

Archivo

Entidad.

Base de Datos

Conjunto de archivos relacionados.

Estructura de Datos para Boletas

Ejemplo de Datos de Boleta

Ejemplo 2: Cálculo de Descuento

Problema: Dado un monto, calcular el descuento considerando lo siguiente:

• Si el monto es mayor a 1000, el descuento es del 10%.
• Si el monto es menor o igual a 1000, el descuento es del 2%.
• Mostrar el valor del descuento.

Algoritmo para el Ejercicio 1 (Salario)

1. Inicio
2. Definir Variables: Hora, Valor-Hora, Sueldo
3. Leer Hora, Valor-Hora
4. Calcular Sueldo = Hora * Valor-Hora
5. Mostrar Sueldo
6. Fin

Algoritmo para el Ejercicio 2 (Descuento)

1. Inicio
2. Definir Variables: Monto, Dcto10 = 0.1, Dcto2 = 0.02, Mdcto
3. Leer Monto
4. Si Monto > 1000
5. Mdcto = Monto * Dcto10
6. Si No
7. Mdcto = Monto * Dcto2
8. Fin Si
9. Mostrar Mdcto
10. Terminar

(Símbolos de diagrama de flujo: Si/No)

Conceptos Avanzados de Algoritmos

Análisis de Traza

Análisis de Traza: Sirve para revisar el algoritmo paso a paso.

03/09/2011

Ciclos e Iteraciones

Ciclo / Iteración: Réplica de un proceso N veces.

Concepto de Ciclo

Mientras (condición)
  Proceso
Fin Mientras

Desde Variable = 1 Hasta 5
  Proceso
Fin Desde

Conceptos Clave

Contador

Variable que sirve para contar la cantidad de veces que se realiza algo.

Acumulador

Variable que acumula un resultado.

Algoritmo con Ciclo y Análisis de Traza

Algoritmo:

1. Inicio
2. Definir Monto, Valor-Dcto, Contador
3. Contador = 0
4. Mientras Contador < 5
5. Contador = Contador + 1
6. Leer Monto
7. Si Monto > 1000
8. Valor-Dcto = Monto * 0.1
9. Si no
10. Valor-Dcto = Monto * 0.02
11. Fin Si
12. Mostrar Valor-Dcto.
13. Fin Mientras
14. Terminar

Análisis de Traza:

Aquí se muestra cómo quedan las variables después de cada iteración.

Procesamiento de Archivos con Ciclos

(Valores de ejemplo para el archivo de montos: 1: 400, 2: 700, 3: 2000, 4: 3000, 5: 0)

1. Abrir Archivo Montos
2. Definir Valor-Dcto.
3. Mientras No EOF (Montos)
4. Leer Monto(Montos)
5. Si Monto(montos) > 1000
6. Valor-Dcto = Monto(montos) * 0.1
7. Si no
8. Valor-Dcto = Monto(montos) * 0.02
9. Fin SI
10. Mostrar Valor-Dcto
11. Fin Mientras
12. Cerrar Montos
13. Terminar

Tipos de Estructuras Condicionales

1. Simples

Si (condición)
  Instrucción
Fin Si

(Representación de diagrama de flujo: Si / No)

2. Dobles (Si-Sino)

Si (condición)
  Instrucción 1
Si No
  Instrucción 2
Fin Si

3. Anidadas

Si (condición 1)
  Si (condición 2)
    Si (condición 3)
      Instrucción A
    Fin SI
  Fin Si
Fin Si

Si (condición X)
  Instrucción 1
Si No
  Si (condición Y)
    Instrucción 2
  Fin Si
Fin Si

Algoritmo de Acumulación con Traza

(Valores ingresando al flujo de datos)

1. Inicio
2. Definir Contador = 0, Valor, Total = 0
3. Mientras Contador < 5
4. Leer Valor
5. Contador = Contador + 1
6. Total = Total + Valor
7. Fin Mientras
8. Mostrar Total
9. Terminar

Análisis de Traza:

(Símbolos de diagrama de flujo: Si / No)

Procesamiento de Notas de Estudiantes

Archivo de Notas

Requerimientos del Algoritmo de Notas

1. Recorrer el archivo de notas de principio a fin y, por cada alumno, calcular el promedio de notas. Por cada registro leído, imprimir o mostrar el Nombre, Nota1, Nota2, Nota3 y el promedio.
2. Incorporar al algoritmo anterior lo siguiente: Determinar o encontrar el alumno cuyo promedio es el mayor e imprimirlo una vez que finalice el programa.

Algoritmo para Procesar Notas

1. Inicio
2. Abrir Notas
3. Definir Promedio = 0, Pmayor = 0, Nmayor = “”
4. Leer Primer Registro de Notas
5. Mientras No EOF(Notas)
6. Promedio = (Nota1 + Nota2 + Nota3) / 3
7. Imprimir Nombre, Nota1, Nota2, Nota3, Promedio
8. Si Promedio > Pmayor
9. Mover Promedio a Pmayor
10. Mover Nombre a Nmayor
11. Fin SI
12. Leer Siguiente Registro de Notas
13. Fin Mientras
14. Imprimir Nmayor, Pmayor
15. Cerrar Archivo
16. Fin

Instrucción: Realizar Diagrama de Flujo del Algoritmo Anterior.

10/09/2011

Procesamiento de Ventas y Productos

Información Requerida de Archivos

Dados los siguientes archivos, se requiere obtener la siguiente información:

• Cantidad total por producto vendido.
• Total de ventas por producto.

Archivo de Productos

Archivo de Ventas

Algoritmo para Procesar Ventas por Producto

1. Inicio
2. Definir Cproducto = 0, Tvta = 0
3. Abrir Archivos Productos, Ventas
4. Leer Primer Registro de Productos
5. Mientras No EOF(Productos)
6. Leer Primer Registro de Ventas (Reiniciar lectura de Ventas para cada producto)
7. Mientras No EOF (Ventas)
8. Si Producto.codigo = Ventas.Codigo
9. Cproducto = Cproducto + Ventas.cantidad
10. Tvta = Tvta + (Ventas.cantidad * Producto.precio)
11. Fin Si
12. Leer Siguiente Registro de Ventas
13. Fin Mientras
14. Mostrar Producto.codigo, Producto.Descripcion, Cproducto, Tvta
15. Leer Siguiente Registro de Productos
16. Cproducto = 0, Tvta = 0 (Reiniciar contadores para el siguiente producto)
17. Fin Mientras
18. Cerrar Archivos Productos, Ventas
19. Fin

Instrucción: Desarrollar Diagrama de Flujo del Algoritmo Anterior.

Conceptos de Estructura de Archivos

Archivo

Contiene Registros.

Registro

Contiene Campos.

Campos

Contienen Datos.

Proyecto de Automatización de Librería

Descripción del Proyecto

Un matrimonio con capital decide invertir en una cadena de locales cuyo objetivo será vender o distribuir libros, diarios, revistas, enciclopedias, golosinas, etc. Actualmente, toda la administración se realiza de manera manual. La inversión incluye la adquisición de computadores e impresoras para automatizar los procesos.

Administración Manual Actual

• Registro de Clientes (en libros físicos)
• Registro de Productos (en libros físicos)
• Registro de Ventas (en libros físicos)
• Registro de Compras (en libros físicos)

Requerimientos del Proyecto

1. Confeccionar un Diagrama de la Situación Actual.
2. Confeccionar un Diagrama de la Situación Propuesta.
3. Definir archivos, registros, campos y datos para lo que se requiere en la nueva situación.
4. Construir algoritmos y/o diagramas de flujo para dar solución a los siguientes requerimientos:

Requerimientos Específicos:

• Cantidad total y valor total de cada producto vendido.
• Cantidad total y valor total de todos los productos vendidos.
• Implementar un proceso que indique cuál es el cliente que más compra.

15/09/2011

Ejercicios Prácticos de Algoritmos

Ejercicio 1: Emisión de Factura

Problema: Escribir un algoritmo que permita emitir la factura correspondiente a la compra de un artículo determinado, del que se adquiere una o varias unidades. El IVA es del 19%, y si el precio BRUTO (Precio de Venta + IVA) es mayor a $13.000, se debe realizar un descuento del 5%.

Salida Requerida:

• Precio por Número de Artículos
• IVA
• Descuento (DCTO)
• TOTAL

Instrucción: Hacer Algoritmo.

15/09/2011

Ejercicio 2: Análisis de Notas de Estudiante

Problema: Dado “N” notas de un estudiante, calcular:

• Cuántas notas tiene reprobadas.
• Cuántas notas tiene aprobadas.
• Promedio de todas las notas.
• Promedio de notas reprobadas.
• Promedio de notas aprobadas.

Instrucción: Construir Algoritmo.

Estructura de Datos Avanzadas

Arreglos (Listas)

Arreglo: Lista de datos del mismo tipo.

• Arreglo Alfanumérico
• Arreglo Numérico

La forma de realizar la búsqueda de un dato es mediante un índice.

Índice

Variable numérica, generalmente nombrada I.

Ejemplo de Búsqueda en Arreglo:

Índice = 1
Mientras Índice <= 5
  Si Arreglo(Índice) = "susy"
    Imprimir "Encontrada"
  Fin Si
  Índice = Índice + 1
Fin Mientras

El arreglo se lee secuencialmente hasta encontrar lo solicitado o realizar algún quiebre.

Matrices

Matriz Unidimensional

Es similar al arreglo, pero la diferencia es que pueden contener distintos tipos de datos.

Representación de Posiciones:

Posición:
  1           2           3

Cómo se leen los elementos:

• N1 (Índice)
• N2 (Índice)
• N3 (Índice)
• N4 (Índice)
• N5 (Índice)

Matriz Bidimensional

Poseen columnas y filas.

Representación:

    1C    2C
1F
2F

Para buscar se lee de la siguiente forma:

• N1 (Fila, Columna)
• N2 (Fila, Columna)