К содержимому
learnspaceYOUR NEXT CHAPTER
ПРОСТРАНСТВО ОБУЧЕНИЯ
ГлавнаяКаталог курсовМоё обучениеCoursera

Знания без границ

Учитесь у лучших университетов и компаний мира.

Открыть Coursera
Интеграция
Пространство университета
Моё пространствоСтраница курса
↵
ЯЛичный кабинетСтудент
© 2026 LearnSpaceКаждый день — возможность узнать больше.Помощь
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them · LearnSpace
Назад в каталог
courseraПрограммирование

Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

Курс от Stanford Online
Средний≈ 13.5 чАнглийский
О курсеНавыкиПрограммаПреподаватели

О курсе

The primary topics in this part of the specialization are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).

Навыки, которые вы освоите

AlgorithmsGraph TheoryTheoretical Computer ScienceData StructuresComputational ThinkingNetwork RoutingComputer Science

Программа курса

4 модулей · 61 учебных материалов

01Week 120 материалов

XXIX. THE BELLMAN-FORD ALGORITHM (Week 1)

Week 1 OverviewЧтениеOverview, Resources, and PoliciesЧтениеLecture SlidesЧтениеSingle-Source Shortest Paths, RevistedВидеоOptimal Substructure

Учитесь у экспертов

Tim Roughgarden

Professor

Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
В каталоге вашей программы

Инвестируйте в себя

Новые знания — в удобное для вас время.

Начать на Coursera

Обучение откроется на Coursera
в новой вкладке

Обучение на Coursera

≈ 13.5 ч

4 модулей

Язык: Английский

Субтитры: Китайский (Тайвань), Арабский, Французский, Бенгальский, Узбекский, Украинский, Китайский (Китай), Греческий, Итальянский, Бразильский португальский, Вьетнамский, Нидерландский, Корейский, Немецкий, Пушту, Урду, Русский, Тайский, Индонезийский, Шведский, Турецкий, Азербайджанский, Испанский, Дари, Хинди, Японский, Финский, Казахский, Малайский, Венгерский, Польский

Часть программы вашего университета
Видео
The Basic Algorithm IВидео
The Basic Algorithm IIВидео
Detecting Negative CyclesВидео
A Space OptimizationВидео
Internet Routing I [Optional]Видео
Internet Routing II [Optional]Видео

XXX. ALL-PAIRS SHORTEST PATHS (Week 1)

Problem DefinitionВидеоOptimal SubstructureВидеоThe Floyd-Warshall AlgorithmВидеоA Reweighting TechniqueВидеоJohnson's Algorithm IВидеоJohnson's Algorithm IIВидео

Problem Set #1

Problem Set #1ЗаданиеOptional Theory Problems (Week 1)Чтение

Programming Assignment #1

Programming Assignment #1Задание
02Week 215 материалов

XXXI. NP-COMPLETE PROBLEMS (Week 2)

Week 2 OverviewЧтениеPolynomial-Time Solvable ProblemsВидеоReductions and CompletenessВидеоDefinition and Interpretation of NP-Completeness IВидеоDefinition and Interpretation of NP-Completeness IIВидеоThe P vs. NP QuestionВидеоAlgorithmic Approaches to NP-Complete ProblemsВидео

XXXII. FASTER EXACT ALGORITHMS FOR NP-COMPLETE PROBLEMS (Week 2)

The Vertex Cover ProblemВидеоSmarter Search for Vertex Cover IВидеоSmarter Search for Vertex Cover IIВидеоThe Traveling Salesman ProblemВидеоA Dynamic Programming Algorithm for TSPВидео

Problem Set #2

Problem Set #2ЗаданиеOptional Theory Problems (Week 2)Чтение

Programming Assignment #2

Programming Assignment #2Задание
03Week 39 материалов

XXXIII. APPROXIMATION ALGORITHMS FOR NP-COMPLETE PROBLEMS (Week 3)

Week 3 OverviewЧтениеA Greedy Knapsack HeuristicВидеоAnalysis of a Greedy Knapsack Heuristic IВидеоAnalysis of a Greedy Knapsack Heuristic IIВидеоA Dynamic Programming Heuristic for KnapsackВидеоKnapsack via Dynamic Programming, RevisitedВидеоAnanysis of Dynamic Programming HeuristicВидео

Problem Set #3

Problem Set #3Задание

Programming Assignment #3

Programming Assignment #3Задание
04Week 417 материалов

XXXIV. LOCAL SEARCH ALGORITHMS (Week 4)

Week 4 OverviewЧтениеThe Maximum Cut Problem IВидеоThe Maximum Cut Problem IIВидеоPrinciples of Local Search IВидеоPrinciples of Local Search IIВидеоThe 2-SAT ProblemВидеоRandom Walks on a LineВидеоAnalysis of Papadimitriou's AlgorithmВидео

XXXV. THE WIDER WORLD OF ALGORITHMS (Week 4)

Stable Matching [Optional]ВидеоMatchings, Flows, and Braess's Paradox [Optional]ВидеоLinear Programming and Beyond [Optional]ВидеоEpilogueВидео

Problem Set #4

Problem Set #4ЗаданиеOptional Theory Problems (Week 4)Чтение

Programming Assignment #4

Programming Assignment #4Задание

Final Exam (1 attempt per 24 hours)

Info and FAQ for final examЧтениеFinal ExamЗадание