Как живущего в Бостоне меня очень заинтересовал пассаж «В Бостоне оказался лучший колледж во всех мировых рейтингах по предпринимательству. Стоит выше Гарварда, Стэнфорда и так далее».
Если у нас есть произвольный направленный граф из n вершин, то ясно, что меньше, чем n * (n — 1) битами обойтись нельзя (потому что всего 2^{n*(n-1)} таких графов). Может, у вас все-таки граф специального вида?
Что же вы успели изучить за две лекции? Нам Максим Бабенко читал в прошлом году годовой (!) спецкурс по потокам, и он далеко не все успел, что хотел. Вот программа, если интересно:
Видимо, хотелось, чтобы результат был полиномиален по длине входа.
Ну пусть будет такая задача: дана N-1 функция f_i: {1, ..., N}^2 -> R. Нужно найти последовательность a_1, a_2, ..., a_N такую, что f_1(a_1, a_2) + f_2(a_2, a_3) +… + f_{N-1}(a_{N-1}, a_N) -> max
Я сам не пробовал школьникам объяснять, что такое предел, но мне в десятом классе это прекрасно объяснили абсолютно строго (нет, я не учился в мат. классе).
> Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).
А вас на этом месте никто не прервал вопросом «как определить формально скорость роста функции»?
А вам не кажется, что это слегка произвольный выбор? Почему выбор именно такой, а не какой-то иначе? Если уж решили заботиться о константе до конца, то нужно учитывать cache-эффекты, branch predictors и т. д. Да и, к примеру, сложения и умножения работают разное время.
Но в целом я согласен, бывает, что асимптотика лучше, но на практике алгоритм хуже (яркий примеры — перемножение матриц методом Штрассена, выбор медианы за детерминированное линейное время, Fibonacci heaps).
Если уж товарищи заинтересовались алгоритмами, то можно было бы вкратце и объяснить, что такое предел. Благо, это несложно, но сугубо необходимо для дальнейшего роста.
А что считать одной операцией? Инструкцию процессора? Строчку кода? Важное свойство O()-нотации: она нечувствительна к (разумной) интерпретации одного языка программирования другим.
Полез гуглить, выяснил, что Илья заканчивал Babson College. Согласно grad-schools.usnews.rankingsandreviews.com/best-graduate-schools/top-business-schools/mba-rankings, Babson College находится на 65 месте. То есть не самое дно, но и не «выше Гарварда и Стэнфорда».
Интересно, какая часть ответов Ильи с такой же гнильцой?
Значение этой школы трудно переоценить, поверьте.
adde.math.msu.su:8080/xwiki/bin/view/MSU/FlowsFall2009
adde.math.msu.su:8080/xwiki/bin/view/MSU/FlowsSpring2010
Есть еще потоки в кососимметрических сетях, мультипотоки, да чего только нет. То есть было бы желание, про потоки можно рассказывать бесконечно.
Кратчайшие пути — это тоже большая и интересная тема. Например, для ознакомления можете посмотреть эту статью:
research.microsoft.com/apps/pubs/default.aspx?id=115272
и ссылки в ней.
Ну пусть будет такая задача: дана N-1 функция f_i: {1, ..., N}^2 -> R. Нужно найти последовательность a_1, a_2, ..., a_N такую, что f_1(a_1, a_2) + f_2(a_2, a_3) +… + f_{N-1}(a_{N-1}, a_N) -> max
> Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).
А вас на этом месте никто не прервал вопросом «как определить формально скорость роста функции»?
Но в целом я согласен, бывает, что асимптотика лучше, но на практике алгоритм хуже (яркий примеры — перемножение матриц методом Штрассена, выбор медианы за детерминированное линейное время, Fibonacci heaps).