Curricula CS-UNI

2.2. Fundamentos Algorítmicos (AL)

Los algoritmos y las estructuras de datos son fundamentales para la informática, ya que todo cálculo teórico y programa aplicado consiste en algoritmos que operan sobre elementos de datos que poseen alguna estructura subyacente. Seleccionar soluciones computacionales apropiadas para problemas del mundo real se beneficia de comprender las capacidades y limitaciones teóricas y prácticas de los algoritmos y paradigmas disponibles, incluyendo su impacto en el medio ambiente y la sociedad. Además, esta comprensión proporciona una visión de la naturaleza intrínseca de la computación, los problemas computacionales y la resolución de problemas computacionales, así como de las posibles técnicas de solución independientes del lenguaje de programación, el paradigma de programación, el hardware de la computadora u otros aspectos de implementación.

Esta área de conocimiento se centra en la naturaleza de la computación, incluyendo los conceptos y habilidades necesarios para diseñar y analizar algoritmos para resolver problemas computacionales del mundo real. Complementa la implementación de algoritmos y estructuras de datos que se encuentran en el área de conocimiento de Fundamentos de Desarrollo de Software (SDF). Como los algoritmos y las estructuras de datos son esenciales en todas las áreas avanzadas de la informática, esta área proporciona los fundamentos algorítmicos que se espera que todo graduado en informática conozca. La exposición a la amplitud de estos temas fundamentales de AL está diseñada para proporcionar a los estudiantes la base para estudiar estos temas en mayor profundidad, para estudiar temas adicionales de computación y algoritmos, y para aprender algoritmos avanzados en una variedad de áreas de conocimiento de CS y disciplinas CS+X.

área de Conocimiento (Knowledge Area-KA) (KA)	Core Tier1	Core Tier2	Electivo
2.2.1 Estructuras de Datos Fundamentales			No
2.2.2 Algoritmos Fundamentales			No
2.2.3 Algoritmos Avanzados			No
2.2.4 Estrategias Algorítmicas			No
2.2.5 Marco de Análisis de Complejidad			No
2.2.6 Notación Asintótica y Clases de Complejidad			No
2.2.7 Análisis de Complejidad II: Recursión, Amortización y Cotas Ajustadas			No
2.2.8 Teoría de la Complejidad Computacional			No
2.2.9 Lenguajes Formales y Autómatas			No
2.2.10 Computabilidad y Decidibilidad			No
2.2.11 Sociedad, ética y la Profesión			No

2.2.1. AL/Estructuras de Datos Fundamentales

Temas:
Core

Tipo de Dato Abstracto (ADT) y operaciones sobre un ADT:
1.
Operaciones de diccionario (insertar, eliminar, encontrar)
Arreglos:
1.
Numéricos vs no numéricos, cadenas de caracteres
2.
Unidimensionales (vector) vs multidimensionales (matriz)
Registros/Estructuras/Tuplas y Objetos
Listas enlazadas (por razones históricas):
1.
Simples vs Dobles y Lineales vs Circulares
Pilas
Colas y deques:
1.
Cola de prioridad basada en montículo
Tablas/mapas hash:
1.
Resolución de colisiones y complejidad (por ejemplo, sondeo, encadenamiento, rehash)
árboles:
1.
Binarios, n-arios y árboles de búsqueda
2.
Balanceados (por ejemplo, AVL, Rojo-Negro, Montículo)
Conjuntos

Aprendizaje esperado (Learning Outcomes):
Core:

1.

Para cada ADT/Estructura de Datos en esta unidad:

a): Explicar su definición, propiedades, representación(es) y operaciones de ADT asociadas.
b): Explicar paso a paso cómo las operaciones de ADT asociadas con la estructura de datos la transforman.

[Explicar]

2.

Explicar cómo se maneja la evitación de colisiones y la resolución de colisiones en tablas hash [Explicar]

3.

Explicar la propiedad de montículo y el uso de montículos como una implementación de una cola de prioridad [Explicar]

2.2.2. AL/Algoritmos Fundamentales

Temas:
Core

Grafos (por ejemplo, [no]dirigidos, [a]cíclicos, [no]conexos y [no]ponderados):
1.
Representación de grafos: lista de adyacencia vs matriz
Algoritmos de búsqueda:
1.
Complejidad O(n) (por ejemplo, búsqueda lineal/secuencial en arreglo/lista)
2.
Complejidad O(log ₂n) (por ejemplo, búsqueda binaria)
3.
Complejidad O(log _bn) (por ejemplo, búsqueda en árbol no informada en profundidad/amplitud)
Algoritmos de ordenamiento (por ejemplo, estables, inestables):
1.
Complejidad O(n²) (por ejemplo, inserción, selección)
2.
Complejidad O(nlog n) (por ejemplo, quicksort, merge, timesort)
Algoritmos de grafos:
1.
Camino más corto (por ejemplo, Dijkstra, Floyd)
2.
árbol de expansión mínima (por ejemplo, Prim, Kruskal)
Algoritmos de ordenamiento:
1.
Complejidad O(nlog n) heapsort
2.
Pseudo O(n) complejidad (por ejemplo, bucket, counting, radix)
Algoritmos de grafos:
1.
Clausura transitiva (por ejemplo, Warshall)
2.
Ordenamiento topológico
Emparejamiento:
1.
Emparejamiento eficiente de cadenas (por ejemplo, Boyer-Moore, Knuth-Morris-Pratt)
2.
Emparejamiento de subsecuencia común más larga
3.
Emparejamiento de expresiones regulares

Aprendizaje esperado (Learning Outcomes):
Core:

1.

Para cada algoritmo en esta unidad explicar paso a paso cómo opera el algoritmo [Explicar]

2.

Para cada enfoque algorítmico (por ejemplo, ordenamiento) en esta unidad aplicar un ejemplo

prototípico del enfoque (por ejemplo, ordenamiento por mezcla) [Aplicar]

3.

Dados los requisitos para un problema, desarrollar múltiples soluciones usando varias estructuras de datos y algoritmos. Posteriormente, evaluar la idoneidad, fortalezas y debilidades seleccionando un enfoque que satisfaga mejor los requisitos [Crear]

4.

Explicar factores más allá de la eficiencia computacional que influyen en la elección de algoritmos, como el tiempo de programación, la mantenibilidad y el uso de patrones específicos de la aplicación en los datos de entrada [Explicar]

5.

Para cada uno de los algoritmos y enfoques algorítmicos en los temas del Núcleo KA:

a): Explicar un ejemplo prototípico del algoritmo, y
b): Explicar paso a paso cómo opera el algoritmo.

[Explicar]

2.2.3. AL/Algoritmos Avanzados

Temas:
Non Core

Algoritmos de criptografía (por ejemplo, SHA-256)
Algoritmos paralelos
Algoritmos de consenso (por ejemplo, Blockchain):
1.
Prueba de trabajo vs prueba de participación
Algoritmos de computación cuántica:
1.
Basados en oráculo (por ejemplo, Deutsch-Jozsa, Bernstein-Vazirani, Simon)
2.
Aceleración superpolinomial mediante QFT (por ejemplo, Shor)
3.
Aceleración polinomial mediante amplificación de amplitud (por ejemplo, Grover)
Algoritmo de Transformada Rápida de Fourier (FFT)
Algoritmo de evolución diferencial

Aprendizaje esperado (Learning Outcomes):
NonCore:

1.: Una apreciación de la computación cuántica y su aplicación a ciertos problemas [Explicar]

2.2.4. AL/Estrategias Algorítmicas

Temas:
Core

Paradigmas:
1.
Fuerza Bruta (por ejemplo, búsqueda lineal, ordenamiento por selección, viajante de comercio, mochila)
2.
Disminuir y Vencer:
a)
Por una Constante (por ejemplo, ordenamiento por inserción, ordenamiento topológico)
b)
Por un Factor Constante (por ejemplo, búsqueda binaria)
c)
Por un Tamaño Variable (por ejemplo, Euclides)

3.
Dividir y Vencer (por ejemplo, búsqueda binaria, quicksort, mergesort, Strassen)
4.
Voraz (por ejemplo, Dijkstra, Kruskal, Mochila)
5.
Transformar y Vencer:
a)
Simplificación de instancia (por ejemplo, encontrar duplicados mediante preordenamiento de lista)
b)
Cambio de representación (por ejemplo, heapsort)
c)
Reducción de problema (por ejemplo, mínimo común múltiplo, programación lineal)
d)
Programación dinámica (por ejemplo, Floyd, Marshall, Bellman-Ford)

6.
Compromisos espacio vs tiempo (por ejemplo, hash)
Manejo del crecimiento exponencial (por ejemplo, heurística A*, ramificación y poda, retroceso)
Iteración vs recursión (por ejemplo, factorial, búsqueda en árbol)
Paradigmas:
1.
Algoritmos de aproximación
2.
Mejora iterativa (por ejemplo, Ford-Fulkerson, simplex)
3.
Algoritmos aleatorizados/estocásticos (por ejemplo, corte máximo, bolas y cubos)

Non Core

Computación cuántica

Aprendizaje esperado (Learning Outcomes):
Core:

1.

Para cada uno de los paradigmas en esta unidad:

a): Explicar sus características definitorias
b): Explicar un ejemplo que demuestre el paradigma incluyendo cómo este ejemplo satisface las características del paradigma.

[Explicar]

2.

Para cada uno de los algoritmos en la unidad Fundamentos Algorítmicos (AL) -FoundationalDataStructuresAlgorithms, explicar el paradigma utilizado por el algoritmo y cómo ejemplifica este paradigma [Explicar]

3.

Dado un algoritmo, explicar el paradigma utilizado por el algoritmo y cómo ejemplifica este paradigma [Explicar]

4.

Dar un problema del mundo real, evaluar paradigmas algorítmicos apropiados y algoritmos de estos paradigmas que aborden el problema incluyendo evaluar los compromisos entre los paradigmas y algoritmos seleccionados [Evaluar]

5.

Dar ejemplos de algoritmos iterativos y recursivos que resuelvan el mismo problema, explicar los beneficios y desventajas de cada enfoque [Explicar]

6.

Evaluar si un enfoque voraz conduce a una solución óptima [Evaluar]

7.

Explicar varios enfoques para abordar problemas computacionales cuyas soluciones algorítmicas son exponenciales [Explicar]

2.2.5. AL/Marco de Análisis de Complejidad

Temas:
Core

Marco de Análisis de Complejidad:
1.
Rendimiento de un algoritmo en el mejor caso, caso promedio y peor caso
2.
Mediciones empíricas y relativas (Orden de Crecimiento)
3.
Tamaño de entrada y operaciones primitivas
4.
Eficiencia de tiempo y espacio
Mediciones empíricas de rendimiento
Compromisos tiempo-espacio en algoritmos

Aprendizaje esperado (Learning Outcomes):
Core:

1.: Preparar una presentación que explique a estudiantes de primer año los conceptos básicos de complejidad algorítmica incluyendo comportamiento de algoritmo en mejor caso, caso promedio y peor caso, notaciones Big-O, Omega y Theta, clases de complejidad, compromisos tiempo-espacio, medición empírica e impacto en problemas prácticos [Explicar]
2.: Para cada algoritmo en la unidad Fundamentos Algorítmicos (AL) -FoundationalDataStructuresAlgorithms, explicar su clase de complejidad de tiempo de ejecución y por qué pertenece a esta clase [Explicar]
3.: Evaluar informalmente la clase de complejidad fundamental de algoritmos simples [Evaluar]
4.: Desarrollar estudios empíricos para determinar y validar hipótesis sobre la complejidad de tiempo de ejecución de varios algoritmos ejecutando algoritmos con entradas de varios tamaños y comparando el rendimiento real con el análisis teórico [Crear]
5.: Explicar ejemplos que ilustren los compromisos tiempo-espacio de algoritmos [Explicar]
6.: Explicar cómo el balance del árbol afecta la eficiencia de las operaciones de árbol de búsqueda binaria [Explicar]

2.2.6. AL/Notación Asintótica y Clases de Complejidad

Temas:
Core

Análisis de complejidad asintótica (cotas promedio y peor caso):
1.
Notaciones formales Big-O, Big-Omega y Big-Theta
2.
Clases de Complejidad Fundamentales y Ejemplos/Problemas Representativos:
a)
O(1) Constante (por ejemplo, acceso a arreglo)
b)
O(log ₂n) Logarítmica (por ejemplo, búsqueda binaria)
c)
O(n) Lineal (por ejemplo, búsqueda lineal)
d)
O(nlog ₂n) Log Lineal (por ejemplo, mergesort)
e)
O(n²) Cuadrática (por ejemplo, ordenamiento por selección)
f )
O(n^c) Polinomial (por ejemplo, O(n³) eliminación gaussiana)
g)
O(2ⁿ) Exponencial (por ejemplo, Mochila, Satisfactibilidad (SAT), Viajante de Comercio (TSP), todos los subconjuntos)
h)
O(n!) Factorial (por ejemplo, circuito hamiltoniano, todas las permutaciones)

Aprendizaje esperado (Learning Outcomes):
Core:

1.: Usando ejemplos, explicar cada una de las clases de complejidad fundamentales en esta unidad [Explicar]
2.: Para cada clase de complejidad fundamental en esta unidad, explicar un algoritmo que demuestre la complejidad de tiempo de ejecución asociada [Explicar]
3.: Explicar a una audiencia no técnica la importancia de los algoritmos tratables versus intratables usando una explicación intuitiva de la complejidad Big-O [Explicar]
4.: Aplicar la notación Big-O para dar cotas superiores en la complejidad tiempo/espacio de algoritmos [Aplicar]

2.2.7. AL/Análisis de Complejidad II: Recursión, Amortización y Cotas Ajustadas

Temas:
Core

Notaciones Little-o, Little-Omega y Little Theta
Análisis recursivo formal
Análisis amortizado

Aprendizaje esperado (Learning Outcomes):
Core:

1.: Dado un problema para programar para el cual puede haber varios enfoques algorítmicos, evaluarlos y determinar cuáles son factibles, y seleccionar uno que sea óptimo en implementación y comportamiento de tiempo de ejecución [Evaluar]
2.: Usar relaciones de recurrencia para evaluar la complejidad de tiempo de algoritmos definidos recursivamente [Aplicar]
3.: Aplicar relaciones de recurrencia elementales usando una forma del Teorema Maestro [Aplicar]

2.2.8. AL/Teoría de la Complejidad Computacional

Temas:
Core

Tractabilidad e intractabilidad:
1.
Clases de Complejidad P, NP y NP-Completo
2.
Problemas NP-Completos (por ejemplo, SAT, Mochila, TSP)
3.
Reducciones
Modelos de complejidad basados en Máquinas de Turing:
1.
Complejidad de tiempo:
a)
Clases P, NP, NP-C y EXP
b)
Teorema de Cook-Levin

2.
Complejidad de espacio:
a)
NSpace y PSpace
b)
Teorema de Savitch

Aprendizaje esperado (Learning Outcomes):
Core:

1.: Explicar la importancia de la NP-Completitud [Explicar]
2.: Explicar cómo NP-Duro es una cota inferior y NP es una cota superior para la NP-Completitud [Explicar]
3.: Explicar ejemplos de problemas NP-completos [Explicar]
4.: Explicar el Teorema de Cook-Levin y la NP-Completitud de SAT [Explicar]
5.: Explicar las clases P y NP [Explicar]
6.: Demostrar que un problema es NP-Completo reduciendo un problema NP-C clásico conocido a él (por ejemplo, 3SAT y Clique) [Crear]
7.: Explicar la clase P-espacio y su relación con la clase EXP [Explicar]

2.2.9. AL/Lenguajes Formales y Autómatas

Temas:
Core

Autómatas formales:
1.
Estado Finito
2.
Pila
3.
Linealmente Acotado
4.
Máquina de Turing
Lenguajes formales, gramáticas y Jerarquía de Chomsky:
1.
Regulares (Tipo-3):
a)
Expresiones Regulares

2.
Libres de Contexto (Tipo-2)
3.
Sensibles al Contexto (Tipo-1)
4.
Recursivamente Enumerables (Tipo-0)
Relaciones entre autómatas formales, lenguajes y gramáticas
Autómatas deterministas y no deterministas
Demostraciones del Lema de Bombeo:
1.
Demostración de la limitación de Estado Finito/Lenguaje Regular
2.
Limitación de Autómatas de Pila/Lenguaje Libre de Contexto
Modelos equivalentes de computación algorítmica:
1.
Máquinas de Turing y Variaciones (por ejemplo, multicinta, no deterministas)
2.
Cálculo Lambda
3.
Funciones Mu-Recursivas

Aprendizaje esperado (Learning Outcomes):
Core:

1.

Para cada autómata formal en esta unidad:

a): Explicar su definición comparando sus características con los otros autómatas de esta unidad
b): Usando un ejemplo, explicar paso a paso cómo el autómata opera sobre la entrada incluyendo si acepta la entrada asociada
c): Explicar un ejemplo de entradas que pueden y no pueden ser aceptadas por el autómata.

[Explicar]

2.

Dado un problema, desarrollar un autómata apropiado que aborde el problema [Crear]

3.

Desarrollar una expresión regular para un lenguaje regular dado expresado en lenguaje natural [Crear]

4.

Explicar la diferencia entre expresiones regulares (aceptadores Tipo-3) y las expresiones regulares (aceptadores Tipo-2) usadas en lenguajes de programación [Explicar]

5.

Para cada modelo formal en esta unidad:

a): Explicar su definición comparando sus características con las otras en esta unidad
b): Explicar ejemplos de entradas que son y no pueden ser aceptadas por el lenguaje/gramática.

[Explicar]

6.

Para cada autómata formal en esta unidad explicar (comparar/contrastar) sus capacidades deterministas y no deterministas [Explicar]

7.

Aplicar lemas de bombeo, o medios alternativos, para demostrar las limitaciones de los autómatas de Estado Finito y Pila [Aplicar]

8.

Convertir entre notaciones equivalentemente poderosas para un lenguaje, incluyendo entre DFAs, NFAs y expresiones regulares, y entre PDAs y CFGs [Aplicar]

2.2.10. AL/Computabilidad y Decidibilidad

Temas:
Core

Decidabilidad, (in)computabilidad y parada
La tesis de Church-Turing
Corrección algorítmica:
1.
Invariantes (por ejemplo, en iteración, recursión, búsqueda en árbol)
Decidabilidad:
1.
Aritmetización y diagonalización
Reducibilidad y reducciones
Complejidad de tiempo basada en Máquina de Turing
Complejidad de espacio (por ejemplo, Pspace, Teorema de Savitch)

Non Core

Computación cuántica:
1.
Postulados de la mecánica cuántica:
a)
Espacio de estados
b)
Evolución del estado
c)
Composición de estados
d)
Medición del estado

2.
Representaciones de vector columna de qubits
3.
Representaciones matriciales de operaciones cuánticas
4.
Compuertas cuánticas simples (por ejemplo, XNOT, CNOT)

Aprendizaje esperado (Learning Outcomes):
Core:

1.: Explicar una Máquina de Turing universal y su operación [Explicar]
2.: Presentar a una audiencia de compañeros de trabajo y gerentes la imposibilidad de proporcionarles un programa que verifique todos los otros programas, incluyendo algunos aparentemente simples, en busca de bucles infinitos incluyendo una explicación del problema de la parada, por qué no tiene solución algorítmica y su importancia para la computación algorítmica del mundo real [Explicar]
3.: Explicar ejemplos de problemas clásicos incomputables [Explicar]
4.: Explicar la Tesis de Church-Turing y su importancia para la computación algorítmica [Explicar]
5.: Explicar cómo los invariantes (de bucle) pueden usarse para demostrar la corrección de un algoritmo [Explicar]
6.: Aplicar aritmetización y diagonalización para demostrar que el Problema de la Parada para Máquinas de Turing es Indecidible [Aplicar]
7.: Dado un lenguaje indecidible conocido, aplicar una reducción por mapeo o historia computacional para demostrar que otro lenguaje es indecidible [Aplicar]
8.: Explicar el teorema de Rice y su importancia [Explicar]
9.: Explicar un ejemplo de demostración de un problema que es incomputable reduciendo un problema incomputable clásico conocido a él [Explicar]
10.: Explicar las funciones Recursivas Primitivas y Generales (cero, sucesor, selección, recursión primitiva, composición y Mu), su importancia e implementaciones en Máquina de Turing [Explicar]
11.: Explicar cómo se realiza la computación en el Cálculo Lambda (por ejemplo, conversión alfa y reducción beta) [Explicar]

NonCore:

12.

Para un sistema cuántico dar ejemplos que expliquen los siguientes postulados:

a): Espacio de Estados - estado del sistema representado como un vector unitario en espacio de Hilbert
b): Evolución del Estado - el uso de operadores unitarios para evolucionar el estado del sistema
c): Composición de Estados - el uso de producto tensorial para componer estados del sistema
d): Medición del Estado - la salida probabilística de medir un estado del sistema.

[Explicar]

13.

Explicar la operación de una compuerta cuántica XNOT o CNOT sobre un bit cuántico representado como una matriz y vector columna, respectivamente [Explicar]

2.2.11. AL/Sociedad, ética y la Profesión

Temas:
Core

Algoritmos sociales, éticos y seguros
Equidad algorítmica
Anonimato (por ejemplo, Privacidad Diferencial)
Responsabilidad/Transparencia
Algoritmos responsables
Impactos económicos y otros de algoritmos ineficientes
Sostenibilidad
Computación consciente del contexto

Aprendizaje esperado (Learning Outcomes):
Core:

1.: Desarrollar soluciones algorítmicas a problemas sociales del mundo real, como enrutar una ambulancia a un hospital [Crear]
2.: Explicar el impacto que un algoritmo puede tener en el medio ambiente y la sociedad cuando se usa para resolver un problema del mundo real considerando su sostenibilidad y que puede afectar a diferentes grupos sociales de diferentes maneras [Explicar]
3.: Preparar una presentación que justifique la selección de estructuras de datos y/o algoritmos apropiados para resolver un problema del mundo real dado [Explicar]
4.: Explicar un ejemplo que articule cómo la privacidad diferencial protege el conocimiento de los datos de un individuo [Explicar]
5.: Explicar los impactos ambientales de las decisiones de diseño que se relacionan con el diseño de algoritmos [Explicar]
6.: Explicar los compromisos involucrados en los algoritmos de prueba de trabajo y prueba de participación [Explicar]