Como estudiante graduado, me parece cada vez más común que empresas prestigiosas (como Google, Facebook, Microsoft, ...) presenten preguntas de algoritmos en sus pruebas y entrevistas. Algunas nuevas empresas a las que solicité también me preguntaron sobre algoritmos. Me pregunto si la fluidez de los algoritmos es lo más importante para el desarrollador de software en esas empresas.
Si la respuesta es afirmativa, ¿cuáles son los mejores métodos o recursos para aprender y practicar los algoritmos de manera efectiva? Parece que no puedo interesarme en resolver problemas aparentemente demasiado complicados que se encuentran en la mayoría de los libros de texto o sitios web. Aunque entiendo fácilmente los algoritmos básicos (como quicksort, bubblesort, ...), me resulta inmensamente difícil recordarlos y reutilizarlos más tarde.
Gracias.
P / S: Si me preguntas qué me gusta, está creando buenos softwares para resolver los problemas de los usuarios de manera innovadora. Supongo que eso no necesariamente significa que el software tiene que ser muy complicado.
fuente
Respuestas:
Los algoritmos son claros.
Esto es lo bueno de los algoritmos: el espacio del problema con el que se ocupan está bien definido, es decir, sus requisitos no solo se conocen realmente , sino que incluso se formalizan de manera muy similar a las métricas para la calidad de la solución.
Entonces, si le digo que invente un algoritmo, no hay mucho potencial para problemas de comunicación, y medir su desempeño es una tarea trivial. Al mismo tiempo, su rendimiento es un indicador bastante bueno de su capacidad de pensar lógicamente.
Los algoritmos son un filtro eficiente.
El problema actual de la industria (y la educación) es la mala calidad promedio de los graduados. Esto se ha ilustrado con la prueba FizzBuzz , que es:
Aparentemente, la mayoría de los graduados de Comp Sci no resuelven este problema. Tenga en cuenta que esta es una pregunta algorítmica, aunque, por supuesto, una pregunta vergonzosamente simple. Dado esto, al encontrar a alguien que pueda resolver el tipo de problemas que se dan en Google Code Jam o Project Euler, ya estás disfrutando de la crema de la crema.
Los algoritmos son una pequeña parte del desarrollo de software.
La verdad es que, tan pronto como trabaje en la industria, no utilizará sus habilidades de algoritmo más del 1% del tiempo.
Antes de comenzar a escribir código, primero debe reunir y analizar los requisitos. Luego debes sintetizar tu diseño basado en ellos. Entonces debes implementar el diseño. Luego debe evaluar la implementación con los requisitos originales, luego repetir los requisitos, luego repetir el diseño, luego repetir la implementación y así sucesivamente.
Uno de los requisitos es el rendimiento razonable . Si no se cumple ese requisito, debe perfilar su implementación para rastrear los cuellos de botella y luego puede optimizarlo, lo que a veces es una cuestión de micro-optimización directa (que es bastante fácil de hacer), pero a veces es una cuestión de utilizando mejores algoritmos (que no siempre se hace fácilmente después). Por lo tanto:
Los algoritmos son críticos.
Cuanto mejor comprenda los algoritmos, mayor será la posibilidad de acertar la primera vez. De lo contrario, no solo es probable que se encuentre con un problema que solo se puede resolver implementando un algoritmo mejor, sino que tampoco podrá resolverlo.
Entonces, aunque casi nunca necesita esta habilidad, presenta un solo punto de falla en su metodología de desarrollo y si no tiene la habilidad, solo puede esperar que la necesidad nunca surja, o que alguien más salte a solucionarla. tú.
Lo realmente importante es tener una idea de la complejidad computacional y cómo mantenerla baja, como también expliqué en respuesta a una pregunta similar . O para especializarse en cosas en las que esto simplemente no es importante, como el desarrollo de GUI, pero de nuevo casi todo el mundo lo odia ... ¡por una razón!
fuente
fizzbuzzsi el número era divisible por ambos y que muchos se deslizaron sobre eso porque necesita ordenar cuidadosamente los cheques de módulo.En general, la programación como trabajo no se trata de algoritmos. Puede pasar años programando aplicaciones CRUD sin requerir habilidades algorítmicas profundas.
La programación como trabajo se trata de:
Comunicación:
Su código fuente es un medio para comunicar sus ideas a sus compañeros. Si nadie puede leer / entender su código, no tiene valor.
Un desarrollador solitario que no habla con ningún otro desarrollador probablemente comenzará a cometer errores en el código y creerá que su propio enfoque es el único aceptable.
Debe saber cómo comunicarse con las partes interesadas, el departamento de control de calidad, los usuarios, los diseñadores visuales, los DBA, etc.
Como desarrollador experimentado, debe enseñar a colegas menos experimentados que deseen mejorar sus habilidades.
Conocimiento de las herramientas adecuadas: control de versiones, sistema de seguimiento de errores, IDE, qué idioma es más adecuado para una tarea específica y por qué, cómo usar el análisis de código, etc.
Amplio conocimiento y cultura: ¿qué son los lenguajes funcionales? ¿Cómo interpretan las computadoras el código? ¿Por qué LOC es una medida sin sentido? etc.
Conocimiento profundo de los idiomas con los que trabaja.
Algoritmos
La informática, por otro lado, está más orientada a los algoritmos. Si trabaja como científico, esto puede no tener nada que ver con el trabajo de un desarrollador, y trabajará más sobre cómo optimizar un algoritmo, cómo transformar una representación de datos en otra, etc.
fuente
Creo que las preguntas sobre algoritmos en las entrevistas son una de las principales formas en que las empresas intentan juzgar la comprensión de los fundamentos de la informática por parte de los candidatos. Si bien esta no es la única área de habilidad importante para un programador profesional, es una de las competencias centrales de un buen programador.
Creo que la razón por la cual muchas grandes empresas enfatizan los fundamentos de CS en su proceso de entrevista, es que es la habilidad principal que se desarrolla menos después de graduarse y pasar a la fuerza laboral. La capacidad de programación práctica, las habilidades de diseño, las prácticas de ingeniería de software y similares son todas las cosas que se desarrollan principalmente a través de la experiencia, mientras que los fundamentos de CS se desarrollan principalmente en el curso de su educación.
En cuanto a cómo practicar el diseño de algoritmos, Steve Yegge recomienda el Manual de diseño de algoritmos de Skiena en su excelente guía para entrevistar como programador .
fuente
Como desarrollador de software exitoso que es autodidacta y solo tomó algunos cursos de ciencias de la computación en la universidad, diré que los problemas más grandes que enfrentan las empresas hoy en día no son la capacidad de todos sus programadores para escribir un algoritmo de clasificación de burbujas de la manera más eficiente posible. Los verdaderos problemas que enfrentan las empresas:
Desarrolladores que no pueden aprender rápidamente y adaptarse a nuevos dominios
Desarrolladores que no pueden interactuar socialmente con clientes o partes interesadas de manera significativa
Desarrolladores que no pueden adivinar y cuestionar los requisitos comerciales incorrectos o mal pensados
Desarrolladores que no entienden cómo probar a fondo su código y características
Desarrolladores que no pueden proporcionar estimaciones significativas de manera oportuna
Desarrolladores que no pueden crear documentación clara y concisa
Desarrolladores que no pueden comenzar por sí mismos o hacerse cargo de una situación
Nueve de cada diez veces apostaré a que casi todas las circunstancias en las que un desarrollador falla en una empresa es porque fallan irremediablemente en una de las cualidades anteriores. Olvídese de Google y Facebook, son casos excepcionales y tienen una necesidad legítima de personas que entienden profundamente la informática.
Aunque los negocios reales no luchan con las complejidades de la informática, luchan con las complejidades de la humanidad. El problema es que es REALMENTE difícil probar las cualidades mencionadas anteriormente. La mayoría de las veces tiene que juzgar a las personas sobre estas cualidades en función de su reacción intestinal. Eso es difícil si no tienes buenas habilidades de personas e intuición, es mucho más fácil probar el conocimiento del algoritmo.
fuente
Personalmente, veo algoritmos y estructuras de datos "estándar" como parte del vocabulario de un programador. Y muchos de los problemas prácticos que enfrenta como programador a menudo tienen una solución que es (al menos parcialmente) expresable en este vocabulario.
Tener este vocabulario a su disposición le impide tener que encontrar sus "propias" soluciones (reinventar la rueda, por así decirlo), lo que le permite trabajar de manera más inteligente y, a menudo, más rápido.
Oblígate a completarlos. Te lo agradecerás más adelante. Incluso si no los recuerda con todo detalle (aunque con suficiente práctica lo hará), poder decir "Recuerdo haber resuelto algo similar usando el algoritmo X o la estructura de datos Y" lo ayudará enormemente. Incluso si requiere que busque los detalles y actualice su memoria.
fuente
Aunque no puede ser un buen programador sin conocer sus algoritmos, es injusto mantener otros aspectos de la profesión de programación fuera de la imagen. Por ejemplo, la disciplina estricta y el buen dominio de su lengua materna son al menos tan importantes para ser un buen programador como lo es su conocimiento de algoritmos. Tampoco se debe subestimar la importancia de comprender sus herramientas básicas, como lenguajes de programación, sistemas de control de fuente, entornos de prueba, etc.
Sin embargo, cuando se trata de entrevistas, medir su comprensión de los algoritmos es mucho más simple que medir sus otras habilidades relacionadas con el trabajo como programador. Es por eso que los entrevistadores a menudo se concentran en preguntar sobre algoritmos y prestan mucha atención a la forma en que los explica durante la entrevista. No es porque otras cosas sean menos importantes, sino porque es difícil evaluar estas otras cosas en los 30 minutos asignados para la entrevista.
fuente
Sí, la programación se trata principalmente de algoritmos.
Pero tal vez no en el sentido de que estás pensando.
Tengo la impresión de que todos estamos usando diferentes definiciones de algoritmo. Para ser honesto, esta pregunta es difícil de responder porque algoritmo es un término vago. Usaré la definición de Wikipedia para responder esta pregunta:
Este es el corazón y el alma de la programación. Cuando escribes cualquier código, solo estás implementando un algoritmo. Si está escribiendo algunas aplicaciones CRUD, está implementando un algoritmo simple. Poder programar un algoritmo para resolver un problema es lo que es la programación. El resto son solo detalles.
No estoy de acuerdo con el póster anterior que decía que tener una comprensión profunda de un idioma es más importante que comprender algoritmos. Cualquier buen programador debería ser capaz de aprender un idioma en profundidad, pero sin algoritmos, no puede encontrar ningún código por su cuenta.
fuente
La respuesta depende completamente del trabajo que está realizando. Algunos campos están particularmente más centrados en algoritmos que otros. Hablando con esa nota, tuve el placer de entrevistarme con Amazon varias veces. A pesar de que la posición tendría poco que ver con estos algoritmos complejos, me preguntaron cómo hacer que una tarea amortice el tiempo constante.
Lo que demuestra una sólida comprensión de los algoritmos es una prueba para su posible empleador de que usted es un solucionador de problemas apto. Realmente no es un buen indicador (IMO) de un buen empleado, pero algunos empleadores lo usan para la detección. Si está solicitando un puesto que requiere un título de posgrado, se espera que tenga una base más rigurosa en algoritmos.
Lo que (IMO) es inmensamente útil en la práctica no es memorizar algoritmos específicos, sino que al comprender cómo funcionan algunos algoritmos hay una pequeña pepita en el fondo de su mente donde dirá "He visto esto antes" o "Sé que puede hacerlo mejor ", lo que generará un poco de investigación sobre la solución a su problema.
fuente
Siempre pienso que la programación se basa más en datos que los algoritmos ... pero entonces, de qué sirven los datos si no le haces nada ... todas esas manipulaciones son algoritmos. Entonces, en realidad, sí, la programación se basa prácticamente en algoritmos.
Puede que no parezca matemática, y una gran cantidad de trabajo algorítmico que haría día a día es simplemente algo como enviar datos entre una GUI y un programa, pero eso también cuenta como un algoritmo. Insertar un elemento en un cuadro de lista es un algoritmo de inserción estándar que viene con sus propios problemas, como el rendimiento y las manipulaciones de la estructura de la lista.
fuente
Solo los programadores que trabajan para esas compañías realmente pueden responder su pregunta. Los tipos de algoritmos tratados en decir "Introducción a los algoritmos" probablemente han jugado un papel en el 0.01% de mi vida de programación en los últimos 25 años. Cuando necesito una estructura de datos o un tipo, generalmente las bibliotecas o marcos provistos tienen lo que necesito. Cuando necesito una FFT súper rápida, encuentro algo como la Intel Math lib en lugar de escribirla yo mismo. Sin embargo, puedo entender cómo lo que hacen en Google es muy diferente de lo que he hecho en mi carrera. El libro de Skiena "El manual de diseño de algoritmos" fue revelador debido a las historias de guerra que cuenta. Se nota que usa Algoritmos en su trabajo MUCHO.
En mi experiencia como consultor de programación independiente, el éxito proviene de tres cosas: 1. Comunicación efectiva con los clientes. 2. Escribir código que funcione. 3. Gestión de la complejidad
Hacer solo los números 1 y 2 no es suficiente. Si el código no es mantenible (por alguien que no sea el programador que lo escribió, está condenado).
El número 3 es la habilidad de programación más difícil de dominar. Requiere pensar en arquitectura, diseño y codificación. Requiere dominar la refactorización. Requiere una comprensión de los principios SÓLIDO / SECO. Si tuviera que contratar a un programador que hubiera leído Introducción a Algoritmos y se dedicara a dominarlo o uno que leyera El Programador Pragmático y se dedicara a ser uno, contrataría a este último cada vez. (No es que tengan que excluirse mutuamente).
fuente
Sí.
La informática es principalmente algoritmos (por porcentaje).
No.
Pero esa es la "ciencia" de las computadoras. La aplicación más común de la informática es la ingeniería de software. La ingeniería de software no es principalmente algoritmos. Se trata principalmente del arte de crear, la búsqueda de la perfección, y se centra en afectar positivamente la vida de las personas reales que existen hoy en día. Si bien la informática puede compartir algo de la misma motivación, está muy lejos de la ingeniería de software.
Pregúntele a un profesor titular en una importante Universidad de Ciencias de la Computación qué es lo más importante que debe entender sobre la programación, y probablemente le dirá "algoritmos y estructuras de datos"
Pregúntele a un desarrollador sénior de una importante compañía de software qué es lo más importante que debe comprender sobre la programación, y es probable que le digan "aprender a deleitar a los clientes" (lo que implica entender ágilmente, pensar como un cliente, enviar a tiempo y continuamente, haciendo que las cosas funcionen , etc.)
Puede parecer una semántica, pero desde mi punto de vista, los dos son notablemente diferentes tanto en la práctica como en la teoría.
fuente
Si tuviera que elegir una cosa en informática como la parte más importante, elegiría abstracciones , no algoritmos.
fuente
En Ciencias de la Computación, qué conceptos aprenderá serán inútiles hasta que lo muestre. El problema es la principal preocupación que debe resolverse, por lo que el algoritmo es una breve planificación de cómo se resolverá el problema en general. Por lo tanto, es de gran preocupación en el mundo de la informática.
Creo que casi todos los aspectos de la informática necesitan un algoritmo. Permítanme mostrarles esto. La siguiente lista incluiría varias áreas de informática y qué algoritmos utilizan.
Autómatas
Construcción de powerset. Algoritmo para convertir autómata no determinista en autómata determinista. Algoritmo de Todd-Coxeter. Procedimiento para generar cosets.
Inteligencia artificial
Alfa Beta. Alpha max más beta min. Ampliamente utilizado en juegos de mesa. Ant-algoritmos. La optimización de colonias de hormigas es un conjunto de algoritmos inspirados en el comportamiento de las hormigas para resolver un problema, encontrar la mejor ruta entre dos ubicaciones. DE (evolución diferencial). Resuelva el problema de ajuste polinómico de Chebyshev. Reconocimiento semi-supervisado de oraciones sarcásticas en revisiones de productos en línea. Algortitmo que reconoce sacarsms o ironía en un tweet o un documento en línea. Un algoritmo de este tipo también será esencial para la programación de robots humanoides.
Visión por computador
Epítome. Representar una imagen o video por uno más pequeño. Contando objetos en una imagen . Utiliza el algoritmo de etiquetado de componentes conectados para etiquetar primero cada objeto y luego contar los objetos. Algoritmo de O'Carroll. A partir de una conversión matemática de la visión de los insectos, este algoritmo evalúa cómo moverse evitando los objetos.
Algoritmos genéticos
Usan tres operadores. selección (elija la solución), reproducción (use las soluciones elegidas para construir otras), reemplazo (reemplace la solución si es mejor).
Selección proporcional de aptitud. También conocida como selección de rueda de ruleta, es una función utilizada para seleccionar soluciones. Selección de truncamiento. Otro método para seleccionar soluciones, ordenado por aptitud. Selección de torneo. Seleccione la mejor solución por tipo de torneo. Muestreo universal estocástico. Los individuos se asignan a segmentos contiguos de una línea, de modo que el segmento de cada individuo tiene el mismo tamaño que su estado físico exactamente como en la selección de la ruleta.
Redes neuronales
Hopfield net. Red neuronal artificial recurrente que sirve como sistemas de memoria direccionables por contenido con unidades de umbral binarias. Convergen a un estado estable. Propagación hacia atrás. Técnica de aprendizaje supervisada utilizada para entrenar redes neuronales artificiales. Mapa autoorganizado (mapa de Kohonen). Redes neuronales entrenadas utilizando aprendizaje no supervisado para producir una representación de baja dimensión (2D, 3D) de las muestras de entrenamiento. Bueno para visualizar datos de alta dimensión.
Bioinformática
Needleman-Wunsch. Realiza una alineación global en dos secuencias, para secuencias de proteínas o nucleótidos. Smith-Waterman. Variación del Needleman-Wunsch.
Compresión
Algoritmos de compresión sin pérdida
Transformación de Burrows-Wheeler. Preprocesamiento útil para mejorar la compresión sin pérdidas. Desinflar. Compresión de datos utilizada por ZIP. Codificación delta. Ayuda a la compresión de datos en los que los datos secuenciales ocurren con frecuencia. Codificación incremental. Codificación Delta aplicada a secuencias de cadenas. LZW. (Lempel-Ziv-Welch). Sucesor de LZ78. Crea una tabla de traducción a partir de los datos para comprimir. Es utilizado por el formato gráfico GIF. LZ77 y 78. La base de otras variaciones de LZ (LZW, LZSS, ...). Ambos son codificadores de diccionario. LZMA Abreviatura de Lempel-Ziv-Markov chain-Algorithm. LZO Algoritmo de compresión de datos que se centra en la velocidad. PPM(Predicción por coincidencia parcial). Técnica de compresión de datos estadísticos adaptativa basada en predicción y modelado de contexto. Codificación de Shannon-Fano. Construye códigos de prefijo basados en un conjunto de símbolos y sus probabilidades. Binario truncado. Una codificación de entropía típicamente utilizada para distribuciones de probabilidad uniformes con un alfabeto finito. Mejora la codificación binaria. Codificación de longitud de ejecución. Compresión primaria que reemplaza una secuencia del mismo código por el número de ocurrencias. Sequitur Inferencia gramatical incremental en una cadena. EZW (Wavelet Zerotree integrado). Codificación progresiva para comprimir una imagen en un flujo de bits con mayor precisión. Puede ser compresión con pérdida también con mejores resultados.
Codificación de entropía Esquema de codificación que asigna códigos a los símbolos para hacer coincidir las longitudes de los códigos con las probabilidades de los símbolos.
Codificación Huffman. Compresión simple sin pérdidas aprovechando las frecuencias de caracteres relativas. Codificación adaptativa de Huffman. Técnica de codificación adaptativa basada en la codificación de Huffman. Codificación aritmética. Codificación avanzada de entropía. Codificación de rango. Igual que la codificación aritmética, pero visto de una manera ligeramente diferente. Codificación unaria. Código que representa un número n con n unos seguidos de un cero. Elias delta, gamma, codificación omega. Código universal que codifica los enteros positivos. Codificación de Fibonacci. Código universal que codifica enteros positivos en palabras de código binario. Codificación Golomb. Forma de codificación de entropía que es óptima para alfabetos que siguen distribuciones geométricas. Codificación de arroz. Forma de codificación de entropía que es óptima para alfabetos que siguen distribuciones geométricas.
Algoritmos de compresión con pérdida
Codificación predictiva lineal. Compresión con pérdida al representar la envoltura espectral de una señal digital del habla en forma comprimida. Algoritmo de ley A. Algoritmo de comparación estándar. Algoritmo de ley Mu. Algoritmo de compresión o compresión de señal analógica estándar. Compresión fractal. Método utilizado para comprimir imágenes usando fractales. Transformar codificación. Tipo de compresión de datos para datos como señales de audio o imágenes fotográficas. Cuantización vectorial. Técnica utilizada a menudo en la compresión de datos con pérdida. Compresión Wavelet. Forma de compresión de datos adecuada para compresión de imagen y audio.
Criptografía
Clave secreta (cifrado simétrico)
Use una clave secreta (o un par de claves directamente relacionadas) para descifrar y cifrar.
Estándar de cifrado avanzado (AES) , también conocido como Rijndael. Blowfish Diseñado por Schneier como un algoritmo de propósito general, destinado a reemplazar el envejecimiento DE. Estándar de cifrado de datos (DES) , anteriormente Algoritmo DE. IDEA (Algoritmo internacional de cifrado de datos) . Anteriormente IPES (PES mejorado), otro reemplazo para DES. Es utilizado por PGP (Pretty Good Privacy). Realiza transformaciones en datos divididos en bloques, utilizando una clave. RC4 o ARC4. Cifrado de flujo ampliamente utilizado en protocolos como SSL para tráfico de Internet y WEP para redes inalámbricas. Algoritmo de cifrado minúsculo. Algoritmo de cifrado de bloques fácil de implementar utilizando algunas fórmulas. PES (Estándar de cifrado propuesto). Nombre antiguo para IDEA.
Clave pública (cifrado asimétrico)
Use un par de claves, designadas como clave pública y clave privada. La clave pública cifra el mensaje, solo la clave privada permite descifrarlo.
DSA (algoritmo de firma digital). Generar claves con números primos y aleatorios. Fue utilizado por agencias de EE. UU. Y ahora es de dominio público. ElGamal Basado en Diffie-Hellman, utilizado por el software GNU Privacy Guard, PGP y otros sistemas criptográficos. RSA (Rivest, Shamir, Adleman). Ampliamente utilizado en protocolos de comercio electrónico. Usa números primos. Intercambio de claves de Diffie-Hellman (Merkle) (o intercambio de claves exponencial). Método y algoritmo para compartir secretos sobre un canal de comunicaciones desprotegido. Usado por RSA. NTRUEncrypt. Haga uso de anillos de polinomios con multiplicaciones de convolución.
Funciones de resumen de mensajes
Un resumen de mensaje es un código resultante del cifrado de una cadena o datos de cualquier longitud, procesados por una función hash.
MD5. Se utiliza para verificar imágenes ISO de CD o DVD. RIPEMD (Resumen de mensajes de evaluación de primitivas de integridad RACE). Basado en los principios de MD4 y similar a SHA-1. SHA-1 (Algoritmo de hash seguro 1). El más utilizado del conjunto SHA de funciones hash criptográficas relacionadas. Fue diseñado por la agencia de la NSA. HMAC autenticación de mensaje de hash con clave. Tigre (TTH). Usualmente se usa en hachís de tigre.
Criptográfico utilizando números pseudoaleatorios Ver. Generadores de números aleatorios
Técnicas en criptografía.
Secreto compartido, división secreta, división de claves, algoritmos M of N.
El esquema de intercambio secreto de Shamir. Esta es una fórmula basada en la interpolación polinómica. El esquema de intercambio secreto de Blakley. Es de naturaleza geométrica, el secreto es un punto en un espacio m-dimensional.
Otras técnicas y descifrado
Subconjunto suma. Dado un conjunto de enteros, ¿alguna suma de subconjunto es igual a cero? Utilizado en criptografía. Algoritmo de Shor. Algoritmo cuántico capaz de descifrar un código basado en funciones asimétricas como RSA.
Geometría
Envoltorio de regalo. Determinación del casco convexo de un conjunto de puntos. Gilbert-Johnson-Keerthi distancia. Determinar la distancia más pequeña entre dos formas convexas. Graham scan. Determinación del casco convexo de un conjunto de puntos en el plano. Intersección de segmento de línea. Encontrar si las líneas se cruzan con un algoritmo de línea de barrido. Punto en polígono. Comprueba si un punto dado se encuentra dentro de un determinado. Rayo / intersección plana. * Intersección línea / triángulo. * Caso particular de intersección Ray / Plano. Poligonización de superficies implícitas. Aproximar una superficie implícita con una representación poligonal. TriangulaciónMétodo para evaluar la distancia a un punto desde ángulos a otros puntos, cuya distancia es conocida.
Gráficos Tecnología 3D Surface Tracker. Proceso para agregar imágenes en paredes en un video mientras se tienen en cuenta las superficies ocultas. Bellman-Ford. Calcula las rutas más cortas en un gráfico ponderado (donde algunos de los pesos de los bordes pueden ser negativos). Algoritmo de Dijkstra. Calcula las rutas más cortas en un gráfico con pesos de borde no negativos. Métodos de perturbación. Un algoritmo que calcula las rutas localmente más cortas en un gráfico. Floyd-Warshall. Resuelve el problema de la ruta más corta de todos los pares en un gráfico ponderado y dirigido. El ciclo de búsqueda de Floyd. Encuentra ciclos en iteraciones. Johnson Todos los pares de algoritmo de ruta más corta en un gráfico dirigido ponderado disperso. KruskalEncuentra un árbol de expansión mínimo para un gráfico. Prim. Encuentra un árbol de expansión mínimo para un gráfico. También se llama DJP, Jarník o algoritmo Prim-Jarník. * Boruvka. * Encuentra un árbol de expansión mínimo para un gráfico. Ford-Fulkerson. Calcula el flujo máximo en un gráfico. Edmonds-Karp. Implementación de Ford-Fulkerson. Interruptor de expansión mínima sin bloqueo. Para una central telefónica. Woodhouse-Sharp. Encuentra un árbol de expansión mínimo para un gráfico. A base de primavera. Algoritmo para dibujar gráficos. Húngaro. Algoritmo para encontrar una combinación perfecta. Algoritmo de coloración. Algoritmo de coloración gráfica. El vecino mas cercano.Encuentra al vecino más cercano. Tipo topológico. Ordene un gráfico acíclico dirigido de tal manera que cada nodo venga antes que todos los nodos a los que tiene bordes (de acuerdo con las instrucciones). El algoritmo de antepasados menos comunes fuera de línea de Tarjan. Calcule los antepasados comunes más bajos para pares de nodos en un árbol.
Gráficos
Algoritmo de línea de Bresenham. Utiliza variables de decisión para trazar una línea recta entre 2 puntos especificados. Paisaje Dibuja un paisaje 3D. * Algoritmo de línea DDA. * Utiliza matemática de punto flotante para trazar una línea recta entre 2 puntos especificados. Inundación de relleno. Llena una región conectada con un color. Restauración de imagen. Restaurar foto, mejorar imágenes. Algoritmo de línea de Xiaolin Wu. Línea antialiasing. Algoritmo del pintor. Detecta partes visibles de un escenario tridimensional. Trazado de rayos. Representación realista de imágenes. Phong sombreado. Un modelo de iluminación y un método de interpolación en gráficos 3D por computadora. Sombreado de Gouraud.Simule los diferentes efectos de luz y color en la superficie de un objeto 3D. Representación de scanline. Construye una imagen moviendo una línea imaginaria. Iluminación global. Considera la iluminación directa y la reflexión de otros objetos. Interpolación. Construcción de nuevos puntos de datos, como en el zoom digital. Resintetizador. Elimine un objeto en una foto y reconstruya el fondo utilizado por Photoshop y The Gimp. Tutorial de resintetizador. Algoritmo de intercepción de pendiente. Es una implementación de la fórmula pendiente-intersección para dibujar una línea. Interpolación de spline. Reduce el error con el fenómeno de Runge. Tecnología 3D Surface Tracker. Agregar imágenes o videos en las paredes de un video, teniendo en cuenta las superficies ocultas.
Listas, matrices y árboles.
buscando
Búsqueda de diccionario. Ver búsqueda predictiva. Algoritmo de selección. Encuentra el kth elemento más grande en una lista. Algoritmo de búsqueda binaria. Localiza un elemento en una lista ordenada. Búsqueda de amplitud primero. Atraviesa un gráfico nivel por nivel. Búsqueda de profundidad primero. Atraviesa un gráfico rama por rama. Mejor primera búsqueda. Atraviesa un gráfico en el orden de importancia probable utilizando una cola de prioridad. Una búsqueda en árbol. * Caso especial de la mejor búsqueda en primer lugar que utiliza heurística para mejorar la velocidad. Búsqueda de costo uniforme. Una búsqueda de árbol que encuentra la ruta de menor costo donde los costos varían. Búsqueda predictivaBúsqueda binaria similar que tiene en cuenta la magnitud del término de búsqueda frente a los valores altos y bajos de la búsqueda. Tabla de picadillo. Asociar claves a elementos en una colección sin clasificar, para recuperarlos en un tiempo lineal. Búsqueda interpolada Ver búsqueda predictiva.
Clasificación
Árbol binario tipo. Una especie de árbol binario, incremental, similar a la ordenación por inserción. Bogosort. Tipo de tarjeta de escritorio aleatorio ineficiente. Ordenamiento de burbuja. Para cada par de índices, intercambie los artículos si están fuera de servicio. Tipo de cubo. Dividir una lista en cubos y ordenarlos individualmente. Generaliza la clasificación de casilleros. Clasificación de cóctel (o burbuja bidireccional, agitador, ondulación, lanzadera, clasificación de hora feliz). La variación del tipo de burbuja que se ordena en ambas direcciones pasa a través de la lista. Peine de clasificación. Variación eficiente del tipo de burbuja que elimina las "tortugas", los valores pequeños cerca del final de la lista y hace uso de lagunas entre los valores. Contando tipo.Utiliza el rango de números en la lista A para crear una matriz B de esta longitud. Los índices en B se usan para contar cuántos elementos en A tienen un valor menor que i. Gnomo tipo. Similar a la ordenación por inserción, excepto que mover un elemento a su lugar apropiado se logra mediante una serie de intercambios, como en la ordenación por burbuja. Heapsort. Convierta la lista en un montón, elimine el elemento más grande del montón y agréguelo al final de la lista. Tipo de inserción. Determine dónde pertenece el elemento actual en la lista de ordenados e insértelo allí. Introsort. O tipo introspectivo. Comienza en clasificación rápida y cambia a clasificación múltiple en cierto nivel de recursión. Combinar tipo.Ordene la primera y la segunda mitad de la lista por separado, luego combine las listas ordenadas. Tipo de panqueque. Elementos inversos de algún prefijo de una secuencia. Tipo de casillero. Rellene una matriz vacía con todos los elementos de una matriz que se ordenarán, en orden. Cartero tipo. Variante jerárquica de tipo cubo, utilizada por las oficinas de correos. Ordenación rápida. Divida la lista en dos, con todos los elementos de la primera lista antes de todos los elementos de la segunda lista .; luego ordena las dos listas. A menudo, el método de elección. Radix sort. Ordena las claves asociadas a elementos o enteros procesando dígitos. Selección de selección. Elija el más pequeño de los elementos restantes, agréguelo al final de la lista ordenada. Tipo de concha.Mejora el orden de inserción con el uso de espacios entre valores. Smoothsort Ver montón. Tipo estocástico. Ver bogosort.
y muchos más...
fuente
Has hecho dos preguntas en el encabezado de la pregunta, por lo que responderé a ambas.
Sí, la informática se trata de algoritmos. Bueno ... en realidad eso es un poco engañoso porque hay muchos aspectos de la informática, así que lo reformularé. La ciencia de la computación, tal como se aplica en el mundo laboral, se basa principalmente en algoritmos. Las empresas como Google, Facebook y todos esos lugares locos en Wall Street que contratan físicos y desarrolladores quieren que los problemas altamente complejos se reduzcan a una forma simple, que en sí misma requiere una comprensión profunda de las matemáticas y el diseño de algoritmos.
No, la programación no se trata solo de algoritmos. La programación consiste en tomar especificaciones y convertirlas en código que pueda compilarse para su ejecución.
La parte adicional de la respuesta: el desarrollo de software no es programación y, sin embargo, muchos parecen confundir los términos y usarlos indistintamente. La programación es simplemente una función o una técnica tal vez del proceso más amplio de desarrollo de software. Ciertamente, el desarrollo de software no se trata solo de algoritmos, se trata de resolver problemas con el software y aplicar procesos compatibles con el negocio para permitir que los problemas se resuelvan de manera eficiente. Si bien los procesos de desarrollo de software, e incluso la programación misma, pueden ser procesos algorítmicos en su naturaleza, esto no es lo mismo que ser sobre algoritmos.
fuente