El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Implementación de Algoritmos

Siguiente ►
►

En este módulo, aprenderemos cómo implementar algoritmos en ALGOL. Los algoritmos son la base de la programación y son esenciales para resolver problemas de manera eficiente. Este módulo cubrirá varios tipos de algoritmos, desde los más básicos hasta los más avanzados, y proporcionará ejemplos prácticos y ejercicios para reforzar el aprendizaje.

Contenido

  1. Introducción a los Algoritmos
  2. Algoritmos de Búsqueda
  3. Algoritmos de Ordenamiento
  4. Algoritmos de Recursión
  5. Ejercicios Prácticos
  6. Conclusión

Introducción a los Algoritmos

Un algoritmo es una secuencia finita de instrucciones bien definidas y no ambiguas que, al ser ejecutadas, resuelven un problema específico. Los algoritmos son fundamentales en la programación y se utilizan en una amplia variedad de aplicaciones.

Características de un Buen Algoritmo

  • Claridad: Las instrucciones deben ser claras y fáciles de entender.
  • Eficiencia: El algoritmo debe utilizar los recursos de manera óptima.
  • Finitud: El algoritmo debe terminar después de un número finito de pasos.
  • Entrada y Salida: Debe tener entradas bien definidas y producir salidas correctas.

Algoritmos de Búsqueda

Búsqueda Lineal

La búsqueda lineal es el algoritmo más simple para encontrar un elemento en una lista. Se recorre la lista secuencialmente hasta encontrar el elemento deseado o hasta que se haya recorrido toda la lista.

begin
  integer array[1:10];
  integer i, n, key, position;
  boolean found;

  ! Inicializar el arreglo
  for i := 1 step 1 until 10 do
    array[i] := i * 2;

  ! Leer el valor a buscar
  read(key);

  ! Inicializar variables
  found := false;
  position := 0;

  ! Búsqueda lineal
  for i := 1 step 1 until 10 do
    if array[i] = key then
      found := true;
      position := i;
      exit;

  ! Mostrar el resultado
  if found then
    print("Elemento encontrado en la posición: ", position);
  else
    print("Elemento no encontrado");

end;

Búsqueda Binaria

La búsqueda binaria es un algoritmo más eficiente que la búsqueda lineal, pero requiere que la lista esté ordenada. Divide la lista en dos partes y compara el elemento buscado con el elemento central.

begin
  integer array[1:10];
  integer low, high, mid, key;
  boolean found;

  ! Inicializar el arreglo (debe estar ordenado)
  for i := 1 step 1 until 10 do
    array[i] := i * 2;

  ! Leer el valor a buscar
  read(key);

  ! Inicializar variables
  low := 1;
  high := 10;
  found := false;

  ! Búsqueda binaria
  while low <= high do
    mid := (low + high) div 2;
    if array[mid] = key then
      found := true;
      exit;
    else if array[mid] < key then
      low := mid + 1;
    else
      high := mid - 1;

  ! Mostrar el resultado
  if found then
    print("Elemento encontrado en la posición: ", mid);
  else
    print("Elemento no encontrado");

end;

Algoritmos de Ordenamiento

Ordenamiento por Burbuja

El ordenamiento por burbuja es uno de los algoritmos de ordenamiento más simples. Compara elementos adyacentes y los intercambia si están en el orden incorrecto.

begin
  integer array[1:10];
  integer i, j, temp;

  ! Inicializar el arreglo
  for i := 1 step 1 until 10 do
    array[i] := 10 - i;

  ! Ordenamiento por burbuja
  for i := 1 step 1 until 9 do
    for j := 1 step 1 until 10 - i do
      if array[j] > array[j + 1] then
        temp := array[j];
        array[j] := array[j + 1];
        array[j + 1] := temp;

  ! Mostrar el arreglo ordenado
  for i := 1 step 1 until 10 do
    print(array[i]);

end;

Ordenamiento Rápido (Quicksort)

El ordenamiento rápido es un algoritmo de ordenamiento eficiente que utiliza el enfoque de "divide y vencerás".

procedure quicksort(array, low, high);
  integer array[], low, high;

  begin
    integer pivot, i, j, temp;

    if low < high then
      pivot := array[low];
      i := low;
      j := high;

      while i < j do
        while array[i] <= pivot and i < high do
          i := i + 1;
        while array[j] > pivot do
          j := j - 1;
        if i < j then
          temp := array[i];
          array[i] := array[j];
          array[j] := temp;

      array[low] := array[j];
      array[j] := pivot;

      quicksort(array, low, j - 1);
      quicksort(array, j + 1, high);

  end;

begin
  integer array[1:10];
  integer i;

  ! Inicializar el arreglo
  for i := 1 step 1 until 10 do
    array[i] := 10 - i;

  ! Llamar a quicksort
  quicksort(array, 1, 10);

  ! Mostrar el arreglo ordenado
  for i := 1 step 1 until 10 do
    print(array[i]);

end;

Algoritmos de Recursión

Factorial de un Número

El cálculo del factorial de un número es un ejemplo clásico de recursión.

procedure factorial(n);
  integer n;

  begin
    if n = 0 then
      return 1;
    else
      return n * factorial(n - 1);
  end;

begin
  integer n, result;

  ! Leer el número
  read(n);

  ! Calcular el factorial
  result := factorial(n);

  ! Mostrar el resultado
  print("El factorial de ", n, " es ", result);

end;

Ejercicios Prácticos

Ejercicio 1: Implementar Búsqueda Lineal

Descripción: Implementa una función de búsqueda lineal que reciba un arreglo y un valor a buscar, y retorne la posición del valor en el arreglo o -1 si no se encuentra.

Solución:

procedure linear_search(array, n, key);
  integer array[], n, key;

  begin
    integer i;

    for i := 1 step 1 until n do
      if array[i] = key then
        return i;

    return -1;
  end;

begin
  integer array[1:10];
  integer i, key, position;

  ! Inicializar el arreglo
  for i := 1 step 1 until 10 do
    array[i] := i * 2;

  ! Leer el valor a buscar
  read(key);

  ! Llamar a la función de búsqueda lineal
  position := linear_search(array, 10, key);

  ! Mostrar el resultado
  if position <> -1 then
    print("Elemento encontrado en la posición: ", position);
  else
    print("Elemento no encontrado");

end;

Ejercicio 2: Implementar Ordenamiento por Selección

Descripción: Implementa el algoritmo de ordenamiento por selección para ordenar un arreglo de enteros.

Solución:

procedure selection_sort(array, n);
  integer array[], n;

  begin
    integer i, j, min_index, temp;

    for i := 1 step 1 until n - 1 do
      min_index := i;
      for j := i + 1 step 1 until n do
        if array[j] < array[min_index] then
          min_index := j;

      temp := array[i];
      array[i] := array[min_index];
      array[min_index] := temp;
  end;

begin
  integer array[1:10];
  integer i;

  ! Inicializar el arreglo
  for i := 1 step 1 until 10 do
    array[i] := 10 - i;

  ! Llamar a selection_sort
  selection_sort(array, 10);

  ! Mostrar el arreglo ordenado
  for i := 1 step 1 until 10 do
    print(array[i]);

end;

Conclusión

En este módulo, hemos aprendido a implementar varios algoritmos fundamentales en ALGOL, incluyendo algoritmos de búsqueda, ordenamiento y recursión. Estos algoritmos son esenciales para resolver problemas de manera eficiente y son la base para muchos otros algoritmos más complejos.

Resumen de Conceptos Clave

  • Búsqueda Lineal: Recorrer una lista secuencialmente para encontrar un elemento.
  • Búsqueda Binaria: Dividir una lista ordenada en dos partes para encontrar un elemento.
  • Ordenamiento por Burbuja: Comparar e intercambiar elementos adyacentes para ordenar una lista.
  • Ordenamiento Rápido (Quicksort): Utilizar el enfoque de "divide y vencerás" para ordenar una lista.
  • Recursión: Llamar a una función dentro de sí misma para resolver problemas de manera repetitiva.

Preparación para el Siguiente Tema

En el próximo módulo, exploraremos aplicaciones prácticas de los algoritmos aprendidos, incluyendo métodos numéricos y la implementación de un compilador simple. ¡Prepárate para poner en práctica tus conocimientos y enfrentar nuevos desafíos!

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados