Análisis algorítmico
Utiliza la combinatoria y las relaciones de recurrencia.
Una gran parte de la ciencia de la computación implica tratar de comprender cuán eficientes son los algoritmos para realizar tareas específicas. Desea una manera de poder considerar si un algoritmo es más rápido o menos intensivo en recursos que otro; de esta manera, puede diseñar programas que realicen la misma tarea con menos recursos. Esto es necesario si desea poder escalar sus aplicaciones para manejar grandes entradas.
Para hacer esto, los científicos informáticos han inventado una serie de notaciones y trucos para clasificar el rendimiento de los algoritmos. La idea es bastante sencilla:
- la complejidad del tiempo (la cantidad de tiempo que toma) de un algoritmo es aproximadamente igual al número de operaciones que realiza en una entrada determinada. Digamos que quieres poder ordenar una lista de números [math] n [/ math]. Si el paso más caro en este proceso utiliza las operaciones [math] n ^ {2} [/ math], entonces usted dice que la complejidad del tiempo es del orden de las operaciones [math] n ^ {2} [/ math], denotadas como [math] O (n ^ {2}) [/ math]. Derivar la complejidad del tiempo implica una gran cantidad de matemáticas, en particular la combinatoria y las relaciones de recurrencia.
- la complejidad del espacio (la cantidad de espacio que ocupa) de un algoritmo es aproximadamente la cantidad de recursos adicionales que necesita para poder manejar la entrada. Nuevamente, tomemos una lista de números [math] n [/ math]. Si terminas creando listas adicionales de [math] n [/ math], cada una con un personaje, entonces tienes una complejidad de espacio de [math] O (n) [/ math].
La complejidad temporal de los algoritmos a veces no es muy intuitiva. La exponenciación mediante el algoritmo de cuadratura puede tomar el tiempo de [math] O (log (n)) [/ math], por ejemplo. Aquí hay una derivación de la complejidad temporal de la ordenación de fusión utilizando series infinitas y relaciones de recurrencia.
Esquemas de compresión de datos
Usa probabilidad y estadísticas – mucho.
Una gran cantidad de algoritmos por sí mismos explotan las matemáticas avanzadas. La probabilidad es una de las favoritas de siempre.
Los esquemas de compresión de datos se utilizan para comprimir archivos mediante la explotación de patrones en los datos. Por ejemplo, en lugar de escribir ‘aaaaa’, una computadora podría simplemente marcar esa región en la memoria como 5a, lo que indica que esta sección tiene cinco a, lo que reduce la cantidad de caracteres necesarios para expresar eso de 5 a solo 2.
Sin embargo, a veces no es muy fácil discernir patrones que pueden ser explotados. Ahí es donde entra la probabilidad. Esquemas como la combinación de contextos intentan predecir la siguiente región en la memoria de todas las piezas anteriores, lo que potencialmente ahorra muchos gastos generales.
Visión por Computador, Gráficos y Procesamiento de Imágenes.
Utiliza álgebra lineal (y ocasionalmente cálculo)
Si alguna vez has jugado a un videojuego o has visto una animación, realmente estás viendo una de las hazañas matemáticas más monumentales de la informática. Casi todo en gráficos de computadora se puede describir como una transformación : tomas un vector y le aplicas una serie de matrices para obtener un nuevo vector. El vector es la unidad fundamental de los gráficos, una buena analogía es una línea recta. Encadenarlos juntos te permite construir gráficos realmente interesantes.
La visión de computadora se ocupa de que las computadoras entiendan lo que significan las imágenes. En realidad, las imágenes no son más que valores RGB codificados en una matriz, por lo que, cuando vemos una obra de arte pintoresca, la computadora solo ve un área gigante de números. Si alguna vez aplicó un filtro en Instagram, realmente ha estado haciendo algunas notables multiplicaciones de matrices avanzadas.
¿Qué pueden hacer los algoritmos de desenfoque gaussiano con un poco de matemáticas?
Muchos motores de juegos hacen uso de la física también para calcular cosas como la dispersión de la luz en juegos en 3D. Por experiencia, puedo decirles que estas son integrales realmente complicadas y feas, y la mayoría de las computadoras usan algoritmos numéricos (como los métodos de diferencias finitas) para resolverlos.
Estructuras de datos
Usa la teoria grafica
Este es un árbol de búsqueda binario, un ejemplo de un árbol binario y una estructura de datos.
Las estructuras de datos son abstracciones que le permiten manipular cómo se almacenan y se accede a los objetos. Una gran cantidad de estructuras de datos realmente interesantes, todas muy útiles, porque algunos de ellos pueden reducir los algoritmos complejos de [math] O (n ^ {2}) [/ math] a solo [math] O (1) [/ math] ( tiempo constante ) algoritmos – son gráficos.
Creo que no es un error decir que la teoría de grafos es lo único que terminas aprendiendo si estás en ciencias de la computación. Puedes usarlo para diseñar motores de ajedrez, por ejemplo, o construir Google Maps. La teoría de gráficos a menudo se ocupa de encontrar rutas (formas de pasar de un nodo a otro) a través de un gráfico; si puede modelar su problema como un gráfico, puede aplicar soluciones de la teoría de gráficos en la mayoría de los casos.
Las estructuras de datos generalmente se agrupan con algoritmos en la mayoría de los cursos de CS.
Criptografía
Utiliza la teoría de los números.
La criptografía hace uso de muchas técnicas para hacer exactamente dos cosas:
- Realizando operaciones de números en diferentes bases.
- Factorizar enteros grandes, que requieren muchos trucos de aritmética modular
No todo esto implica matemáticas avanzadas: los Crypto Challenges de Matasano tienen el famoso orgullo de que todos se pueden resolver con matemáticas muy elementales. Pero requiere que entres en la mente de un teórico numérico.
