Algoritmia elemental - meruiz22/Analisis-de-Algoritmos GitHub Wiki

Notación

La notación en algoritmia se refiere a los símbolos y convenciones utilizados para representar conceptos matemáticos y de programación de manera estandarizada. Incluye:

Tipos de anotación

Notación Big-O: Describe el comportamiento asintótico de funciones (O, Ω, Θ)

Notación matemática: Símbolos para conjuntos (∈, ⊆, ∪, ∩), cuantificadores (∀, ∃)

Pseudocódigo: Convenciones para describir algoritmos de manera estructurada pero independiente del lenguaje`

Contradicción

Método de demostración lógica que:

Supone lo opuesto a lo que se quiere probar

Muestra que esta suposición lleva a una contradicción

Concluye que la afirmación original debe ser verdadera

Ejemplo clásico: demostración de que √2 es irracional.

Inducción Matemática

Técnica para demostrar proposiciones sobre números naturales:

Base: Se verifica para el caso inicial (normalmente n=0 o n=1) Paso inductivo: Se asume válido para n=k (hipótesis inductiva) y se demuestra para n=k+1

Variantes:

Inducción completa (fuerte)

Inducción estructural (para estructuras recursivas)