PS: Ну вы и нафлудили...

Добавлено (20.02.2008, 17:04)
---------------------------------------------
Первая версия, часть 1.
http://msiu-prog.ifolder.ru/5429942

В общем, я исправил кое-какие свои опечатки в ответах по элементарной математике. Сегодня-завтра думаю дописать какие знаю вопросы по математике и выложить.

Добавлено (22.02.2008, 11:43)
---------------------------------------------
Вторая версия. Исправлены опечатки и решены (или даны некоторые наброски решения) несколько задач по математике.
http://msiu-prog.ifolder.ru/5452349

Добавлено (22.02.2008, 11:52)
---------------------------------------------
УРА!!!!!!!!!
Мне удалось скачать чрезвычайно полезный документик под названием
Introduction To Algorithms 2Nd Edition Solutions(Instructor's.Manual).pdf (инструкция для преподавателей, которые основывают на "Алгоритмах" Кормана, содержащие ответы на все вопросы книги) - настоятельно рекомендую всем, кто хочет сдать этот коллок.
Чем не могу не поделиться (прямую ссылку дать не хочу, ибо качал ослом очень медленно, поэтому просто перезалил на ifolder).

http://msiu-prog.ifolder.ru/5452453

Добавлено (22.02.2008, 11:59)
---------------------------------------------
Сори, вру, не на все. Тока на самые сложные (читаю введение). В общем, в любом случае штука чрезвычайно полезная.

Добавлено (22.02.2008, 13:00)
---------------------------------------------
Блин... Книжка часто содержит только ответы или указания решения. В общем из разряда "глупому не поможет, умному не за чем"... Придется думать самому или разбирать на семинарах :(.

Добавлено (01.03.2008, 00:56)
---------------------------------------------
Хотя, с другой стороны, если вдруг в задаче 2.16 окажется, что это верно для c = 1, то всё будет нормально.

Добавлено (01.03.2008, 01:00)
---------------------------------------------
Да, в решении получаем, что log([log log n]!) = o(log n), значит фиксируя c = 1 можно перейти к O(log n), откуда следует полиномиальная ограниченность исследуемой функции.
Всем спасибо, вы мне очень помогли.
Надо будет поразбираться в этом примере более трезвым

Добавлено (01.03.2008, 10:44)
---------------------------------------------
=================
Гыыы. Я умён и мудёр - нашол исчо одно доказательство log(n!) = \Theta(n log n).
Способ 1 основывется на формуле Стирлинга (кстати пока в моих решениях по этому поводу написан полный бред. Я уже разобрался как это доказывать, осталось исправить решение) - но с ним мы будем судя по всему разбираться на следующем семинаре.

Способ 2 основывается на сравнении ряда с интегралом (подробнее смотри в Кормане):
log(n!) = log 1 + log 2 +...+ log n
Сверху за константу можно взять единицу: log 1 + log 2 + ... + log n <= log n + log n +...+ log n = n log n
Cнизу: log 1 + log 2 +...+ log n = log 2 + log 3 + ... + log n >= Int_1^n log x dx = n log n - n log e + log e > n log n - n log e.
Покажем, что существует такое c, что
n log n - n log e >= c n log n. Возьмем в качестве c = 1/2, тогда 1/2 n log n >= n log e <=> n >= e^2. Что выполнено для n > 9. Таким образом, получаем, что для любых n > 9 выполнено:
0 <= 1/2 n log n <= log(n!) <= n log n, но это и значит, что log(n!) = \Theta(n log n).

Добавлено (01.03.2008, 10:48)
---------------------------------------------
PS: на мой взгляд второй способ много конструктивнее, красивее, проще, да и вообще просто замечателен сам по себе тем фактом, что я вывел его самостоятельно.

Добавлено (02.03.2008, 03:07)
---------------------------------------------
Итак, обновил свои ответы к колку:
http://msiu-prog.ifolder.ru/5567494
Там решены ещё не все задачи, а ряд задач решены не полностью, с ошибками или с очень малой формализацией.
Можете модифицировать кто хочет, тк. скорее-всего я более не буду сопровождать этот документ (осталось не так много времени, а я ещё не разбирался с теорией и программами).

И хотя, по-хорошему, работа ещё не завершена, надеюсь что она кому-то поможет.

Добавлено (02.03.2008, 12:05)
---------------------------------------------
Там в последних двух задачах фигня написана. В ответе 2.21 должна стоять фигурная скобка:
/ 0, при n = 1
\ [log n] - 1, иначе (см. примечание);
В ответе 2.22:
/ 0, при n = 1
\ [log log n], иначе (см. примечание).
На самом деле это квивалентно соответсвенно max{0, [log n] - 1} и max{0, [log log n]} соответсвенно (если положить log log 1 = -Inf). Но так лучше, потому что не нужно никаких доп. усложнений.
Замечание: то, что в этих задачах я обозначил как [f(n)] нужно обозначать как округление в большую сторону.

Вот здесь все, что я нашел у себя на компе по колоку.....

Выражаю благодарность всем кто решал эти задачи....

Пролистал, пока возникли следующие вопросы:

Элементарная математика:
7. Ты пользуешься тем, что 3 > 2^{\sqrt 2} - уверен, что Роганов не попросит это доказать? (это все-таки совсем не очевидный факт).
Есть более простое решение без использования производных: возвести обе части уравнения в степень \sqrt 3.

21. - в одной тетрадке доказательство вроде нормальное, в другой тупо нарисован квадрат.

Математика:
6) Что-то я не понял, сначала ты утверждаешь, что n log n растет быстрее, чем log (n!), потом пытаешься доказать, что они эквивалентны (Кстати, не уверен в строгости доказательства, т.к. ты почему-то игнорируешь \Theta(1/n) в формуле Стирлинга)...

10) - можешь прокомментировать?
1 < 1 + sin n < 2 - неверно (может нужен модуль при синусе),
lim (1/(n^{1+sin n})) = 1 ??? - Ты уверен, что этот придел вообще существует. Да и вообще, если этот предел существует и равен 1, то f(n) ~ g(n), но это значит, что f(n) = \Theta(g(n)) - т.е. эти функции заведомо не удовлетворяют условию задачи (вроде этого предела нет, но надо бы проверить).

15, 16) - Уж не знаю, как ты доказывал, вот только в 16) явно ответ не сходится [log log n]! - полиномиально ограничена (см. солюшен) (если я конечно правильно тебя понял, т.к. никакой формулировки вроде "Ответ" у тебя нет, а тот факт, что [log log n]! = O(n^k) вовсе не отменяет их тета-эквивалентность).

17) - не понимаю, а где там использована теорема о реккурентных оценках.

А теперь постараюсь ответить на возникшие вопросы:

7. 3 > 2^1.5 > 2^{\sqrt 2} Вот тебе все и доказательство...

21. что я могу ответить? учи по той тетрадке где " доказательство вроде нормальное" )))

6, 10, 15,16,17 - не хотелось вдумываться в ответ... прикрепляю другой вариант доказательств... http://rapidshare.com/files/96831327/Dop.rar.html

17 - Вот сама теорема о рекуррентных оценках... http://rapidshare.com/files/96832796/Toro.JPG.html

В общем, спасибо что ответил на вопросы.

условие задачи:

Что произойдёт при попытке запустить следующую программу на языке Ruby?
puts "String".sub(’g’,’G’)=="String".sub(’g’,’G’) #возвращает true
Как будет выглядеть программа на языке Java, выполняющая аналогичные действия и дающая такой же результат?

В решении написано, что см. задачу №13. А в этой задаче:

class Test12 {
public static void main(String[] args) {
System.out.println("String".replace(’g’,’G’) =="String".replace(’g’,’G’));
}
}
//возвращает false

А в условии задачи 18 написано, что надо написать программу, выполняющую аналогичные действия и дающую такой же результат.
................................................................................................

То есть должно быть так:

public class Test17 {
public static void main(String[] args) {
System.out.print("String".replace('g','G').contentEquals("String".replace('g','G')));
}
}

Сомневаюсь, что это ночной глюк.

class MTest17 {
public static void main(String[] args) {
System.out.println("String".replace('g','G').equals(
"String".replace('g','G')));
}
}

Добавлено (14.04.2008, 23:44)
---------------------------------------------
при n-к бесконечности

\lim_{n \to \infty}{\frac{\log{n}{n}} = [m = \log{n}, n = 2^m] = \lim_{m \to \infty}{\frac{m}{2^m}} = 0

причем в \lim_{m \to \infty}{\frac{m}{2^m}} m \in R

что очевидно в силу того, что \lim_{n \to \infty}{\frac{n}{2^n}} = 0
и \frac{[m]}{2^{[m]+1}} <= \frac{m}{2^m} <= \frac{[m]+1}{2^{[m]}}

Добавлено (15.04.2008, 19:53)
---------------------------------------------
P.S. огромное спасибо Xaron'у и dima'е

Пусть \lim_{n \to \infty}{\frac{\log{n}}{n}} != 0, тогда рассмотрим подпоследовательность b_n = \frac{\log{n}}{n}, где n=2^m (m \in N).
Т.к. \lim_{n \to \infty}{\frac{\log{n}}{n}} != 0, то \lim_{n \to infty}{b_n} != 0.
Т.е. \lim_{m \to infty}{\frac{m}{2^m}} != 0, УРА мы получили БРЕД,
а следовательно исходное утверждение не верно, те
\lim_{n \to \infty}{\frac{\log{n}}{n}} = 0.

Чтд

Добавлено (15.04.2008, 22:20)
---------------------------------------------
Ладно, доказательство в последней на данный момент версии, расшифровываю Дена. Рассматривая предел последовательности log(n)/n, мы делаем замену переменных n=2^m, где m=log(n), причем m - число действительное. Тем самым мы переходим уже не к пределу последовательности, а к пределу функции f(m)=m/2^m, равенство нулю которого придется доказать методами отличными от применяемых для схожей последовательности n/2^n. Для любого вещественного m справедливо следующее (квадратные скобки означают округление вниз): [m]<=m<[m]+1, поэтому, уменьшая числитель и увеличивая знаменатель, мы уменьшаем дробь: [m]/2^([m]+1)<=m/2^m. Так же верно и то, что дробь увеличивается при увеличении числителя и уменьшении знаменателя: m/2^m<=([m]+1)/2^[m]. Таким образом функция m/2^m оказывается заключенной между двумя другими, предел которых равен 0 (что легко доказать, рассмотрев пределы последовательностей n/2^(n+1) и (n+1)/2^n, ведь значения этих функций на ненатуральных положительных m, в силу округления, совпадают в элементами последовательностей). Раз предел функций, заключающих между собой функцию m/2^m равен нулю, то и пределу этой функции тоже некуда деваться. чтд.

Добавлено (16.04.2008, 00:05)
---------------------------------------------
lim(f(x))=log(lim(2^f(x))) - эту формулу можно использовать?
если да, то:
lim(log(x)/x)=log(lim(2^(log(x)/x)))=log(lim((2^log(x))^(1/x)))=log(lim(x^(1/x)))=log(1)=0
только надо ещё доказать, что lim(x^(1/x))=1

Добавлено (16.04.2008, 19:17)
---------------------------------------------
По просьбам трудящихся доказываю, что 2^log*n=o(sqrt(log n)). Рассмотрим последовательность c членами 2^log*n/sqrt(log n). Среди них выделем подпоследовательность с n=(2^2^...^2; m раз), где m - натуральное. Члены этой подпоследовательности имеют вид m/sqrt(log(2^2^...^2; m раз)), что равно sqrt((m^2)/(2^2^...^2; m-1 раз)). Выразим последующий член подпоследовательности через предыдущий:
sqrt(((m+1)^2)/(2^2^...^2; m раз)) =
= sqrt((m^2)*(1+2/m+1/m^2)/((2^2^...^2; m-1 раз)*2^((2^2^...^2; m-1 раз)-log(2^2^...^2; m-1 раз)))) =
= sqrt(((m+1)^2)/(2^2^...^2; m раз))*sqrt((1+2/m+1/m^2)*(2^2^...^2; m-1 раз)/2^(2^2^...^2; m-1 раз)).
Мы выяснили, что последующий член подпоследовательности получается из предыдущего домножением на sqrt((1+2/m+1/m^2)*(2^2^...^2; m-1 раз)/2^(2^2^...^2; m-1 раз)). Найдем предел этого коэффициента:
lim(sqrt((1+2/m+1/m^2)*(2^2^...^2; m-1 раз)/2^(2^2^...^2; m-1 раз))) =
= lim(sqrt(1+2/m+1/m^2))*lim(sqrt((2^2^...^2; m-1 раз)/2^(2^2^...^2; m-1 раз))) =
= 1*lim(sqrt((2^2^...^2; m-1 раз)/2^(2^2^...^2; m-1 раз))) =
= lim(sqrt((2^2^...^2; m-1 раз)/2^(2^2^...^2; m-1 раз))) = [k=(2^2^...^2; m-1 раз)]
= lim(sqrt(k/2^k)) = 0.
Отсюда lim(m/sqrt(log(2^2^...^2; m раз))) =
= lim(sqrt((m^2)/(2^2^...^2; m-1 раз))) =
= lim(sqrt(((m+1)^2)/(2^2^...^2; m раз))) =
= lim(sqrt((1+2/m+1/m^2)*(2^2^...^2; m-1 раз)/2^(2^2^...^2; m-1 раз))) * lim(sqrt((m^2)/(2^2^...^2; m-1 раз))) =
= 0*lim(sqrt((m^2)/(2^2^...^2; m-1 раз))) = 0.
Возьмем произвольную достаточно большую m. Пусть n1=(2^2^...^2; m раз), n2=(2^2^...^2; m+1 раз). Найдем предел отношения n1+1 члена последовательности к n1-ому. lim(((2^log*(n1+1))*sqrt(log n1)/(sqrt(log(n1+1))*2^log*n1)) =
= lim((2^(log*n1+1))/2^log*n1)*lim(sqrt(log n1)/sqrt(log(n1+1))) =
= 2*1 = 2.
Получается, что n1+1 член последовательности стремиться быть в 2 раза больше, чем n1, но так как n1 член стремится к нулю, то и n+1 обязан к нему стремиться. Далее рассмотрим все члены последовательность с номером n: n1+1<n<n2. Так как n берется из указанного интервала, то 2^log*(n+1)=2^log*n=2^log*n2, а раз так, то 2^log*(n1+1)/sqrt(log(n1+1)) > 2^log*(n)/sqrt(log n) > 2^log*(n2)/sqrt(log n2). Как видим, n-ые члены последовательности зажаты между n1 и n2 членами, раз они стремятся к нулю, то и n-ые члены должны к нулю стремиться. В силу произвольности взятой m, а значит и пары (n1, n2) смеем утверждать, что рассмотренны все достаточно большие члены последовательности и их предел равен нулю, что эквивалентно утверждению о том, что 2^log*n=o(sqrt(log n)). чтд.

Добавлено (17.04.2008, 21:07)
---------------------------------------------
У кого по ссылке не переходит, дам так, не выпендриваясь))) http://heap.altlinux.org/alt-doc....ts.html

Добавлено (09.05.2008, 11:45)
---------------------------------------------