Третья лекция

4 views
Skip to first unread message

Ivan Veselov

unread,
Mar 26, 2009, 7:35:47 AM3/26/09
to kiev...@googlegroups.com
Всем привет!

Поскольку на этой неделе проходят такие события как CodeCamp
(http://codecamp.org.ua) и Exception, мы решили объединиться с ними и
провести нашу лекцию в рамках их OpenSpace.

Третья лекция будет более практической, чем вторая, и тема её -- метод
разработки алгоритмов "разделяй и властвуй", который будет
иллюстрироваться на множестве небольших алгоритмов для разных задач.

Касательно предудущей лекции: её материал был сложноватым, возможно у
кого-то возникли проблемы с пониманием материала -- готовьте ваши
вопросы :) Кроме того, мы собираемся раздать упражнения по решению
рекуррентностей и доказательству асимптотических тождеств, чтобы можно
было потренироваться в решении. И не забывайте для прояснения
непонятного иногда заглядывать в книгу :) А также про то, что наша
рассылка существует не только для объявления времени и места
проведения новых лекций, но и для обсуждения разных вопросов,
предложений, фидбэка и прочего :)

Время и место третьей лекции:
Суббота, 26 марта, 7й корпус КПИ, 16:00.
http://codecamp.org.ua/map.jpg

Конкретную аудиторию я думаю можно будет найти по указателям в самом
корпусе, на сайте организаторов она явно не указана.

Приходите! :)

С уважением,
Иван Веселов.

Ivan Veselov

unread,
Mar 26, 2009, 7:38:13 AM3/26/09
to kiev...@googlegroups.com
2009/3/26 Ivan Veselov <ves...@gmail.com>:

> Время и место третьей лекции:
> Суббота, 26 марта, 7й корпус КПИ, 16:00.
> http://codecamp.org.ua/map.jpg
>

Прошу прощения:
Суббота, 28 марта

С уважением,
Иван Веселов.

Roman Cheplyaka

unread,
Mar 26, 2009, 12:34:04 PM3/26/09
to kiev...@googlegroups.com
* Ivan Veselov <ves...@gmail.com> [2009-03-26 13:35:47+0200]

> Всем привет!
>
> Поскольку на этой неделе проходят такие события как 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

unread,
Mar 26, 2009, 12:58:48 PM3/26/09
to kiev...@googlegroups.com
2009/3/26 Roman Cheplyaka <ro...@ro-che.info>:

>
> Что за exception? Не видел анонса.
> А идея хорошая -- будет пиар лекциям :)
>

Вот анонс :)
http://www.developers.org.ua/archives/piranha/2009/03/26/exception-10/

--
WBR,
Ivan N. Veselov

Roman Cheplyaka

unread,
Mar 29, 2009, 4:31:25 PM3/29/09
to kiev...@googlegroups.com
В последней лекции была упомянута асимптотическая сложность наивной
рекурсивной реализации чисел Фибоначчи -- φ^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

unread,
Mar 30, 2009, 5:40:08 AM3/30/09
to kiev...@googlegroups.com
Кстати, похожее упражнение есть в нашей SICP wiki.
Возможное решение здесь:
http://sicp.org.ua/sicp/Exercise1-13

2009/3/29 Roman Cheplyaka <ro...@ro-che.info>:

--
WBR,
Ivan N. Veselov

Roman Cheplyaka

unread,
Mar 30, 2009, 5:47:30 AM3/30/09
to kiev...@googlegroups.com
Там просто выводится формула Бине и асимптотика чисел Фибоначчи, это все
понятно. Мне как раз была неочевидна связь роста чисел Фибоначчи и
сложность их вычисления. Оказывается, это одно и то же.

* Ivan Veselov <ves...@gmail.com> [2009-03-30 12:40:08+0300]

Anton Tayanovskyy

unread,
Mar 30, 2009, 5:51:46 AM3/30/09
to kiev...@googlegroups.com
Привет, можете объяснить зачем \sqrt{5}?

Вроде ж бы: f ~ O(g) <=> f ~ O(Cg)


--A

2009/3/30 Roman Cheplyaka <ro...@ro-che.info>:

Ivan Veselov

unread,
Mar 30, 2009, 5:54:17 AM3/30/09
to kiev...@googlegroups.com
В лекции было \Omega(\phi^n)

2009/3/30 Anton Tayanovskyy <anton.ta...@gmail.com>:

Roman Cheplyaka

unread,
Mar 30, 2009, 6:03:00 AM3/30/09
to kiev...@googlegroups.com
* Anton Tayanovskyy <anton.ta...@gmail.com> [2009-03-30 12:51:46+0300]

>
> Привет, можете объяснить зачем \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

unread,
Mar 30, 2009, 6:06:42 AM3/30/09
to kiev...@googlegroups.com
Cпасибо, теперь ясно. --А

2009/3/30 Roman Cheplyaka <ro...@ro-che.info>:

Vio

unread,
Mar 30, 2009, 10:02:36 AM3/30/09
to kiev...@googlegroups.com
кое-что по алгоритмам и другим темам есть на гугле, может кому пригодится:
http://code.google.com/edu

2009/3/26 Ivan Veselov <ves...@gmail.com>:

Reply all
Reply to author
Forward
0 new messages