Diseño de Algoritmos: Enfoque de Resolución de Problemas

Algorithm Design

• Problem-solving approach: Break down a problem into smaller, manageable parts, and develop a step-by-step solution.
• Characteristics of a good algorithm:
  • Correctness: Produces the correct output for a given input.
  • Efficiency: Minimizes computational resources and time.
  • Scalability: Performs well with large inputs.
  • Simplicity: Easy to understand and implement.
• Algorithm design techniques:
  • Divide and Conquer: Break down a problem into smaller sub-problems, solve each, and combine the results.
  • Dynamic Programming: Break down a problem into smaller sub-problems, solve each, and store the results to avoid re-computation.
  • Greedy Algorithms: Make the locally optimal choice at each step, hoping to find a global optimum.

Functions

• Definition: A block of code that performs a specific task, can be reused, and takes input parameters.
• Characteristics:
  • Reusability: Can be called multiple times from different parts of the program.
  • Modularity: Encapsulates a specific task, making it easier to maintain and modify.
  • Abstraction: Hides implementation details, only exposing the input and output.
• Function types:
  • Void function: Returns no value.
  • Value-returning function: Returns a value.
  • Recursive function: Calls itself in its implementation.

Loops

• Definition: A control structure that allows a section of code to be executed repeatedly.
• Loop types:
  • For loop: Iterates over a sequence of values, with a fixed number of iterations.
  • While loop: Iterates until a condition is met, with an unknown number of iterations.
  • Do-while loop: Similar to a while loop, but the condition is checked after the first iteration.
• Loop control statements:
  • Break: Exits the loop immediately.
  • Continue: Skips the current iteration and moves to the next one.

Conditional Statements

• Definition: A control structure that executes different blocks of code based on a condition.
• Types of conditional statements:
  • If statement: Executes a block of code if a condition is true.
  • If-else statement: Executes one of two blocks of code based on a condition.
  • Switch statement: Executes one of multiple blocks of code based on the value of an expression.
• Conditional operators:
  • Logical operators: AND (&&), OR (||), NOT (!)
  • Comparison operators: ==, !=, >, <, >=, <=

Recursion

• Definition: A function that calls itself in its implementation.
• Recursion types:
  • Direct recursion: A function calls itself directly.
  • Indirect recursion: A function calls another function, which in turn calls the original function.
• Recursion principles:
  • Base case: A trivial case that can be solved without recursion.
  • Recursive case: A case that breaks down the problem into smaller sub-problems, solved by recursive calls.
  • Termination: The recursive function must eventually terminate, usually by reaching the base case.

Diseño de Algoritmos

• Enfoque de resolución de problemas: Descomponer un problema en partes más pequeñas y manejables, y desarrollar una solución paso a paso.
• Características de un buen algoritmo:
  • Corrección: Produce la salida correcta para una entrada determinada.
  • Eficiencia: Minimiza los recursos computacionales y el tiempo.
  • Escalabilidad: Se desempeña bien con entradas grandes.
  • Simplicidad: Fácil de entender y implementar.
• Técnicas de diseño de algoritmos:
  • Divide y Venceras: Descomponer un problema en sub-problemas más pequeños, resolver cada uno y combinar los resultados.
  • Programación Dinámica: Descomponer un problema en sub-problemas más pequeños, resolver cada uno y almacenar los resultados para evitar re-computación.
  • Algoritmos Codiciosos: Realizar la elección óptima local en cada paso, con la esperanza de encontrar un óptimo global.

Funciones

• Definición: Un bloque de código que realiza una tarea específica, puede ser reutilizado y toma parámetros de entrada.
• Características:
  • Reusabilidad: Puede ser llamada multiple veces desde diferentes partes del programa.
  • Modularidad: Encapsula una tarea específica, haciendo que sea más fácil de mantener y modificar.
  • Abstracción: Oculta detalles de implementación, solo exponiendo la entrada y salida.
• Tipos de funciones:
  • Función void: No devuelve ningún valor.
  • Función de valor de retorno: Devuelve un valor.
  • Función recursiva: Se llama a sí misma en su implementación.

Bucles

• Definición: Una estructura de control que permite ejecutar una sección de código repetidamente.
• Tipos de bucles:
  • Bucle for: Itera sobre una secuencia de valores, con un número fijo de iteraciones.
  • Bucle while: Itera hasta que se cumpla una condición, con un número desconocido de iteraciones.
  • Bucle do-while: Parecido a un bucle while, pero la condición se evalúa después de la primera iteración.
• Instrucciones de control de bucle:
  • Break: Sale del bucle inmediatamente.
  • Continue: Salta la iteración actual y pasa a la siguiente.

Declaraciones Condicionales

• Definición: Una estructura de control que ejecuta diferentes bloques de código según una condición.
• Tipos de declaraciones condicionales:
  • Declaración if: Ejecuta un bloque de código si se cumple una condición.
  • Declaración if-else: Ejecuta uno de dos bloques de código según una condición.
  • Declaración switch: Ejecuta uno de varios bloques de código según el valor de una expresión.
• Operadores condicionales:
  • Operadores lógicos: Y (&&), O (||), NO (!)
  • Operadores de comparación: ==, !=, >, >=, <=, <