oekaki.png6 Кб, 400x400
тест тест /testtest/ Тест 25783 2 В конец треда | Веб
ghhh!jLD3QRtGw6 2 29441 1
тест
3 29477 2
4 29481 2
5 29487 1
>>25783 (OP)
h
(Автор этого поста был предупрежден.)
6 29557 2
out1.webm8,3 Мб, webm,
320x210
7 30717 1
out2.webm8,3 Мб, webm,
320x210
8 30719 1
out3.webm8,4 Мб, webm,
320x210
9 30720 1
out4.webm7,5 Мб, webm,
180x240
10 30721 1
out5.webm8 Мб, webm,
260x240
11 30722 2
out6.webm8,3 Мб, webm,
320x180
12 30724 2
out6.webm11,7 Мб, webm,
640x480
13 30725 1
out6.webm8,2 Мб, webm,
320x180
14 30726 1
out7.webm11,1 Мб, webm,
640x360
15 30727 1
test2.webm9,4 Мб, webm,
400x720
16 30732 1
test2.webm5,8 Мб, webm,
400x720
17 30733 2
test3.webm5,9 Мб, webm,
400x720
18 30734 1
test4.webm5,9 Мб, webm,
400x720
19 30735 1
test5.webm4 Мб, webm,
400x720
20 30736 1
test3.webm5,9 Мб, webm,
400x720
21 30737 1
test3.webm5,8 Мб, webm,
400x720
22 30738 1
test3.webm5,8 Мб, webm,
400x720
23 30739 2
vp9test.webm5,3 Мб, webm,
400x720
24 30741 1
25 42645 1
trew
26 42648 1
test
27 43099 1
`для оформления кода`
28 43100 1
	about
29 43104 1
tvdhtfjg
Test 30 46499 1
Test
31 46502 1
test
32 46503 1
test
33 46513 1
sassassassas
34 46557 1
test
35 46558 1
36 46559 2
1
37 46900 1
Тест
38 46901 1
weq
39 46907 1
test
40 46919 1
sa
41 46920 1
test
42 46922 1
test
Аноним 43 46931 1
44 46933 1
test
45 46982 1
test
46 46987 1
еуые
47 50936 1
zxzx
48 50976 1
jhgnb
49 53835 1
50 53838 1
yugyug 51 54236 1
hjgjhguyg
52 54238 1
.
!MRRv.BWxgg 53 54282 1
test
54 54283 1
test
55 54284 1
56 54286 1
57 54636 1
тест
58 55424 4
test
59 55737 1
test
60 55738 1
61 55765 1
62 55767 1
Test
63 55771 1
Навернул по совету этого китайского тинейджера кинхс аватар, оказалось довольно годно.
нотабли:
-хомаж на вуксии в виде всяких приставок оэлдэ перед именами,
-то, как быстро китайсы выстраиваются в иерархию (босс, мастер, годя),
-ФРАЗОЧКИ (твойдедбля (laozi), "ты зойчем врагу мораль поднимаешь, а нас расстраиваешь, IS IT PROPER?"
-внезапно лучшее, что я видел про онлайн игры-ВР, включая САО, хаксы, бляму, аксельворлдо - хотя бы не кривит ебло в оскомине присутствие этого контента, видимо из-за того, что годный микс с реальной жизнью киберкотлет
-everyone is scheming, even positive characters (moreso positive characters)
-лэйдбэчный протаг с постоянной faint smile на ебале, я все в вуксия пытался представить себе, как они там постоянно с фейнт смайл ходят, а вот как
из минусов
- стандартное мейл-фимейл негодование

ебаная шарада на слово из спам-листа
64 55772 1
65 55774 2
68 55841 1
69 55847 1
test
70 55850 1
Test
71 55876 1
72 56023 1
test
73 56026 1
test
74 64755 2
fasfa
75 64756 1
76 64863 1
test
77 65443 1
test
78 65483 1
test
79 67116 1
test
sage 80 75871 1
test
81 75872 1
test2
82 75881 1
test
83 77545 1
image.jpeg1 Мб, 1150x1536
84 77555 1
85 77561 1
test
86 77562 1
xcasd
87 77694 1
test
JewsIlumminati.webm3,8 Мб, webm,
1024x576, 0:39
88 77804 1
test
Kak otmetil.webm2,6 Мб, webm,
640x360, 0:14
89 77805 1
90 77811 1
test
91 77812 1
zzzz
92 77820 1
93 77821 1
tst
94 78271 1
95 78283 1
test
96 78915 1
97 78918 1
98 78920 1
100 78993 1
le pooq
101 79017 1
102 79049 1
Test
103 79077 1
104 79108 1
Test?
105 83462 1
Test
106 83464 1
test
107 83624 1
122
108 83651 1
109 83655 1
test
Аноним 110 83686 1
111 83687 1
fafafaaf
OP!ewxdWBJtu2 112 83872 1
Test
113 84050 1
4d71f921084bf8f602c4b8aec0c60e32-imagepng.png491 Кб, 480x480
114 84370 1
 .png491 Кб, 480x480
115 84371 1
4d71f921084bf8f602c4b8aec0c60e32-imagepng.png491 Кб, 480x480
116 84372 1
4d71f921084bf8f602c4b8aec0c60e32-imagepng.png491 Кб, 480x480
117 84373 1
1534168338436.png491 Кб, 480x480
119 84376 1
120 84377 1
Test
121 84379 1
122 84380 1
123 84385 1
sdf23412
124 84389 2
jghjghj
125 84390 1
Уебан!rGOAfuB3jA 126 84782 1
Уебан!hPBgzqRU72 127 84783 1
Уебан!tvTAuWxzUc 128 84784 1
Well fuck me.
Уебан!sCB0VFRkPE 129 84785 1
You are the scum of earth.
Уебан!zDRyYc9jds 130 84786 2
God is dead.
131 84798 1
132 84849 1
2
133 85093 1
;tf
134 85096 1
135 85103 1
test
136 85514 1
>>29441
5ttttt
137 85516 1
q
138 85526 1
Test
139 85552 1
test
140 85555 1
141 85902 1
ТЕСТ
@
ТЕСТ
@
ТЕСТ
142 85903 1
ТЕСТ
@
ТЕСТ
@
ТЕСТ
143 85907 1
h
144 85929 1
test
145 85933 1
1
146 85952 1
test
147 128251 1
test
148 128253 1
test
149 128289 1
150 128291 1
151 128558 1
gg
152 128563 1
GAMMA
153 128567 1
Test
154 128618 1
test
155 128640 1
156 128641 1
157 128643 1
сосать
158 128656 1
159 128676 1
m
160 140695 1
<iframe width="640" height="360" frameborder="0" src="https://mega.nz/embed#!undefined!cYDgH3yQgAQSZjxsFYDQCBayDUd0WG3FIBS9QmPnqLQ" allowfullscreen></iframe>
161 140697 1
test
162 140698 1
test
163 140703 1
ede
164 140706 1
t
165 140712 1
166 140713 1
Nn
167 140714 1
Test
168 140715 0
Test
sage 169 146961 1
Э-ээ, ну, как бы, м-мм, да, вот.

CLRS — Appendix C: Counting

Глава про какой-то очень маленький кусочек комбинаторики, покрывающая только самые-самые базовые понятия и основные формулы. Настолько базовые вещи, что там даже отдельно упомянуты формальное определение k-строки (просто упорядоченная последовательность из k элементов какого-то конечного множества). Ну, и формулы для перестановок и сочетаний там тоже есть, да.

Тем не менее, даже тут встретились какие-то небольшие трудности, пока разбирался. Вот, например, в доказательстве формулы для нижней границы биномиального коэффициента: (nk) ≥ (n/k)k. Сама по себе формула доказывается в два шага, но только, если знаешь вот это неравенство: (n−m)/(k−m) ≥ n/k (для 0 ≤ m < k ≤ n). Э-э, и тут я немного запутался сам в себе. Я точно помню, что доказательство этого неравенства вызывало какие-то адские трудности, но сейчас не вижу тут ничего сложного: достаточно просто сделать несколько эквивалентных преобразований:

> (n−m)/(k−m) ≥ n/k


> (n−m)/n ≥ (k−m)/k


> 1/n ≤ 1/k


> n ≥ k


Хотя, возможно, всё из-за того, что я увидел это доказательство вывернутым наизнанку (то есть n ≥ k последовательно преобразовывалось до неравенства, которое мы доказываем), что как бы формально более корректно, но выглядит при этом как последовательность совершенно случайных действий, которые совершенно случайным образом приводят нас к доказываемуму утверждению. В общем, это ещё один пример того, как по-дурацки записанное доказательство делает из простейшего утверждение какой-то роскет скиенсе, недоступный для понимания тупице вроде меня. И примеров таких очень-очень много, я вообще в чужих доказательствах с трудом ориентируюсь, если они не разбиты логически на пункты и не отмечено вкратце, что делается в каждом пункте. Большинство доказательств просто пишутся сплошной стеной текста, сдобренной фразочками вроде «доказательство этого утверждения предоставляется читателю в качестве упражнения» и «следует из утверждения 2.6.5» (формулировка которого, естественно, находится где-то далеко позади, если вообще не в другой книжке).

Ну, ладно, это была только нижняя граница для биноминального коэффициента. Верхняя же доказывается просто выводится из одной из оценок Стирлинга для факториала (там вроде довольно много всяких формул, но я помню только вот эти две: n! ~ √(2πn)·(n/e)n и √(2π)·nn+1/2·e−n ≤ n! ≤ e·nn+1/2·e−n). В общем, всё сводится вот к этому:

> (n/k)k ≤ (nk) ≤ (e·n/k)k


И, наверное, это круто.

На этом сама глава закончилась, но за ней следовала целая куча упражнений, которые не столько были на закрепление материала (которого по сути особо и не было), но на доказательство всяких новых штук.

CLRS — Appendix C: Counting (Exercises)

C.1-1

>How many k-substrings does an n-string have? (Consider identical k-substrings at different positions to be different.) How many substrings does an n-string have in total?



Ну, это совсем простая задачка, как и большинство из тех, которые есть к этой главе, но интересны они все тем, что у них, помимо простого решения в лоб, есть особое комбинаторное решение.

Вот, например, в этой задачке можно, конечно, просто просуммировать число строк длины 1, длины 2, и так далее до n и получить (n+12). Но гораздо проще представить, что между символами в строке можно поставить условные «маркеры» (перед первым симоволом, после первого, ..., перед последним и после последнего, то есть всего — n+1) и тогда любая подстрока задаётся выбором каких-то двух «маркеров», стоящих по разные стороны относительно подстроки. Ну, а число способов выбрать 2 элемента из n+1 — это и есть (n+12).

Собственно, примерно в такой же манере решаются и все остальные задачки на комбинаторику. И это уже было, кстати, в 6.042J.

Вот, например:

> k·(nk) = n·(n-1k−1)


Эту формулу можно проинтерпретировать как «число способов собрать команду из k человек (выбирая из n претендентов) и выбрать в ней капитана». Слева — мы сначала собираем команду, а потом выбираем в ней капитана, а справа — сначала выбираем n способами капитана, а потом капитан добирает себе в команду оставшихся k−1 человека. То есть разными способами считаем одно и то же.

> (nk) = (n−1k) + (n−1k−1)


Вот эта формула вроде довольно часто встречается и даже как-то по-умному называется. Тут выделяется какой-то конкретный особый предмет среди всех n предметов, из которых мы выбираем коллекцию из k штук, и тогда все возможные наборы из k предметов делятся на два дизъюнктных множества: множество наборов, в которых этот особый предмет присутствует, и наборы, в которых его нет.

Последний факт, кстати, используется при построении Треугольника Паскаля, про который я вроде когда-то слышал, но никогда не знал толком, что это. Как оказалось, это просто последовательность строк, записанных друг под другом, где в n-ой строке выписаны n биноминальных коэффициентов: начиная с (n0), и, заканчивая (nn). Получается такой прямоугольный треугольник, у которого по границе стоят единицы, а остальные элементы вычисляются как сумма вышестоящего и слева-сверху-стоящего элементов. Полезно, если ты не знаешь коэффициенты для Бинома Ньютона для какой-то там большой степени: можно быстро просуммировать на бумажке и получить их выписанными в одном из рядов в треугольнике.

С.1-10

>Покажите, что (nk) принимает максимальное значение в k = [n/2].


Доказательство на пикрелейтеде. Я его отдельно довольно подробно расписал, потому что один раз умудрился запутаться во всех этих индексах и доказать неправильно. Сейчас вроде как нормально.

С.1-11

> (nj+k) ≤ (nj)·(n−jk)


Вроде очевидно, но заставляет задуматься. Может показаться, что верно и более строгое утверждение, с равенством, но на деле это не так: слева — число способов выбрать j+k элементов из n, а справа — число способов сначала выбрать j, а потом k элементов из того же набора. То есть во втором случае нам чуть-чуть важен порядок, так что в каком-нибудь простом примере на множестве {A, B} и j=1, k=1 будет выполняться строгое неравенство: с одной стороны, можем выбрать только одним способом сразу два элемента, с другой, последовательно элементы мы можем выбрать двумя способами: либо сначала A, а потом B, либо сначала B, а потом A.

C.1-13

>Use Stirling's approximation to prove that (2nn) = чему-то там


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

Остаются только две приложенных картинки.

Первая из двух, но третья из четырёх, вот такая математика — доказательство какого-то очередного глупого неравенства. ОБРАТИТЕ ВНИМАНИЕ на два «короче» внизу и на то, что я, будучи человеком, который неспособен сложить два двузначных числа в уме, героически посчитал производную сложной функции, доведя её до состояния, где можно понять, что производная имеет какой-то там знак на каком-то там интервале. А само доказательство получилось каким-то заковыристым, плюс наверняка там полная ерунда с областями определения n и k, так что там в некоторых местах могут быть деления на ноль, которые надо бы отдельно рассматривать, но мне всё равно, вот. А доказательство для второй половины промежутка там следует просто из такой своего рода «симметричности» биноминального коэффициента.

На последней картинке на мой взгляд человека, не обременённого особыми познаниями во всяких математиках — просто какие-то формулы, которые как-то магически друг из друга выводятся. Какой смысл у всего этого, что такое binary entropy function, почему мы обозначали k = λn — не знаю.

Короче, чёт такое. Уже предвосхищаю слетевшую разметку с поста.
sage 169 146961 1
Э-ээ, ну, как бы, м-мм, да, вот.

CLRS — Appendix C: Counting

Глава про какой-то очень маленький кусочек комбинаторики, покрывающая только самые-самые базовые понятия и основные формулы. Настолько базовые вещи, что там даже отдельно упомянуты формальное определение k-строки (просто упорядоченная последовательность из k элементов какого-то конечного множества). Ну, и формулы для перестановок и сочетаний там тоже есть, да.

Тем не менее, даже тут встретились какие-то небольшие трудности, пока разбирался. Вот, например, в доказательстве формулы для нижней границы биномиального коэффициента: (nk) ≥ (n/k)k. Сама по себе формула доказывается в два шага, но только, если знаешь вот это неравенство: (n−m)/(k−m) ≥ n/k (для 0 ≤ m < k ≤ n). Э-э, и тут я немного запутался сам в себе. Я точно помню, что доказательство этого неравенства вызывало какие-то адские трудности, но сейчас не вижу тут ничего сложного: достаточно просто сделать несколько эквивалентных преобразований:

> (n−m)/(k−m) ≥ n/k


> (n−m)/n ≥ (k−m)/k


> 1/n ≤ 1/k


> n ≥ k


Хотя, возможно, всё из-за того, что я увидел это доказательство вывернутым наизнанку (то есть n ≥ k последовательно преобразовывалось до неравенства, которое мы доказываем), что как бы формально более корректно, но выглядит при этом как последовательность совершенно случайных действий, которые совершенно случайным образом приводят нас к доказываемуму утверждению. В общем, это ещё один пример того, как по-дурацки записанное доказательство делает из простейшего утверждение какой-то роскет скиенсе, недоступный для понимания тупице вроде меня. И примеров таких очень-очень много, я вообще в чужих доказательствах с трудом ориентируюсь, если они не разбиты логически на пункты и не отмечено вкратце, что делается в каждом пункте. Большинство доказательств просто пишутся сплошной стеной текста, сдобренной фразочками вроде «доказательство этого утверждения предоставляется читателю в качестве упражнения» и «следует из утверждения 2.6.5» (формулировка которого, естественно, находится где-то далеко позади, если вообще не в другой книжке).

Ну, ладно, это была только нижняя граница для биноминального коэффициента. Верхняя же доказывается просто выводится из одной из оценок Стирлинга для факториала (там вроде довольно много всяких формул, но я помню только вот эти две: n! ~ √(2πn)·(n/e)n и √(2π)·nn+1/2·e−n ≤ n! ≤ e·nn+1/2·e−n). В общем, всё сводится вот к этому:

> (n/k)k ≤ (nk) ≤ (e·n/k)k


И, наверное, это круто.

На этом сама глава закончилась, но за ней следовала целая куча упражнений, которые не столько были на закрепление материала (которого по сути особо и не было), но на доказательство всяких новых штук.

CLRS — Appendix C: Counting (Exercises)

C.1-1

>How many k-substrings does an n-string have? (Consider identical k-substrings at different positions to be different.) How many substrings does an n-string have in total?



Ну, это совсем простая задачка, как и большинство из тех, которые есть к этой главе, но интересны они все тем, что у них, помимо простого решения в лоб, есть особое комбинаторное решение.

Вот, например, в этой задачке можно, конечно, просто просуммировать число строк длины 1, длины 2, и так далее до n и получить (n+12). Но гораздо проще представить, что между символами в строке можно поставить условные «маркеры» (перед первым симоволом, после первого, ..., перед последним и после последнего, то есть всего — n+1) и тогда любая подстрока задаётся выбором каких-то двух «маркеров», стоящих по разные стороны относительно подстроки. Ну, а число способов выбрать 2 элемента из n+1 — это и есть (n+12).

Собственно, примерно в такой же манере решаются и все остальные задачки на комбинаторику. И это уже было, кстати, в 6.042J.

Вот, например:

> k·(nk) = n·(n-1k−1)


Эту формулу можно проинтерпретировать как «число способов собрать команду из k человек (выбирая из n претендентов) и выбрать в ней капитана». Слева — мы сначала собираем команду, а потом выбираем в ней капитана, а справа — сначала выбираем n способами капитана, а потом капитан добирает себе в команду оставшихся k−1 человека. То есть разными способами считаем одно и то же.

> (nk) = (n−1k) + (n−1k−1)


Вот эта формула вроде довольно часто встречается и даже как-то по-умному называется. Тут выделяется какой-то конкретный особый предмет среди всех n предметов, из которых мы выбираем коллекцию из k штук, и тогда все возможные наборы из k предметов делятся на два дизъюнктных множества: множество наборов, в которых этот особый предмет присутствует, и наборы, в которых его нет.

Последний факт, кстати, используется при построении Треугольника Паскаля, про который я вроде когда-то слышал, но никогда не знал толком, что это. Как оказалось, это просто последовательность строк, записанных друг под другом, где в n-ой строке выписаны n биноминальных коэффициентов: начиная с (n0), и, заканчивая (nn). Получается такой прямоугольный треугольник, у которого по границе стоят единицы, а остальные элементы вычисляются как сумма вышестоящего и слева-сверху-стоящего элементов. Полезно, если ты не знаешь коэффициенты для Бинома Ньютона для какой-то там большой степени: можно быстро просуммировать на бумажке и получить их выписанными в одном из рядов в треугольнике.

С.1-10

>Покажите, что (nk) принимает максимальное значение в k = [n/2].


Доказательство на пикрелейтеде. Я его отдельно довольно подробно расписал, потому что один раз умудрился запутаться во всех этих индексах и доказать неправильно. Сейчас вроде как нормально.

С.1-11

> (nj+k) ≤ (nj)·(n−jk)


Вроде очевидно, но заставляет задуматься. Может показаться, что верно и более строгое утверждение, с равенством, но на деле это не так: слева — число способов выбрать j+k элементов из n, а справа — число способов сначала выбрать j, а потом k элементов из того же набора. То есть во втором случае нам чуть-чуть важен порядок, так что в каком-нибудь простом примере на множестве {A, B} и j=1, k=1 будет выполняться строгое неравенство: с одной стороны, можем выбрать только одним способом сразу два элемента, с другой, последовательно элементы мы можем выбрать двумя способами: либо сначала A, а потом B, либо сначала B, а потом A.

C.1-13

>Use Stirling's approximation to prove that (2nn) = чему-то там


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

Остаются только две приложенных картинки.

Первая из двух, но третья из четырёх, вот такая математика — доказательство какого-то очередного глупого неравенства. ОБРАТИТЕ ВНИМАНИЕ на два «короче» внизу и на то, что я, будучи человеком, который неспособен сложить два двузначных числа в уме, героически посчитал производную сложной функции, доведя её до состояния, где можно понять, что производная имеет какой-то там знак на каком-то там интервале. А само доказательство получилось каким-то заковыристым, плюс наверняка там полная ерунда с областями определения n и k, так что там в некоторых местах могут быть деления на ноль, которые надо бы отдельно рассматривать, но мне всё равно, вот. А доказательство для второй половины промежутка там следует просто из такой своего рода «симметричности» биноминального коэффициента.

На последней картинке на мой взгляд человека, не обременённого особыми познаниями во всяких математиках — просто какие-то формулы, которые как-то магически друг из друга выводятся. Какой смысл у всего этого, что такое binary entropy function, почему мы обозначали k = λn — не знаю.

Короче, чёт такое. Уже предвосхищаю слетевшую разметку с поста.
sage 170 146962 0
Э-ээ, ну, как бы, м-мм, да, вот.

CLRS — Appendix C: Counting

Глава про какой-то очень маленький кусочек комбинаторики, покрывающая только самые-самые базовые понятия и основные формулы. Настолько базовые вещи, что там даже отдельно упомянуты формальное определение k-строки (просто упорядоченная последовательность из k элементов какого-то конечного множества). Ну, и формулы для перестановок и сочетаний там тоже есть, да.

Условимся, что (n | k) — это биноминальный коэффициент, или же «цэ из эн по ка». Я мог бы записать их вот так: (nk), но тогда из-за того, что здесь слишком много биноминальных коэффициентов, слетает разметка.

Тем не менее, даже тут встретились какие-то небольшие трудности, пока разбирался. Вот, например, в доказательстве формулы для нижней границы биномиального коэффициента: (n | k) ≥ (n/k)k. Сама по себе формула доказывается в два шага, но только, если знаешь вот это неравенство: (n−m)/(k−m) ≥ n/k (для 0 ≤ m < k ≤ n). Э-э, и тут я немного запутался сам в себе. Я точно помню, что доказательство этого неравенства вызывало какие-то адские трудности, но сейчас не вижу тут ничего сложного: достаточно просто сделать несколько эквивалентных преобразований:

> (n−m)/(k−m) ≥ n/k


> (n−m)/n ≥ (k−m)/k


> 1/n ≤ 1/k


> n ≥ k


Хотя, возможно, всё из-за того, что я увидел это доказательство вывернутым наизнанку (то есть n ≥ k последовательно преобразовывалось до неравенства, которое мы доказываем), что как бы формально более корректно, но выглядит при этом как последовательность совершенно случайных действий, которые совершенно случайным образом приводят нас к доказываемуму утверждению. В общем, это ещё один пример того, как по-дурацки записанное доказательство делает из простейшего утверждение какой-то роскет скиенсе, недоступный для понимания тупице вроде меня. И примеров таких очень-очень много, я вообще в чужих доказательствах с трудом ориентируюсь, если они не разбиты логически на пункты и не отмечено вкратце, что делается в каждом пункте. Большинство доказательств просто пишутся сплошной стеной текста, сдобренной фразочками вроде «доказательство этого утверждения предоставляется читателю в качестве упражнения» и «следует из утверждения 2.6.5» (формулировка которого, естественно, находится где-то далеко позади, если вообще не в другой книжке).

Ну, ладно, это была только нижняя граница для биноминального коэффициента. Верхняя же доказывается просто выводится из одной из оценок Стирлинга для факториала (там вроде довольно много всяких формул, но я помню только вот эти две: n! ~ √(2πn)·(n/e)n и √(2π)·nn+1/2·e−n ≤ n! ≤ e·nn+1/2·e−n). В общем, всё сводится вот к этому:

> (n/k)k ≤ (nk) ≤ (e·n/k)k


И, наверное, это круто.

На этом сама глава закончилась, но за ней следовала целая куча упражнений, которые не столько были на закрепление материала (которого по сути особо и не было), но на доказательство всяких новых штук.

CLRS — Appendix C: Counting (Exercises)

C.1-1

>How many k-substrings does an n-string have? (Consider identical k-substrings at different positions to be different.) How many substrings does an n-string have in total?



Ну, это совсем простая задачка, как и большинство из тех, которые есть к этой главе, но интересны они все тем, что у них, помимо простого решения в лоб, есть особое комбинаторное решение.

Вот, например, в этой задачке можно, конечно, просто просуммировать число строк длины 1, длины 2, и так далее до n и получить (n+1 | 2). Но гораздо проще представить, что между символами в строке можно поставить условные «маркеры» (перед первым симоволом, после первого, ..., перед последним и после последнего, то есть всего — n+1) и тогда любая подстрока задаётся выбором каких-то двух «маркеров», стоящих по разные стороны относительно подстроки. Ну, а число способов выбрать 2 элемента из n+1 — это и есть (n+1 | 2).

Собственно, примерно в такой же манере решаются и все остальные задачки на комбинаторику. И это уже было, кстати, в 6.042J.

Вот, например:

> k·(n | k) = n·(n-1 | k−1)


Эту формулу можно проинтерпретировать как «число способов собрать команду из k человек (выбирая из n претендентов) и выбрать в ней капитана». Слева — мы сначала собираем команду, а потом выбираем в ней капитана, а справа — сначала выбираем n способами капитана, а потом капитан добирает себе в команду оставшихся k−1 человека. То есть разными способами считаем одно и то же.

> (n | k) = (n−1 | k) + (n−1 | k−1)


Вот эта формула вроде довольно часто встречается и даже как-то по-умному называется. Тут выделяется какой-то конкретный особый предмет среди всех n предметов, из которых мы выбираем коллекцию из k штук, и тогда все возможные наборы из k предметов делятся на два дизъюнктных множества: множество наборов, в которых этот особый предмет присутствует, и наборы, в которых его нет.

Последний факт, кстати, используется при построении Треугольника Паскаля, про который я вроде когда-то слышал, но никогда не знал толком, что это. Как оказалось, это просто последовательность строк, записанных друг под другом, где в n-ой строке выписаны n биноминальных коэффициентов: начиная с (n | 0), и, заканчивая (n | n). Получается такой прямоугольный треугольник, у которого по границе стоят единицы, а остальные элементы вычисляются как сумма вышестоящего и слева-сверху-стоящего элементов. Полезно, если ты не знаешь коэффициенты для Бинома Ньютона для какой-то там большой степени: можно быстро просуммировать на бумажке и получить их выписанными в одном из рядов в треугольнике.

С.1-10

>Покажите, что (n | k) принимает максимальное значение в k = [n/2].


Доказательство на пикрелейтеде. Я его отдельно довольно подробно расписал, потому что один раз умудрился запутаться во всех этих индексах и доказать неправильно. Сейчас вроде как нормально.

С.1-11

> (n | j+k) ≤ (n | j)·(n−j | k)


Вроде очевидно, но заставляет задуматься. Может показаться, что верно и более строгое утверждение, с равенством, но на деле это не так: слева — число способов выбрать j+k элементов из n, а справа — число способов сначала выбрать j, а потом k элементов из того же набора. То есть во втором случае нам чуть-чуть важен порядок, так что в каком-нибудь простом примере на множестве {A, B} и j=1, k=1 будет выполняться строгое неравенство: с одной стороны, можем выбрать только одним способом сразу два элемента, с другой, последовательно элементы мы можем выбрать двумя способами: либо сначала A, а потом B, либо сначала B, а потом A.

C.1-13

>Use Stirling's approximation to prove that (2n | n) = чему-то там


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

Остаются только две приложенных картинки.

Первая из двух, но третья из четырёх, вот такая математика — доказательство какого-то очередного глупого неравенства. ОБРАТИТЕ ВНИМАНИЕ на два «короче» внизу и на то, что я, будучи человеком, который неспособен сложить два двузначных числа в уме, героически посчитал производную сложной функции, доведя её до состояния, где можно понять, что производная имеет какой-то там знак на каком-то там интервале. А само доказательство получилось каким-то заковыристым, плюс наверняка там полная ерунда с областями определения n и k, так что там в некоторых местах могут быть деления на ноль, которые надо бы отдельно рассматривать, но мне всё равно, вот. А доказательство для второй половины промежутка там следует просто из такой своего рода «симметричности» биноминального коэффициента.

На последней картинке на мой взгляд человека, не обременённого особыми познаниями во всяких математиках — просто какие-то формулы, которые как-то магически друг из друга выводятся. Какой смысл у всего этого, что такое binary entropy function, почему мы обозначали k = λn — не знаю.

Короче, чёт такое.
sage 170 146962 0
Э-ээ, ну, как бы, м-мм, да, вот.

CLRS — Appendix C: Counting

Глава про какой-то очень маленький кусочек комбинаторики, покрывающая только самые-самые базовые понятия и основные формулы. Настолько базовые вещи, что там даже отдельно упомянуты формальное определение k-строки (просто упорядоченная последовательность из k элементов какого-то конечного множества). Ну, и формулы для перестановок и сочетаний там тоже есть, да.

Условимся, что (n | k) — это биноминальный коэффициент, или же «цэ из эн по ка». Я мог бы записать их вот так: (nk), но тогда из-за того, что здесь слишком много биноминальных коэффициентов, слетает разметка.

Тем не менее, даже тут встретились какие-то небольшие трудности, пока разбирался. Вот, например, в доказательстве формулы для нижней границы биномиального коэффициента: (n | k) ≥ (n/k)k. Сама по себе формула доказывается в два шага, но только, если знаешь вот это неравенство: (n−m)/(k−m) ≥ n/k (для 0 ≤ m < k ≤ n). Э-э, и тут я немного запутался сам в себе. Я точно помню, что доказательство этого неравенства вызывало какие-то адские трудности, но сейчас не вижу тут ничего сложного: достаточно просто сделать несколько эквивалентных преобразований:

> (n−m)/(k−m) ≥ n/k


> (n−m)/n ≥ (k−m)/k


> 1/n ≤ 1/k


> n ≥ k


Хотя, возможно, всё из-за того, что я увидел это доказательство вывернутым наизнанку (то есть n ≥ k последовательно преобразовывалось до неравенства, которое мы доказываем), что как бы формально более корректно, но выглядит при этом как последовательность совершенно случайных действий, которые совершенно случайным образом приводят нас к доказываемуму утверждению. В общем, это ещё один пример того, как по-дурацки записанное доказательство делает из простейшего утверждение какой-то роскет скиенсе, недоступный для понимания тупице вроде меня. И примеров таких очень-очень много, я вообще в чужих доказательствах с трудом ориентируюсь, если они не разбиты логически на пункты и не отмечено вкратце, что делается в каждом пункте. Большинство доказательств просто пишутся сплошной стеной текста, сдобренной фразочками вроде «доказательство этого утверждения предоставляется читателю в качестве упражнения» и «следует из утверждения 2.6.5» (формулировка которого, естественно, находится где-то далеко позади, если вообще не в другой книжке).

Ну, ладно, это была только нижняя граница для биноминального коэффициента. Верхняя же доказывается просто выводится из одной из оценок Стирлинга для факториала (там вроде довольно много всяких формул, но я помню только вот эти две: n! ~ √(2πn)·(n/e)n и √(2π)·nn+1/2·e−n ≤ n! ≤ e·nn+1/2·e−n). В общем, всё сводится вот к этому:

> (n/k)k ≤ (nk) ≤ (e·n/k)k


И, наверное, это круто.

На этом сама глава закончилась, но за ней следовала целая куча упражнений, которые не столько были на закрепление материала (которого по сути особо и не было), но на доказательство всяких новых штук.

CLRS — Appendix C: Counting (Exercises)

C.1-1

>How many k-substrings does an n-string have? (Consider identical k-substrings at different positions to be different.) How many substrings does an n-string have in total?



Ну, это совсем простая задачка, как и большинство из тех, которые есть к этой главе, но интересны они все тем, что у них, помимо простого решения в лоб, есть особое комбинаторное решение.

Вот, например, в этой задачке можно, конечно, просто просуммировать число строк длины 1, длины 2, и так далее до n и получить (n+1 | 2). Но гораздо проще представить, что между символами в строке можно поставить условные «маркеры» (перед первым симоволом, после первого, ..., перед последним и после последнего, то есть всего — n+1) и тогда любая подстрока задаётся выбором каких-то двух «маркеров», стоящих по разные стороны относительно подстроки. Ну, а число способов выбрать 2 элемента из n+1 — это и есть (n+1 | 2).

Собственно, примерно в такой же манере решаются и все остальные задачки на комбинаторику. И это уже было, кстати, в 6.042J.

Вот, например:

> k·(n | k) = n·(n-1 | k−1)


Эту формулу можно проинтерпретировать как «число способов собрать команду из k человек (выбирая из n претендентов) и выбрать в ней капитана». Слева — мы сначала собираем команду, а потом выбираем в ней капитана, а справа — сначала выбираем n способами капитана, а потом капитан добирает себе в команду оставшихся k−1 человека. То есть разными способами считаем одно и то же.

> (n | k) = (n−1 | k) + (n−1 | k−1)


Вот эта формула вроде довольно часто встречается и даже как-то по-умному называется. Тут выделяется какой-то конкретный особый предмет среди всех n предметов, из которых мы выбираем коллекцию из k штук, и тогда все возможные наборы из k предметов делятся на два дизъюнктных множества: множество наборов, в которых этот особый предмет присутствует, и наборы, в которых его нет.

Последний факт, кстати, используется при построении Треугольника Паскаля, про который я вроде когда-то слышал, но никогда не знал толком, что это. Как оказалось, это просто последовательность строк, записанных друг под другом, где в n-ой строке выписаны n биноминальных коэффициентов: начиная с (n | 0), и, заканчивая (n | n). Получается такой прямоугольный треугольник, у которого по границе стоят единицы, а остальные элементы вычисляются как сумма вышестоящего и слева-сверху-стоящего элементов. Полезно, если ты не знаешь коэффициенты для Бинома Ньютона для какой-то там большой степени: можно быстро просуммировать на бумажке и получить их выписанными в одном из рядов в треугольнике.

С.1-10

>Покажите, что (n | k) принимает максимальное значение в k = [n/2].


Доказательство на пикрелейтеде. Я его отдельно довольно подробно расписал, потому что один раз умудрился запутаться во всех этих индексах и доказать неправильно. Сейчас вроде как нормально.

С.1-11

> (n | j+k) ≤ (n | j)·(n−j | k)


Вроде очевидно, но заставляет задуматься. Может показаться, что верно и более строгое утверждение, с равенством, но на деле это не так: слева — число способов выбрать j+k элементов из n, а справа — число способов сначала выбрать j, а потом k элементов из того же набора. То есть во втором случае нам чуть-чуть важен порядок, так что в каком-нибудь простом примере на множестве {A, B} и j=1, k=1 будет выполняться строгое неравенство: с одной стороны, можем выбрать только одним способом сразу два элемента, с другой, последовательно элементы мы можем выбрать двумя способами: либо сначала A, а потом B, либо сначала B, а потом A.

C.1-13

>Use Stirling's approximation to prove that (2n | n) = чему-то там


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

Остаются только две приложенных картинки.

Первая из двух, но третья из четырёх, вот такая математика — доказательство какого-то очередного глупого неравенства. ОБРАТИТЕ ВНИМАНИЕ на два «короче» внизу и на то, что я, будучи человеком, который неспособен сложить два двузначных числа в уме, героически посчитал производную сложной функции, доведя её до состояния, где можно понять, что производная имеет какой-то там знак на каком-то там интервале. А само доказательство получилось каким-то заковыристым, плюс наверняка там полная ерунда с областями определения n и k, так что там в некоторых местах могут быть деления на ноль, которые надо бы отдельно рассматривать, но мне всё равно, вот. А доказательство для второй половины промежутка там следует просто из такой своего рода «симметричности» биноминального коэффициента.

На последней картинке на мой взгляд человека, не обременённого особыми познаниями во всяких математиках — просто какие-то формулы, которые как-то магически друг из друга выводятся. Какой смысл у всего этого, что такое binary entropy function, почему мы обозначали k = λn — не знаю.

Короче, чёт такое.
171 148276 0
tset
!!DoQIWs14lg 172 148465 1
test
!!Z9D/.oGaR6 173 148466 1
test
!!4TyQtDOOiQ 174 148467 0
test
!!WYE5ILyS8E 175 148468 0
test
!!WYE5ILyS8E 176 148469 1
test
177 148470 2
test
!!WYE5ILyS8E 178 148471 1
test
!89Tnv8KFCc 179 148472 1
test
!PSJlkXyvHI 180 148473 1
t
!!grGTT7Gpkw 181 148474 2
t
!bVJWeaDow2 182 148475 1
t
!!KdGCoecOmE 183 148476 1
t
!!5ZVw7oKRzc 184 148477 1
t
!!ejjmWc6Al6 185 148478 0
t
!!vQbtcHuM26 186 148479 1
t
!!KaxaKAUbUA 187 148480 1
t
!!NPT6xxkek2 188 148481 1
t
!!Z9D/.oGaR6 189 148482 0
t
!!BucVblKjO2 190 148483 1
t
!!kCy8bsoMIc 191 148484 0
t
!!LhYL.Nvi.Q 192 148486 1
t
!GgFrh1Flpw 193 148487 1
t
!QFOalchu6o 194 148488 1
t
!QFOalchu6o 195 148489 1
t
!QFOalchu6o 196 148490 1
t
!!phnGQI0RUg 197 148491 1
t
!!ocNTzFNiwk 198 148492 1
t
!!8u7Wdzur4M 199 148493 1
t
!!ydRxKolJL6 200 148494 0
t
!!ilNtvZ2oRU 201 148495 1
t
!TjPsHx6kTQ 202 148496 1
t
203 148497 1
test
!orgasm.3.A 204 148498 1
3
!IMe14crsrg 205 148500 1
1488
!CUSVM7XhTo 206 148502 1
7
!U8jWzZ98WY 207 148503 1
8
!Kq/nYHaQtY 208 148504 0
7
!t3FzLogAnE 209 148505 1
1
!cLogAndGUQ 210 148506 1
2
!GPaDMwE916 211 148507 1
3
212 148509 1
!loGanOjjtA 213 148510 0
4
214 148522 0
Test
215 148525 1
216 148537 1
Test
217 157272 0
gg
218 157294 0
219 157755 0
1
220 159891 0
2
221 159899 0
test
222 159912 0
223 159914 0
ttest
224 159976 0
ntcn test
225 159985 0
output.gif5,5 Мб, 480x853
226 164262 0
227 164272 0
test
228 164282 0
test
InkedWoWScrnShot042220132619LI.jpg2,7 Мб, 1920x1080
229 164283 0
230 164288 0
efw
231 164310 0
Tttttt
232 164313 0
233 164314 0
234 164459 0
t
235 164474 0
testss
236 164480 0
1
237 164485 0
238 164487 0
test
239 164489 0
test
241 214485 0
KATANA
Обновить тред
« /test/В начало тредаВеб-версияНастройки
/a//b//mu//s//vg/Все доски

Скачать тред только с превьюс превью и прикрепленными файлами

Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах.Подробнее