Introduccion a los Algoritmos

 

Introducción y Búsqueda de Picos

Descripción General de la Lectura
 

* Administración
* Descripción general del Curso
* Problema de " búsqueda de picos — - versiones 1D y 2D
 

Descripción General del Curso
Este curso cubre:
⦁     Procedimientos eficientes para resolver problemas en entradas grandes (Por ejemplo, Mapa de Carreteras de EE., Genoma Humano)
⦁     Escalabilidad
⦁     Estructuras de datos clásicas y algoritmos elementales (texto CLRS)
⦁     Implementaciones reales en Python
⦁     Conjuntos de problemas divertidos!
 

El curso está dividido en 8 módulos — cada uno de los cuales tiene un problema y un problema motivadores conjunto (s) (excepto el último módulo). Los temas tentativos del módulo y los problemas motivadores son como se describe a continuación:

1. Pensamiento Algorítmico: Búsqueda de Picos
2. Clasificación y Árboles: Simulación de Eventos
3. Hashing: Comparación de Genomas
4. Números: Cifrado RSA
5. Gráficos: Cubo de Rubik
6. Rutas más cortas: Caltech → MIT
7. Programación Dinámica: Compresión de Imágenes
8. Temas Avanzados

Buscador de Picos

Versión unidimensional

La posición 2 es un pico si y solo si b ≥ a y b ≥ c. La posición 9 es un pico si i ≥ h.

 

Figura 1: a-i son números

Problema: Encontrar un pico si existe (¿Existe siempre?)
 

Algoritmo Sencillo

     

Comience desde la izquierda
 

Figura 2: Observe n / 2 elementos en promedio, podría observar n elementos en el peor de los casos
 

¿Y si empezamos por el medio? Para la configuración a continuación, nos fijaríamos en n / 2 elementos. ¿Tendríamos que mirar más de n/2 elementos si comenzamos en el medio y elegimos una dirección basada en qué elemento vecino es más grande que el elemento central?

 
¿Podemos hacerlo mejor?
 

 

Figura 3: Divide y Vencerás

⦁    Si a [n / 2] < a [n / 2 − 1], solo mire la mitad izquierda 1 . . . n/2 − − − 1 para buscar el pico
⦁    De lo contrario, si a[n/2] < a[n/2 + 1], solo mire la mitad derecha n/2 + 1 . . . n para buscar el pico
⦁    De lo contrario, la posición n / 2 es un pico: ¿POR QUÉ?

a [n/2] ≥ a [n / 2 − 1]
a [n/2] ≥ a[n / 2 + 1]

¿Cuál es la complejidad?
 

Para resumir los Θ (i) como lo hacemos aquí, necesitamos encontrar una constante que funcione para todos.
Si n = 1000000, Θ (n) algo necesita 13 segundos en python. Si algo es Θ (log n) solo necesitamos 0,001 seg.
Argumenta que el algoritmo es correcto.

Versión bidimensional

 

            Figura 4: Algoritmo de ascenso codicioso: Complejidad Θ(nm), algoritmo Θ(n2) si m = n

a es un pico 2D si:  a ≥ b, a ≥ d, a ≥ c, a ≥ e
 

                                        Figura 5: El valor marcado con un círculo es el pico.

Intento # 1: Extender la División y conquista 1D a 2D
 

⦁    Elija la columna central j = m / 2.
⦁    Encuentre un pico 1D en i, j.
⦁    Use (i, j) como punto de inicio en la fila i para encontrar el pico 1D en la fila i.

El intento #1 falla
Problema: El pico 2D puede no existir en la fila i

 
Termine con 14, que no es un pico 2D.
Intento # 2

 
⦁    Elija la columna central j = m / 2
⦁    Encuentre el máximo global en la columna j en (i, j)
⦁    Comparar (i, j − 1), (i, j), (i, j + 1)
⦁    Elija columnas izquierdas de (i, j-1) > (i, j)
⦁    Del mismo modo para la derecha
⦁    (i, j) es un pico 2D si ninguna de las dos condiciones se cumple ← ¿POR QUÉ?
⦁    Resuelva el nuevo problema con la mitad del número de columnas.
⦁    Cuando tenga una sola columna, busque el máximo global y listo. 

Ejemplo de intento #2
 

Complejidad del intento #2

 
Si T (n, m) denota el trabajo requerido para resolver un problema con n filas y m columnas

 
Pregunta: ¿Y si reemplazamos el máximo global por el pico 1D en el intento #2? Funcionaria?

ImoTechnologics Introduccion a los Algoritmos-2023