Preguntas y respuestas para estudiantes, investigadores y profesionales de la informática.
En un curso de algoritmos estándar se nos enseña que quicksort es en promedio y en el peor de los casos. Al mismo tiempo, se estudian otros algoritmos de clasificación que son en el peor de los casos (como mergesort y heapsort ), e incluso tiempo lineal en el mejor de los casos (como bubbleort )...
Me he dado cuenta de que me resulta mucho más fácil escribir pruebas matemáticas sin cometer errores, que escribir un programa de computadora sin errores. Parece que esto es algo más extendido que solo mi experiencia. La mayoría de las personas cometen errores de software todo el tiempo en su...
Echando un vistazo a la página web de Julia , puede ver algunos puntos de referencia de varios idiomas en varios algoritmos (los tiempos se muestran a continuación). ¿Cómo puede un lenguaje con un compilador originalmente escrito en C, superar el código C? Figura: tiempos de referencia relativos...
Hay un montón de preguntas acerca de cómo analizar el tiempo de ejecución de algoritmos (véase, por ejemplo, el tiempo de ejecución-análisis y algoritmo de análisis ). Muchos son similares, por ejemplo, aquellos que solicitan un análisis de costos de bucles anidados o algoritmos de dividir y...
No entiendo por qué el problema de detención se usa con tanta frecuencia para descartar la posibilidad de determinar si un programa se detiene. La Wikipedia [artículo] [1] explica correctamente que una máquina determinista con memoria finita detendrá o repetirá un estado anterior. Puede usar el...
Soy bastante fluido en C / C ++, y puedo manejar los diversos lenguajes de scripting (awk / sed / perl). Empecé a usar Python mucho más porque combina algunos de los aspectos ingeniosos de C ++ con las capacidades de scripting de awk / sed / perl. Pero, ¿por qué hay tantos lenguajes de...
Nos dieron el siguiente ejercicio. Dejar f(n)={100n occurs in the decimal representation of πelsef(n)={10n occurs in the decimal representation of π0else\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}...
Déjame aclarar: Dada una gráfica de dispersión de un número dado de puntos n, si quiero encontrar mentalmente el punto más cercano a cualquier punto de la gráfica, puedo ignorar inmediatamente la mayoría de los puntos en el gráfico, reduciendo mis opciones a un número pequeño y constante de puntos...
Estoy aprendiendo Haskell y estoy fascinado por el idioma. Sin embargo, no tengo antecedentes serios en matemáticas o CS. Pero soy un programador de software experimentado. Quiero aprender teoría de categorías para poder mejorar en Haskell. ¿Qué temas de la teoría de categorías debería aprender...
Convertir expresiones regulares en NFA (mínimo) que acepten el mismo lenguaje es fácil con algoritmos estándar, por ejemplo, el algoritmo de Thompson . Sin embargo, la otra dirección parece ser más tediosa, y a veces las expresiones resultantes son desordenadas. ¿Qué algoritmos existen para...
La mayor parte del cifrado actual, como el RSA, se basa en la factorización de enteros, que no se cree que sea un problema NP-hard, pero pertenece a BQP, lo que lo hace vulnerable a las computadoras cuánticas. Me pregunto, ¿por qué no ha habido un algoritmo de cifrado basado en un problema NP-hard...
Para intentar probar si un algoritmo para algún problema es correcto, el punto de partida habitual es intentar ejecutar el algoritmo a mano en una serie de casos de prueba simples; pruébelo en algunos ejemplos de problemas, incluidos algunos "casos de esquina" simples ". Esta es una gran...
Un árbol indexado binario tiene muy poca o relativamente poca literatura en comparación con otras estructuras de datos. El único lugar donde se enseña es el tutorial de topcoder . Aunque el tutorial está completo en todas las explicaciones, ¿no puedo entender la intuición detrás de tal árbol? ¿Cómo...
Hay muchos intentos de probar o , y, naturalmente, muchas personas piensan en la pregunta y tienen ideas para probar cualquier dirección.P ≠ N PP = N PPAGS=nortePAGS\mathsf{P} = \mathsf{NP} P ≠ N PPAGS≠nortePAGS\mathsf{P} \neq \mathsf{NP} Sé que hay enfoques que han demostrado que no funcionan, y...
Muchos programas de informática requieren dos o tres clases de cálculo. Me pregunto, ¿cómo y cuándo se usa el cálculo en informática? El contenido de CS de un título en informática tiende a centrarse en algoritmos, sistemas operativos, estructuras de datos, inteligencia artificial, ingeniería de...
Estos dos parecen muy similares y tienen una estructura casi idéntica. ¿Cual es la diferencia? ¿Cuáles son las complejidades de tiempo para las diferentes operaciones de cada
Me he estado preguntando acerca de esta pregunta desde que era estudiante de pregrado. Es una pregunta general, pero elaboraré con ejemplos a continuación. He visto muchos algoritmos, por ejemplo, para problemas de flujo máximo, conozco alrededor de 3 algoritmos que pueden resolver el problema:...
En la mayoría de las clases de algoritmos introductorios, se introducen anotaciones como (Big O) y , y un estudiante generalmente aprendería a usar una de estas para encontrar la complejidad del tiempo.OOOΘΘ\Theta Sin embargo, hay otras notaciones, como , y . ¿Hay escenarios específicos donde una...
La fórmula de dimensión Vapnik – Chervonenkis (VC) para redes neuronales varía de O ( E)O(E)O(E) a O ( E2)O(E2)O(E^2) , con O ( E2V2)O(E2V2)O(E^2V^2) en el peor de los casos, donde miEE es el número de aristas y VVV es el número de nodos El número de muestras de entrenamiento necesarias para tener...
Hay dos métodos de partición de clasificación rápida mencionados en Cormen: Hoare-Partition(A, p, r) x = A[p] i = p - 1 j = r + 1 while true repeat j = j - 1 until A[j] <= x repeat i = i + 1 until A[i] >= x if i < j swap( A[i], A[j] ) else return j y: Lomuto-Partition(A, p,...