University of Colorado Boulder
Approximation Algorithms and Linear Programming

Ce cours n'est pas disponible en Français (France)

Nous sommes actuellement en train de le traduire dans plus de langues. Consultez les langues disponibles.
University of Colorado Boulder

Approximation Algorithms and Linear Programming

10 271 déjà inscrits

Inclus avec Coursera Plus

Obtenez un aperçu d'un sujet et apprenez les principes fondamentaux.
4.9

(40 avis)

niveau Avancées

Expérience recommandée

Planning flexible
Env. 48 heures
Apprenez à votre propre rythme
Préparer un diplôme
Obtenez un aperçu d'un sujet et apprenez les principes fondamentaux.
4.9

(40 avis)

niveau Avancées

Expérience recommandée

Planning flexible
Env. 48 heures
Apprenez à votre propre rythme
Préparer un diplôme

Ce que vous apprendrez

  • Formulate linear and integer programming problems for solving commonly encountered optimization problems.

  • Develop a basic understanding of how linear and integer programming problems are solved.

  • Understand how approximation algorithms compute solutions that are guaranteed to be within some constant factor of the optimal solution

Compétences que vous acquerrez

  • Catégorie : Travelling Salesman Problem (TSP)
  • Catégorie : Integer Programming
  • Catégorie : Approximation Algorithm
  • Catégorie : Linear Programming (LP)

Détails à connaître

Certificat partageable

Ajouter à votre profil LinkedIn

Évaluations

18 quizzes, 1 devoir

Enseigné en Anglais

Découvrez comment les employés des entreprises prestigieuses maîtrisent des compétences recherchées

Emplacement réservé

Élaborez votre expertise du sujet

Ce cours fait partie de la Spécialisation Foundations of Data Structures and Algorithms
Lorsque vous vous inscrivez à ce cours, vous êtes également inscrit(e) à cette Spécialisation.
  • Apprenez de nouveaux concepts auprès d'experts du secteur
  • Acquérez une compréhension de base d'un sujet ou d'un outil
  • Développez des compétences professionnelles avec des projets pratiques
  • Obtenez un certificat professionnel partageable
Emplacement réservé
Emplacement réservé

Obtenez un certificat professionnel

Ajoutez cette qualification à votre profil LinkedIn ou à votre CV

Partagez-le sur les réseaux sociaux et dans votre évaluation de performance

Emplacement réservé

Il y a 4 modules dans ce cours

This module introduces the basics of linear programs and shows how some algorithm problems (such as the network flow problem) can be posed as a linear program. We will provide hands-on tutorials on how to pose and solve a linear programming problem in Python. Finally, we will provide a brief overview of linear programming algorithms including the famous Simplex algorithm for solving linear programs. The problem set will guide you towards posing and solving some interesting problems such as a financial portfolio problem and the optimal transportation problem as linear programs.

Inclus

7 vidéos2 lectures5 quizzes1 devoir de programmation4 laboratoires non notés

This module will cover integer linear programming and its use in solving NP-hard (combinatorial optimization) problems. We will cover some examples of what integer linear programming is by formulating problems such as Knapsack, Vertex Cover and Graph Coloring. Next, we will study the concept of integrality gap and look at the special case of integrality gap for vertex cover problems. We will conclude with a tutorial on formulating and solving integer linear programs using the python library Pulp.

Inclus

6 vidéos4 quizzes1 devoir1 devoir de programmation4 laboratoires non notés

We will introduce approximation algorithms for solving NP-hard problems. These algorithms are fast (often greedy algorithms) that may not produce an optimal solution but guarantees that its solution is not "too far away" from the best possible. We will present some of these algorithms starting from a basic introduction to the concepts involved followed by a series of approximation algorithms for scheduling problems, vertex cover problem and the maximum satisfiability problem.

Inclus

5 vidéos4 quizzes1 devoir de programmation3 laboratoires non notés

We will present the travelling salesperson problem (TSP): a very important and widely applicable combinatorial optimization problem, its NP-hardness and the hardness of approximating a general TSP with a constant factor. We present integer linear programming formulation and a simple yet elegant dynamic programming algorithm. We will present a 3/2 factor approximation algorithm by Christofides and discuss some heuristic approaches for solving TSPs. We will conclude by presenting approximation schemes for the knapsack problem.

Inclus

11 vidéos5 quizzes1 devoir de programmation3 laboratoires non notés

Instructeur

Évaluations de l’enseignant
4.8 (8 évaluations)
Sriram Sankaranarayanan
University of Colorado Boulder
5 Cours71 013 apprenants

Offert par

Recommandé si vous êtes intéressé(e) par Algorithms

Préparer un diplôme

Ce site cours fait partie du (des) programme(s) diplômant(s) suivant(s) proposé(s) par University of Colorado Boulder. Si vous êtes admis et que vous vous inscrivez, les cours que vous avez suivis peuvent compter pour l'apprentissage de votre diplôme et vos progrès peuvent être transférés avec vous.¹

Pour quelles raisons les étudiants sur Coursera nous choisissent-ils pour leur carrière ?

Felipe M.
Étudiant(e) depuis 2018
’Pouvoir suivre des cours à mon rythme à été une expérience extraordinaire. Je peux apprendre chaque fois que mon emploi du temps me le permet et en fonction de mon humeur.’
Jennifer J.
Étudiant(e) depuis 2020
’J'ai directement appliqué les concepts et les compétences que j'ai appris de mes cours à un nouveau projet passionnant au travail.’
Larry W.
Étudiant(e) depuis 2021
’Lorsque j'ai besoin de cours sur des sujets que mon université ne propose pas, Coursera est l'un des meilleurs endroits où se rendre.’
Chaitanya A.
’Apprendre, ce n'est pas seulement s'améliorer dans son travail : c'est bien plus que cela. Coursera me permet d'apprendre sans limites.’

Avis des étudiants

4.9

40 avis

  • 5 stars

    90 %

  • 4 stars

    7,50 %

  • 3 stars

    2,50 %

  • 2 stars

    0 %

  • 1 star

    0 %

Affichage de 3 sur 40

ND
5

Révisé le 16 janv. 2024

Emplacement réservé

Ouvrez de nouvelles portes avec Coursera Plus

Accès illimité à 10,000+ cours de niveau international, projets pratiques et programmes de certification prêts à l'emploi - tous inclus dans votre abonnement.

Faites progresser votre carrière avec un diplôme en ligne

Obtenez un diplôme auprès d’universités de renommée mondiale - 100 % en ligne

Rejoignez plus de 3 400 entreprises mondiales qui ont choisi Coursera pour les affaires

Améliorez les compétences de vos employés pour exceller dans l’économie numérique

Foire Aux Questions