Curso Gratis de Algoritmos en Cadenas Ofrecido por Universidad de California en San Diego

El siguiente curso gratuito está dirigido para todas aquellas personas interesadas en aprender sobre los algoritmos en cadenas.

Este curso forma parte de un programa especial, siendo este, el cuarto de 6.

Por lo que te dejamos el curso anterior aquí abajo.

Curso Gratis de Caja de Herramientas Algorítmica Ofrecido por Universidad de California en San Diego
Curso Gratis Estructuras de Datos Ofrecido por Universidad de California en San Diego
Curso Gratis de Algoritmos en Gráficos Ofrecido por Universidad de California en San Diego

Acerca de Programa especializado: Estructuras de datos y algoritmos

La leyenda de la informática Donald Knuth dijo una vez: “No entiendo las cosas a menos que intente programarlas”. También creemos que la mejor manera de aprender un algoritmo es programarlo.

Sin embargo, muchos libros excelentes y cursos en línea sobre algoritmos, que se destacan en la introducción de ideas algorítmicas, aún no han logrado enseñarle cómo implementar algoritmos, la habilidad informática crucial que debe dominar en su próxima entrevista de trabajo.

Intentamos llenar este vacío formando un equipo diverso de instructores que incluye expertos líderes mundiales en algoritmos teóricos y aplicados en UCSD (Daniel Kane, Alexander Kulikov y Pavel Pevzner) y un ex ingeniero de software en Google (Neil Rhodes).

Esta combinación única de habilidades hace que esta especialización sea diferente de otros excelentes MOOC sobre algoritmos que son desarrollados por científicos informáticos teóricos. Si bien estos MOOC se centran en la teoría, nuestra especialización es una combinación de teoría/práctica/aplicaciones algorítmicas con ingeniería de software.

Sobre el Curso (Por la Plataforma)

El mundo e Internet está lleno de información textual. Buscamos información mediante consultas textuales, leemos sitios web, libros, correos electrónicos.

Todas esas son cuerdas desde el punto de vista de la informática. Para dar sentido a toda esa información y hacer que la búsqueda sea eficiente, los motores de búsqueda utilizan muchos algoritmos de cadena.

Además, el campo emergente de la medicina personalizada utiliza muchos algoritmos de búsqueda para encontrar mutaciones causantes de enfermedades en el genoma humano.

En este curso en línea, aprenderá conceptos clave de coincidencia de patrones: intentos, árboles de sufijos, matrices de sufijos e incluso la transformación de Burrows-Wheeler.

Te Puede Interesar

Habilidades que obtendrás

Árbol de sufijos
Matriz de sufijos
Algoritmo Knuth-Morris-Pratt (KMP)
Algoritmos en cadenas

Ofrecido por

Universidad de California en San Diego

UC San Diego es una potencia académica y un motor económico, reconocida como una de las 10 mejores universidades públicas por US News and World Report. La innovación es fundamental para lo que somos y lo que hacemos. Aquí, los estudiantes aprenden que el conocimiento no solo se adquiere en el salón de clases, la vida es su laboratorio.

Programa (Contenido)

Árboles de sufijo

¿Cómo buscaría la repetición más larga en una cadena en tiempo LINEAL? En 1973, Peter Weiner ideó una solución sorprendente basada en árboles de sufijos, la estructura de datos clave en la coincidencia de patrones.

Los informáticos quedaron tan impresionados con su algoritmo que lo llamaron el Algoritmo del Año. En esta lección, exploraremos algunas ideas clave para la coincidencia de patrones que, a través de una serie de pruebas y errores, nos llevarán a los árboles de sufijos.

Videos: 6

Duración: 32 Minutos

Matrices de transformación y sufijos de Burrows-Wheeler

Aunque la coincidencia EXACTA de patrones con árboles de sufijos es rápida, no está claro cómo usar los árboles de sufijos para la coincidencia APROXIMADA de patrones.

En 1994, Michael Burrows y David Wheeler inventaron un ingenioso algoritmo para la compresión de texto que ahora se conoce como transformación de Burrows-Wheeler.

No sabían nada de genómica, y no podrían haber imaginado que 15 años más tarde su algoritmo se convertiría en el caballo de batalla de los biólogos en busca de mutaciones genómicas.

Pero, ¿qué tiene que ver la compresión de texto con la coincidencia de patrones? En esta lección aprenderá que el destino de un algoritmo suele ser difícil de predecir: sus aplicaciones pueden aparecer en un campo que no tiene nada que ver con el plan original de sus inventores.

Videos: 5

Duración: 30 Minutos

Algoritmo de Knuth-Morris-Pratt

Felicitaciones, ahora ha aprendido los conceptos clave de coincidencia de patrones: intentos, árboles de sufijos, matrices de sufijos e incluso la transformación de Burrows-Wheeler.

Sin embargo, algunos de los resultados que mencionó Pavel siguen siendo misteriosos: por ejemplo, ¿cómo podemos realizar una coincidencia exacta de patrones en el tiempo O(|Texto|) en lugar de en el tiempo O(|Texto|*|Patrón|) como en el algoritmo ingenuo de fuerza bruta? ¿Cómo puede ser que hacer coincidir un patrón de 1000 nucleótidos con el genoma humano sea casi tan rápido como hacer coincidir un patrón de 3 nucleótidos?

Además, aunque Pavel mostró cómo construir rápidamente la matriz de sufijos dado el árbol de sufijos, ¡no ha revelado la magia detrás de los algoritmos rápidos para la construcción del árbol de sufijos! En este módulo, Miсhael abordará algunos desafíos algorítmicos de los que Pavel trató de esconderse.

Videos: 8

Duración: 54 Minutos

Construcción de matrices de sufijos y árboles de sufijos

En este módulo continuamos estudiando los desafíos algorítmicos de los algoritmos de cadenas. Aprenderá un algoritmo O(n log n) para la construcción de matrices de sufijos y un algoritmo de tiempo lineal para la construcción de un árbol de sufijos a partir de una matriz de sufijos. También implementará estos algoritmos y el algoritmo Knuth-Morris-Pratt en la última asignación de programación de este curso.

Videos: 16

Duración: 119 Minutos

Preguntas Frecuentes

¿Cuándo podré acceder a las lecciones y tareas?

El acceso a las clases y las asignaciones depende del tipo de inscripción que tengas. Si tomas un curso en modo de oyente, verás la mayoría de los materiales del curso en forma gratuita. Para acceder a asignaciones calificadas y obtener un certificado, deberás comprar la experiencia de Certificado, ya sea durante o después de participar como oyente. Si no ves la opción de oyente:

Es posible que el curso no ofrezca la opción de participar como oyente. En cambio, puedes intentar con una Prueba gratis o postularte para recibir ayuda económica.
Es posible que el curso ofrezca la opción ‘Curso completo, sin certificado’. Esta opción te permite ver todos los materiales del curso, enviar las evaluaciones requeridas y obtener una calificación final. También significa que no podrás comprar una experiencia de Certificado.

¿Qué recibiré si me suscribo a este Programa especializado?

Cuando te inscribes en un curso, obtienes acceso a todos los cursos que forman parte del Programa especializado y te darán un Certificado cuando completes el trabajo. Se añadirá tu Certificado electrónico a la página Logros. Desde allí, puedes imprimir tu Certificado o añadirlo a tu perfil de LinkedIn. Si solo quieres leer y visualizar el contenido del curso, puedes auditar el curso sin costo.

¿Hay ayuda económica disponible?

Sí. En ciertos programas de aprendizaje, puedes postularte para recibir ayuda económica o una beca en caso de no poder costear los gastos de la tarifa de inscripción. Si hay ayuda económica o becas disponibles para tu selección de programa de aprendizaje, verás un enlace para postularte en la página de descripción.