Este curso forma parte de Programa especializado: Introduction to Discrete Mathematics for Computer Science

4.7
estrellas
358 calificaciones

Alexander S. Kulikov

19.183 ya inscrito

Ofrecido Por

Programa especializado: Introduction to Discrete Mathematics for Computer ScienceUniversity of California San Diego

Acerca de este Curso

2749 vistas recientes

In this online course we’ll implement (in Python) together efficient programs for a problem needed by delivery companies all over the world millions times per day — the travelling salesman problem. The goal in this problem is to visit all the given places as quickly as possible. How to find an optimal solution to this problem quickly? We still don’t have provably efficient algorithms for this difficult computational problem and this is the essence of the P versus NP problem, the most important open question in Computer Science. Still, we’ll implement several solutions for real world instances of the travelling salesman problem.
While designing these solutions, we will rely heavily on the material learned in the courses of the specialization: proof techniques, combinatorics, probability, graph theory. We’ll see several examples of using discrete mathematics ideas to get more and more efficient solutions.

Fechas límite flexibles

Restablece las fechas límite en función de tus horarios.

Certificado para compartir

Obtén un certificado al finalizar

100 % en línea

Comienza de inmediato y aprende a tu propio ritmo.

Curso 5 de 5 en

Programa especializado: Introduction to Discrete Mathematics for Computer Science

Nivel principiante

Aprox. 13 horas para completar

Inglés (English)

Fechas límite flexibles

Restablece las fechas límite en función de tus horarios.

Certificado para compartir

Obtén un certificado al finalizar

100 % en línea

Comienza de inmediato y aprende a tu propio ritmo.

Curso 5 de 5 en

Programa especializado: Introduction to Discrete Mathematics for Computer Science

Nivel principiante

Aprox. 13 horas para completar

Inglés (English)

Instructor

Calificación del instructor

4,65/5 (24 calificaciones)

Alexander S. Kulikov

Professor

Department of Mathematics and Computer Science

700.554 alumnos

13 cursos

Ofrecido por

University of California San Diego

Programa - Qué aprenderás en este curso

Semana

Semana 1

5 horas para completar

Traveling Salesman Problem

We start this module with the definition of mathematical model of the delivery problem — the classical traveling salesman problem (usually abbreviated as TSP). We'll then review just a few of its many applications: from straightforward ones (delivering goods, planning a trip) to less obvious ones (data storage and compression, genome assembly). After that, we will together take the first steps in implementing programs for TSP.

5 horas para completar

4 videos (Total 43 minutos), 1 lectura, 5 cuestionarios

Semana

Semana 2

4 horas para completar

Exact Algorithms

We'll see two general techniques applied to the traveling salesman problem. The first one, branch and bound, is a classical approach in combinatorial optimization that is used for various problems. It can be seen as an improvement of the brute force search: we try to construct a permutation piece by piece, but at each step we check whether it still makes sense to continue constructing the permutation (if it doesn't, we just cut off the current branch). The second one, dynamic programming, is arguably the most popular algorithmic technique. It solves a problem by going through a collection of smaller subproblems.

4 horas para completar

4 videos (Total 49 minutos)

Semana

Semana 3

4 horas para completar

Approximation Algorithms

As we've seen in the previous modules, solving the traveling salesman problem exactly is hard. In fact, we don't even expect an efficient solution in the nearest future. For this reason, it makes sense to ask: is it possible to find efficiently a solution that is probably suboptimal, but at the same time is close to optimal? It turns out that the answer is yes! We'll learn two algorithms. The first one guarantees to find quickly a solution which is at most twice longer than the optimal one. The second algorithms does not have such guarantees, but it is known to work pretty well in practice.

4 horas para completar

2 videos (Total 20 minutos)

Reseñas

4.7

48 reseña

5 stars
76,53 %
4 stars
18,15 %
3 stars
2,79 %
2 stars
2,23 %
1 star
0,27 %

Principales reseñas sobre DELIVERY PROBLEM

por DG20 de may. de 2019

This course is to the point and challenges you with practical application.

por ES18 de jun. de 2018

perfect course! very easy and interesting to follow. Pseudo-Algorithms were very useful and helped a lot to understand the concepts.

por LA30 de oct. de 2020

VERY GOOD COURSE IT IS SO BENTIFITIAL TO THE PEOLPLE WHO ARE INTERTESTED TO DEVELOP THE MATHEMATICAL SKILLS

por AS24 de jul. de 2018

This final course in 5 course specialization is relatively easy one, although the last problem takes little bit time to solve. Provides good introduction to difficult to learn Delivery problem.

Ver todas las reseñas

Acerca de Programa especializado: Introduction to Discrete Mathematics for Computer Science

Discrete Mathematics is the language of Computer Science. One needs to be fluent in it to work in many fields including data science, machine learning, and software engineering (it is not a coincidence that math puzzles are often used for interviews). We introduce you to this language through a fun try-this-before-we-explain-everything approach: first you solve many interactive puzzles that are carefully designed specifically for this online specialization, and then we explain how to solve the puzzles, and introduce important ideas along the way. We believe that this way, you will get a deeper understanding and will better appreciate the beauty of the underlying ideas (not to mention the self confidence that you gain if you invent these ideas on your own!). To bring your experience closer to IT-applications, we incorporate programming examples, problems, and projects in the specialization.

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 compro el Certificado?
Cuando compras un Certificado, obtienes acceso a todos los materiales del curso, incluidas las tareas calificadas. Una vez que completes el curso, 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 participar del curso como oyente 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.

¿Tienes más preguntas? Visita el Centro de Ayuda al Estudiante.

Delivery Problem

Acerca de este Curso