We’ll implement together an efficient program 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 efficient 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.
Spécialisation Introduction to Discrete Mathematics for Computer Science
Build a Foundation for Your Career in IT. Master the math powering our lives and prepare for your software engineer or security analyst career
À propos de cette Spécialisation
Créé par :
Partenaires du secteur :
Suivez l'ordre suggéré ou choisissez le vôtre.
Conçu pour vous aider à vous exercer et à appliquer les compétences que vous avez acquises.
Mettez en évidence vos nouvelles compétences sur votre CV ou sur LinkedIn.
Vue d'ensemble des projets
- Beginner Specialization.
- No prior experience required.
What is a Proof?Session en cours : Apr 16
- 6 weeks, 2–5 hours/week
À propos du coursThere is a perceived barrier to mathematics: proofs. In this course we will try to convince you that this barrier is more frightening than prohibitive: most proofs are easy to understand if explained correctly, and often they are even fun. We pr
Combinatorics and ProbabilitySession en cours : Apr 16
- 6 weeks, 3-5 hours/week
À propos du coursCounting is one of the basic mathematically related tasks we encounter on a day to day basis. The main question here is the following. If we need to count something, can we do anything better than just counting all objects one by one? Do we need to
Introduction to Graph TheorySession en cours : Apr 16
- 5 weeks, 3-5 hours/week
À propos du coursWe invite you to a fascinating journey into Graph Theory — an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major math
Number Theory and CryptographySession à venir : Apr 23
- 4 weeks, 2-5 hours/week
À propos du coursWe all learn numbers from the childhood. Some of us like to count, others hate it, but any person uses numbers everyday to buy things, pay for services, estimated time and necessary resources. People have been wondering about numbers’ properties for t
Delivery ProblemSession à venir : Apr 23
- 3 weeks of study, 2–5 hours/week
À propos du coursWe’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
Alexander S. Kulikov