Оценивание числа шагов (итераций) алгоритма

Со

II

Со

S_^_J

П

F 2л Л

П

П

П

От

Задачи

П

1 + ^ ^ (E(^I S ^) + Edr^'I Si,)) = -1 + -У(Eу/-1 + Eг_п-Л i =i п 1 + - У Eг_г-1 = п - 1 + - У Er_fc.

=п-1+-п

= П П 1=1 п п-1 = п-1 + -У Eг,₁ = п ² i =l fc=o

i =i

§ 8. Функция затрат рандомизированного алгоритма

Итак,

п-1

Ег = п - 1 + - У Er_k, Ег₀ = 0.

fc=0

Такого вида соотношения уже встречались в предыдущем параграфе, и по аналогии с (7.1) мы находим

Е_Хп = 2п In п + 0{п). (8.3)

Возвратимся к рандомизированной быстрой сортировке. Для дан­ного массива длины п математическое ожидание затрат, измеряемых числом сравнений, полностью определяется значением п. Поэтому, например, сложность в худшем случае, т. е. максимум математиче­ских ожиданий рассматриваемого вида для массивов длины п, есть просто математическое ожидание, найденное при рассмотрении это­го п. Мы можем переписать (8.3) как соотношение для сложности f_QS(n) по числу сравнений рандомизированной быстрой сортировки:

f_QS(n) = 2 n In п + 0(п).

Вновь можно заметить, что число перемещений, требуемое ран­домизированной быстрой сортировкой для конкретного массива, не превосходит числа сравнений, домноженного на некоторую констан­ту, откуда сложность в среднем Т' (п) по числу перемещений эле­ментов допускает оценку 7^_s(n) = 0{п log п). Как и обычная быстрая сортировка, рандомизированная быстрая сортировка не использует дополнительных массивов, поэтому S g_S(n) = 0(l).

Сложность рандомизированной быстрой сортировки как по числу сравнений, так и по числу перемещений элементов допускает оцен­ку 0(n log п). Пространственная сложность по числу одновременно хранимых дополнительных величин, равных каким-то элементам ис­ходного массива, допускает оценку 0(1).

При использовании принципа «из двух заданий первым выполня­ется более простое», мы получаем, согласно теореме 7.1, для сложно­сти по объему стековой памяти оценкуJog₂ п.

Совпадению сложностей f_QS(n) и T _QS(n) можно дать объясне­ние: случайный выбор разбивающего элемента, предпринимаемый на каждом этапе сортировки, эквивалентен тому, что мы меняем порядок исходного массива случайным образом и затем применяем «обычную» быструю сортировку; но равенство сложностей такого ро­да не обязано иметь место для других алгоритмов, — все-таки речь идет о математических ожиданиях случайных величин, определенных

Глава 2. Сложность в среднем

на разных вероятностных пространствах. Например, можно несколь­ко ускорить рандомизированную быструю сортировку, если разбива­ющий элемент определять путем случайного выбора без возвращения трех элементов массива и последующего определения второго по ве­личине из этих трех; можно показать, что тогда вместо 2 n I n n + O{n)

возникнет у n I n n + O{n), и совпадения сложностей обычной и ран­домизированной быстрой сортировки уже не будет.

Возвращаясь к примеру 3.1, мы видим, что, основываясь на ран­домизированной быстрой сортировке, можно получить алгоритм по­строения выпуклой оболочки данных n точек координатной плоскости, имеющий сложность в среднем O{n log n) по общему числу операций.

При нахождении или оценивании сложности какого-либо рандоми­зированного алгоритма часто не возникает необходимости детального рассмотрения всевозможных сценариев. Бывает достаточно рассмот­реть сходное с (8.2) разложение пространства сценариев и применить формулу полного математического ожидания. Даже если множество всех сценариев бесконечно, разложение вида (8.2) можно выбрать ко­нечным.

Пример 8.2. Массив x_ъx₂,...,x_n назовем массивом, содержащим большинство, если больше половины его элементов имеют равные значения. Пусть над элементами массивов разрешена операция про­верки равенства двух элементов, будем называть эту операцию срав­нением. Пусть для данного массива, содержащего большинство, тре­буется найти i, l^i^n, такое, что значение x_i принадлежит боль­шинству значений элементов x₁,x₂,...,x_n. Один из возможных ран­домизированных алгоритмов решения этой задачи состоит в том, что i выбирается случайно (распределение вероятностей равномер­но), а затем проверяется, удовлетворяет ли x_i поставленному усло­вию, — сравнений на эту проверку уйдет не более n- 1. Если x_i не подходит, то все повторяется. Сложность в среднем по числу срав­нений этого алгоритма не превосходит 2(n - 1). В самом деле, про­странство всех сценариев разлагается на два события: первая попыт­ка найти нужное i оказывается удачной и, соответственно, эта по­пытка оказывается неудачной. По формуле полного математического ожидания имеем для искомого среднего a:

a ^ p (n -1) + (1- p)(a + n -1).

Отсюда a ^-(n -1) < 2(n -1). p

Доказательство имеется, например, в [59, разд. 3.7].

Задачи

Еще один путь получения этого же результата. Так как вероят­ность p удачного выбора индекса i больше половины, то математи­ческое ожидание количества попыток, которые потребуются для полу­чения удачного значения i, меньше двух. Отсюда среднее число срав­нений a меньше, чем 2(n - 1).

Теоретически нет никакого препятствия к тому, чтобы при опре­делении функции затрат рандомизированного алгоритма взять вме­сто математического ожидания максимум затрат по соответству­ющим сценариям (при таком подходе рандомизированная быст­рая сортировка имеет квадратичную сложность). Но обычно для рандомизированных алгоритмов рассматриваются усредненные зат­раты.

Добавим в заключение, что правомерен взгляд на рандомизиро­ванные алгоритмы, при котором каждому возможному входу сопо­ставляется вероятностное пространство обычных детерминирован­ных алгоритмов¹. Если в этой связи вернуться к примеру 8.1, то можно заметить, что для разрезания полоски бумаги каждый из рас­сматриваемых сценариев задает конкретный детерминированный ал­горитм разрезания.

Мы вернемся к этому в § 18.

23. Верно ли, что для рассмотрения сложности в среднем некото­
рого алгоритма требуется задание распределения вероятностей

а) на множестве всех допустимых входов?

б) на каждом из множеств всех входов фиксированного размера?

24. Как говорилось при обсуждении асимптотического закона рас­
пределения простых чисел, в [39] приводится элементарное доказа­
тельство неравенств Чебышева с C = 6, c = 1 / 3. Добавим, что наибо­
лее легко доказывается нижняя оценка

π (n) > -—,

справедливая для всех n > 1. Доказать, что сложность в среднем алго­ритма пробных делений не является полиномиально ограниченной, используя для этого только последнее неравенство и не прибегая к полному варианту асимптотического закона распределения простых чисел.

См., например, [55].

Глава 2. Сложность в среднем

Указание. Предположение о том, что V (m) < 2^{3 m/ 4} для всех т > т₀, позво­лило бы, исходя из равенства

я(2^т) = я(2^т°) + У(т₀ + 1) + У(т₀ + 2) +... + V(m),

вывести верхнюю оценку я(2^ш) = 0(2^{3ш / 4}), что вступило бы в противоре-

чие с неравенством я(2^т)>с— с положительной константой с. Поэтому существует последовательность тп₁ <гп₂ <... натуральных чисел таких, что V (m _;) > 2^{3 m} ' ^{/ 4}, i = l,2,... Можно рассмотреть (5.5) для тп = тп₁,тп₂,...

25. Сложность по числу перемещений (обменов) в среднем для
сортировки выбором при условии, что мы исключаем обмены вида

x _t<— *Хъ, не превосходит п - 2 + -, где п—длина массива.

Указание. В перестановках из П_п среднее число элементов a, l^ i ^ n -1,

таких, что a_t=i, есть --------- (см. пример 6.1).

26. Найти среднее число присваиваний m:=... при выполнении
алгоритма поиска наименьшего элемента массива:

тп:=х₁;

for i = 2 to п do

if Xi<m then т:=х_; fi od

Предполагается, что все возможные взаимные порядки элементов в исходном массиве длины п являются равновероятными; в качестве размера входа берется п.

Указание. Рассмотреть разложение всего вероятностного пространства в сумму двух событий: последний элемент исходного массива является его наи­меньшим элементом (вероятность равна -) и соответственно последний эле-

п
мент исходного массива не является его наименьшим элементом (вероят­
ность равна------). Пусть s (n) обозначает искомое математическое ожидание.

п Показать, что условное математическое ожидание исследуемого числа при­сваиваний, соответствующее первому событию, есть s (n - 1) + 1, а условное математическое ожидание, соответствующее второму событию, есть s(n - 1). Пользуясь формулой полного математического ожидания, вывести отсюда ре­куррентное соотношение для s(n) и найти его решение, удовлетворяющее условию 5(1) = 1.

27. Пользуясь дискретным аналогом формулы Ньютона—Лейбни-

ца, согласно которому £ (/№ + 1) - /№)) = /(" + 1) - /(1), вычис-

fc=i

лить сумму 2 ттт. — Тл, входящую в (7.3).

Задачи

28. Исходя из (7.3), пользуясь приемом оценки сумм из прило­жения B и результатом из предыдущей задачи, доказать неравен­ство Гд₅(п) ^2 n ln n, из которого будет следовать, что величина 0{п) в правой части (7.4) отрицательна.

29. Вернемся к задаче 8. В качестве алгоритма с указанными свой­ствами можно предложить следующий: при наличии вагонов на пра­вой стороне узла к операции В прибегаем лишь тогда, когда на ле­вой стороне невозможно увеличить на 1 число вагонов с правиль­ным чередованием цветов с помощью какой-то из операций МИМО и ИЗ; в остальных случаях выполняется одна из операций МИМО и ИЗ, если возможны обе, то первая из них. Как и в задаче 8, счи­таем, что черных и белых вагонов по п штук, и п — размер входа. Какова сложность по числу сортировочных операций этого алгорит­ма в среднем?

Указание.^г Можно доказать следующие три утверждения.

1) Предположим, что в исходном расположении первый вагон на правой стороне белый. Тогда число сортировочных операций, требующихся алгорит­му, равно Зп - к, где к есть количество максимальных сплошных последо­вательностей черных вагонов в исходном расположении (непосредственно слева и справа от каждой такой сплошной последовательности нет черных вагонов, таков смысл «максимальности»).

2) Вновь предположим, что в исходном расположении первый вагон на правой стороне белый. Тогда количество исходных расположений, в которых имеется ровно к максимальных сплошных последовательностей черных ва­гонов, есть (J (J.

3) ^{- п}-1^п-1 = 2^п-2,~,n-k к п й в ^{П -} (п-к)^ПП-¹

=

_к=1 n-k к п

Из первых двух утверждений выводится, что искомая сложность в сред­нем есть

2 n + 2 • — =

третье утверждение позволяет получить из этого, что интересующая нас

n (5 n -3) 5 1

сложность есть —----- — = -п +

L = П + -+о(1).

30. (Задача не связана со сложностью в среднем, но приводит к ре­куррентному соотношению, которое решается сходно с (7.2).) Дока­зать, что для любого Z > 0 можно, не применяя клей, построить из костяшек домино, длина каждой из которых равна 2, навес длины Z

Решение принадлежит А.П.Фокину.

Глава 2. Сложность в среднем

Рис. 11. Навес из костяшек домино.

(рис. 11). Предложить алгоритм конструирования таких навесов, тре­бующий O (el) костяшек.

Указание. Будем характеризовать навес из n костяшек неотрицательными числами l _1; l ₂,..., l_n, где l_i — расстояние от правого края i -й сверху костяшки до вертикальной (пунктирной на рис. 11) линии, проходящей через правый край 1-й, т. е. самой верхней, костяшки. (Таким образом, l_t = 0, l_n = l.) Считая, что вес каждой костяшки равен 1, можно показать, что условием равновесия является система неравенств

l_{i +1<}^ai+ⁱ)+^fe+ _i)+-+^a i +ⁱ), i =i,2,..., n -i

(каждое такое неравенство означает, что центр тяжести конструкции из i верхних костяшек не выходит за правый край (i + 1)-й костяшки). Самый длинный навес получается тогда, когда числа l _1; l ₂,... подчинены рекуррент­ному соотношению

l_i+i = i > l i=°-

Далее можно идти тем же путем, что и при решении соотношения (7.2) и т. д.

31. Перестановка (a_ъ a₂,..., a_n) е П _n называется полной, если a_i ф i, i = l,2,...,n. Вероятность d_n = P _n (D_n) события D_n, состоящего в том, что данная перестановка является полной, равна 0 при n = 1 и равна

1.-1. +... + ^- L (8.4)

при n > 1 (следствие: lim d_n = -).

Задача о значении d_n широко известна как задача о шляпах. На собрание, состоявшееся поздно вечером, n его участников пришли в шляпах и оставили их в раздевалке, а когда собрание окончилось, разобрали шляпы наугад в темноте (в раздевалке перегорела лам­почка) и разошлись по домам. Какова вероятность того, что каждый пришел домой в чужой шляпе?

Указание. Для любого r такого, что СЩЩn, можно рассмотреть ве­роятность p (n, r) того, что перестановка длины n имеет ровно r непо-

Задачи

движных точек (ровно г человек пришли домой в своих шляпах). То­гда р(п,0) + р(п, 1) +... +р(п,п) = 1. Далее надо доказать, что р(п,г) =

= (")-, ---------- г— ------ тР(" - г, 0) = -р(п - г, 0), откуда будет следовать, что

г пуп- 1)...(п -г) г!

^ d „ + Y[ dn -! + ^„-! +... + (_-TjA-! + ^ d o = 0.

С учетом d ₀ = 1 последнее соотношение однозначно определяет все d_t,d₂,... Остается убедиться, что подстановка значений (8.4) в левую часть этого со­отношения дает 0. Подставляя т-77 +?7-о7 + --- + i^, r = °> *> •••> ^п, в левую часть этого соотношения, получим J] ^- .^ (роль г играет п - j).

Слагаемые этой суммы можно перегруппировать так, чтобы внутри группы значение i+j было постоянной величиной I. Это даст

ZjZj (Z- i)! i! Z_iJ! Zj (Z- i)! i P ' '

!=0 i =0 г=о;=o

последний шаг доказательства очевиден.

32. При быстрой сортировке (в любом из рассмотренных ее ва­риантов) число пар индексов (i,j), попадающих в стек отложенных заданий, не превосходит длины п исходного массива.

33. Верно ли, что определение усредненных затрат некоторого рандомизированного алгоритма требует задания распределения ве­роятностей

а) на множестве всех допустимых входов?

б) на каждом из множеств всех входов фиксированного размера?

34. Если измерять затраты рандомизированной быстрой сортиров­
ки количеством обращений к генератору случайных чисел, то слож­
ность этой сортировки есть величина порядка п. То же самое верно,
если в определении функции затрат вместо математического ожида­
ния взять максимум затрат по соответствующим сценариям.

35. Идея, лежащая в основе быстрой сортировки, может быть
использована для нахождения rn-го наименьшего элемента среди
а_ъа₂,...,а_п,1^т^п (самый маленький элемент—это 1-й наимень­
ший, следующий элемент —2-й наименьший и т.д.). Разбиение мас­
сива с использованием случайно выбранного разбивающего элемента
порождает два массива длины i - lиn - i при некотором 1 ^ i ^ п. Ес­
ли т = i, то поиск закончен, если т ^ i - 1, то далее рекурсивно нахо­
дится т-й наименьший в первом массиве, а если т > i, то рекурсивно
находится (т - 0-й наименьший во втором массиве. Можно ввести
сложность по числу сравнений при рассмотрении двух параметров

Глава 2. Сложность в среднем

n, m размера входа. Беря максимум этих сложностей по всем m та­ким, что l^ m ^ n, определяем сложности T{n), T{n) по числу срав­нений в худшем случае и в среднем с использованием n в качестве размера входа. Показать, что T{n) = Q{n²) и T (n) < 4 n.

Указание. Возьмем U (n) = max T(k). Очевидно, что U(n) не убывает при

ЫЫ n

возрастании n и что T(n) ^ U (n). Доказывается неравенство

U (n) г£ i(U (n - 1) + тах{ U (1), U n - 2)} +... n

... + max{ U (n - 2), U (1)} + U (n - 1)) + n - 1, из которого, в силу неубывания U (n), следует

U (n)s£-(U (n -l) + U (n -2) +... + U (| _n J)) + n. Отсюда с помощью индукции выводится, что U (n) < 4 n для всех n > 1.

36. В инверсионном векторе (b_ъ b₂,..., b_n) произвольной переста­
новки (a ₁, a ₂,..., a_n)бП _n каждая компонента b_i равна количеству це­
лых j таких, что 1 ^ j <i и a_j >a_i. Например, инверсионный вектор
перестановки (2, 4, 3,1, 6, 5) —это (0, 0,1, 3, 0,1). Показать, что каж­
дому целочисленному вектору (b_ъ b₂, •••, b_n), для которого 0 ^ b_i < i,
i = 1, 2,..., n, соответствует некоторая перестановка длины n, для ко­
торой этот вектор является инверсионным.

Указание. Очевидно, что если b_n = k, 1Цk<n, то a_n=n-k, и это со­ображение приводит к алгоритму построения (a ₁, a ₂,..., a_n), применимому к любому вектору b, удовлетворяющему оговоренным условиям: просматри­ваем компоненты вектора b, продвигаясь от последней к первой, находим значение соответствующей компоненты перестановки a и удаляем найден­ное значение из множества M, первоначально равного {1, 2,..., n }; при этом значение a_i, i = n,n — 1,..., 1, определяется как (b_i - 1)-й наибольший в мно­жестве M (самый большой элемент —это первый наибольший, следующий по величине элемент —это второй наибольший и т.д.).

37. Показать, что один этап пузырьковой сортировки понижает на
единицу значение каждой неотрицательной компоненты инверсион­
ного вектора перестановки (см. предыдущую задачу) и не изменяет
нулевые компоненты. Показать, что вероятность того, что значение
максимума компонент инверсионного вектора выбранной наугад пе­
рестановки длины n равно k, 0^k<n, есть —j—¹.

Указание ко второй части задачи. Количество векторов (b _1; b ₂,..., b_n), для каждого из которых b_i е N+, 0 г£ bi < i, i = 1,2,..., n, и max{ b _1; b₂,..., b_n} г£ k,

Задачи

1 ^ к ^ п - 1, равно к\ к^{п к г}, так как Ь_; может принимать любое значение между 0 и £ - 1 при £ ^ к и любое значение между 0 и к - 1 для k<i^n.

38. Показать, что математическое ожидание числа этапов пузырь­ковой сортировки совпадает с (6.9).

Указание. Пользуясь решением предыдущей задачи, легко получить, что это математическое ожидание есть

J(fc(fc ⁿ -^fc/c!-(/c-l) ⁿ -^fc+1(fc-l)!),

J_ n!

fc=l

что равно

— (>(fc ⁿ -^fc+1fc! - № - l) ⁿ -^fc+2№ - 1)!) - V(fc - l)"-^k+1(k - 1)! V

' k=l k=l

В упрощении последнего выражения поможет дискретный аналог формулы Ньютона—Лейбница (см. задачу 27).

39. Используя идею решения задачи 35, предложить рандомизи­рованный алгоритм восстановления перестановки длины п по ее ин­версионному вектору (см. задачу 36), имеющий сложность в среднем по числу сравнений 0{п²).

40. Пусть {а_ъа₂,...,а_п)— произвольная перестановка длины п. Ее преобразование

for i = n downto 2 do j:= 1 + random(i - 1); щ^а_} od

может дать любую перестановку длины п с вероятностью —. (Это дает алгоритм построения случайных перестановок с равномерным распределением вероятностей.)

41. Предположим, что у нас нет другого генератора случайных чи­
сел, кроме генератора, в результате обращения к которому появля­
ется 0 или 1 с одинаковой вероятностью | (аналог подбрасывания
монеты), и пусть р, O^ p ^l, — заданное вещественное число. Ка­
ким образом с помощью этого генератора можно определить гене­
ратор randp, в результате обращения к которому появляется 0 или 1
с вероятностями соответственно р и 1 - р (незначительные отклоне­
ния допустимы)? Сложность в среднем алгоритма получения одного
случайного числа с помощью randp должна быть меньше 2 (затраты
определяются числом обращений к изначально имеющемуся генера­
тору).

Указание. Представить р (возможно, с небольшой погрешностью) в виде конечной суммы вида —- Н—| +... + -|, где а_{ —это 0 или 1 для всех £, а к — некоторое целое положительное число.

Глава 2. Сложность в среднем

42. Пусть изначально у нас имеется генератор случайных веще­ственных чисел, принадлежащих отрезку [0,1], и вероятность появ­ления числа, принадлежащего отрезку [а,Ъ], О ^ а ^ Ъ ^ 1, есть Ъ - а. Пусть даны неотрицательные вещественные числа a_n,a-i,...,a та-кие, что a_n + ai +... + a =1. Как определить генератор чисел, при-надлежащих множеству {0,1,...,JV - 1}, такой, что вероятность появ­ления числа к, 0 s= к s= N - 1, равна а_к?

43. Предположим, что у нас нет другого генератора случайных чи­сел, кроме генератора, в результате обращения к которому появляет­ся 0 с вероятностью р или 1 с вероятностью 1 - р, причем о р мы ничего не знаем, кроме того, что р^0ир/1. Как с помощью этого генератора можно сконструировать генератор, в результате обраще­ния к которому появляется 0 или 1 с одинаковой вероятностью 1 / 2?

Указание. Порождая подряд две цифры с помощью имеющегося генера­тора, мы получаем комбинации 0,1 и 1, 0 с одинаковой ненулевой вероят­ностью.

44. (Продолжение предыдущей задачи.) Чему равно математиче­ское ожидание числа обращений к изначально имеющемуся генерато­ру случайных чисел при построении последовательности пар до появ­ления 0,1 или 1, 0? Найти сложность в среднем алгоритма получения к «равновероятных» нулей и единиц с помощью сконструированного генератора (затраты определяются количеством обращений к изна­чально имеющемуся генератору). Можно ли указать значения р, для которых эта сложность имеет минимальное и, соответственно, мак­симальное значение?

45. Предложенную в указании к задаче 43 идею обобщить на слу­чай, когда необходимо сконструировать генератор random (JV), N^ 1, описанный в § 8. Найти сложность в среднем алгоритма получения к равновероятных случайных чисел из отрезка [0,JV-1] (затраты определяются числом обращений к изначально имеющемуся генера­тору).

46. Сохранится ли для сложности в среднем формула 2 n In п + 0(п), если в задаче о разрезании полоски клетчатой бумаги на отдельные клетки (см. пример 8.1) считать, что плата за вырезание одной слу­чайно выбранной клетки равна не п -1, а п рублей? Тот же вопрос, если эта плата составляет п² рублей.

47. Известное утверждение (теорема Дирихле, 1849 г.), что два

случайных числа x, y eN⁺ с вероятностью Р, равной —, оказываются взаимно простыми, имеет тот смысл, что если ввести в рассмотрение число М{п), равное количеству пар (х, у) таких, что х и у взаимно

Задачи

просты и, дополнительно, 1 ^ x, y ^ n, то предел lim — т- существует

и равен 4. Предполагая (не обосновывая и не вникая в то, мож­но ли это^обосновать; это соответствует «физическому уровню стро­гости»), что множество N⁺ может быть превращено в вероятност­ное пространство так, что случайное x eN+ кратно фиксированно­му d eN⁺ с вероятностью -, можно предложить несколько довольно

простых доказательств равенства P = —. Для этого можно восполь­зоваться тем, что

7 =

Zj n 2 6

n =1

(доказано Эйлером в 1734 г.) или свойством дзета-функции Римана, согласно которому

V 1 П 1

Z-in^s 11 1 - p^s

n =1 p — простое

и которое справедливо, например, для всех целых s > 1, и, в частно­сти, для s = 2.

В упомянутых выше предположениях доказать равенство P = —, используя следующие подходы.

а) Для произвольного d е N⁺ вычислить вероятность ip{d) того,
что для случайных x, y eN+ выполнено d = нод(x, y). Из равенства

P = 1 - Х> d определить P.^г

d=2

б) Для произвольного простого p вычислить вероятность т/>(p) то­
го, что по крайней мере одно из случайных x, y е N+ не делится на p.
Из равенства P = V'(p) определить P. ²

p — простое

Указания. а) _V(d) = -^; б) т/>(p) = 1 - \.

Для того чтобы сделать доказательство «настоящим», надо для произволь­ного n eN⁺ детально рассмотреть ситуацию 1 ^ x,y ^ n и перейти к пределу при n^ оо, что потребует более кропотливой работы.³

См. [19, разд. 4.5.2].

См. [50, гл. I, разд. 3, прим. 3.3].

См. [19, разд. 4.5.2, упр. 10].

Глава 3

Дата добавления: 2014-01-11