Третья лекция
Ivan Veselov
Поскольку на этой неделе проходят такие события как CodeCamp
(http://codecamp.org.ua) и Exception, мы решили объединиться с ними и
провести нашу лекцию в рамках их OpenSpace.
Третья лекция будет более практической, чем вторая, и тема её -- метод
разработки алгоритмов "разделяй и властвуй", который будет
иллюстрироваться на множестве небольших алгоритмов для разных задач.
Касательно предудущей лекции: её материал был сложноватым, возможно у
кого-то возникли проблемы с пониманием материала -- готовьте ваши
вопросы :) Кроме того, мы собираемся раздать упражнения по решению
рекуррентностей и доказательству асимптотических тождеств, чтобы можно
было потренироваться в решении. И не забывайте для прояснения
непонятного иногда заглядывать в книгу :) А также про то, что наша
рассылка существует не только для объявления времени и места
проведения новых лекций, но и для обсуждения разных вопросов,
предложений, фидбэка и прочего :)
Время и место третьей лекции:
Суббота, 26 марта, 7й корпус КПИ, 16:00.
http://codecamp.org.ua/map.jpg
Конкретную аудиторию я думаю можно будет найти по указателям в самом
корпусе, на сайте организаторов она явно не указана.
Приходите! :)
С уважением,
Иван Веселов.
Ivan Veselov
> Время и место третьей лекции:
> Суббота, 26 марта, 7й корпус КПИ, 16:00.
> http://codecamp.org.ua/map.jpg
>
Прошу прощения:
Суббота, 28 марта
С уважением,
Иван Веселов.
Roman Cheplyaka
> Всем привет!
>
> Поскольку на этой неделе проходят такие события как CodeCamp
> (http://codecamp.org.ua) и Exception, мы решили объединиться с ними и
> провести нашу лекцию в рамках их OpenSpace.
Что за exception? Не видел анонса.
А идея хорошая -- будет пиар лекциям :)
--
Roman I. Cheplyaka :: http://ro-che.info/
"Don't let school get in the way of your education." - Mark Twain
Ivan Veselov
>
> Что за exception? Не видел анонса.
> А идея хорошая -- будет пиар лекциям :)
>
Вот анонс :)
http://www.developers.org.ua/archives/piranha/2009/03/26/exception-10/
--
WBR,
Ivan N. Veselov
Roman Cheplyaka
рекурсивной реализации чисел Фибоначчи -- φ^n/√5. Я сходу не понял,
почему это так, поэтому решил проверить.
Теорема 1. Для произвольного бинарного дерева количество листов на 1
меньше количества внутренних вершин.
Доказательство 1. Индукция по количеству внутренних вершин.
Доказательство 2. Пусть E -- число ребер, L -- число листьев, N -- число
внутренних вершин, V=L+N -- число вершин. Имеем
E=2N (из каждой внутренней вершины исходят 2 ребра), E=V-1 (верно для
любого дерева) => 2N=V-1, 2N=L+N-1, N=L-1.
Теорема 2. Рассмотрим бинарное дерево вычисления чисел Фибоначчи, где
каждая вершина помечена соответствующим числом Фибоначчи, например:
3
/ \
2 1
/ \
1 1
Тогда для любого поддерева число его листьев равно числу в вершине этого
поддерева.
Доказательство. Индукция по вложенности деревьев[1], используя то, что обе
величины являются аддитивными по отношению к объединению деревьев.
Таким образом, из приведенных теорем следует, что количество внутренних
вершин (т.е. количество сложений) для вычисления числа Фибоначчи F_n
равно F_n-1. По формуле Бине для чисел Фибоначчи
φ^n - (1-φ)^n φ^n
F_n = ------------- ~ --- ,
√5 √5
т.к. |1-φ| < 1, (1-φ)^n -> 0.
1. http://en.wikipedia.org/wiki/Well-founded_set#Induction_and_recursion
Ivan Veselov
Возможное решение здесь:
http://sicp.org.ua/sicp/Exercise1-13
2009/3/29 Roman Cheplyaka <ro...@ro-che.info>:
--
WBR,
Ivan N. Veselov
Roman Cheplyaka
понятно. Мне как раз была неочевидна связь роста чисел Фибоначчи и
сложность их вычисления. Оказывается, это одно и то же.
* Ivan Veselov <ves...@gmail.com> [2009-03-30 12:40:08+0300]
Anton Tayanovskyy
Вроде ж бы: f ~ O(g) <=> f ~ O(Cg)
--A
2009/3/30 Roman Cheplyaka <ro...@ro-che.info>:
Ivan Veselov
2009/3/30 Anton Tayanovskyy <anton.ta...@gmail.com>:
Roman Cheplyaka
>
> Привет, можете объяснить зачем \sqrt{5}?
>
> Вроде ж бы: f ~ O(g) <=> f ~ O(Cg)
f = O(g) <=> ∃C: |f| < |Cg|
f(n)
f(n) ~ g(n) (n → ∞) <=> lim ---- = 1
n→∞ g(n)
Асимптотическая эквивалентность -- более точное отношение, чем
О-большое.
Anton Tayanovskyy
2009/3/30 Roman Cheplyaka <ro...@ro-che.info>:
Vio
http://code.google.com/edu
2009/3/26 Ivan Veselov <ves...@gmail.com>: