6.042J / 18.062J Mathematics for Computer Science (SMA 5512), Fall 2002
активна?Активные записи участвуют в каталоге и синках. Неактивная книга скрыта, но не удалена из базы.Загрузка разделов…
Описание?Библиографическая аннотация из domain.books.description. Может содержать HTML из импорта — его можно очистить через LLM ниже.
Course Notes 15 - Milestones of Probability Theory.pdf......Page 0 What is a Proof?......Page 1 Propositions......Page 2 Axioms......Page 3 Logical Deductions......Page 4 Good Proofs and Bad Proofs......Page 5 The Induction Axiom......Page 7 Proof Format......Page 9 A Fibonacci Identity......Page 10 Geometry......Page 11 The Fate of Computer Science at MIT......Page 12 A False Proof......Page 14 The Strong Induction Axiom......Page 15 Postage Stamp Example......Page 16 Induction with nonzero base cases......Page 17 Winning the Game of Nim......Page 18 Induction, Strong Induction, and Least Number Principle......Page 19 Least Number Principle......Page 20 Properties of Relations......Page 23 Boolean Matrices......Page 24 Digraphs......Page 25 Composition......Page 26 Computing Composition and Path Lengths......Page 27 The Symmetric Closure......Page 29 The transitive closure......Page 30 Equivalence Relations and Partitions......Page 31 Partial Orders......Page 33 Directed Acyclic Graphs......Page 35 Topological Sorting......Page 36 Parallel Task Scheduling......Page 37 Increasing and Decreasing Sequences......Page 39 Not Simple Graphs......Page 41 Graphs in the Real World......Page 43 Graph Isomorphism......Page 44 Vertex Degree......Page 45 Chromatic Number......Page 46 Paths in Graphs......Page 47 Adjacency Matrices......Page 48 Connectedness......Page 49 Trees......Page 52 Euler Tours......Page 55 Hamiltonian Circuits......Page 56 Die Hard......Page 58 Basic definitions......Page 59 Examples......Page 60 Executions of state machines......Page 61 Reachability and Invariants......Page 62 The Robot......Page 63 Sequential algorithm examples......Page 64 The Euclidean Algorithm......Page 65 Termination of GCD......Page 66 Fast Exponentiation......Page 67 Extended GCD......Page 68 Derived Variables......Page 69 The Stable Marriage Problem......Page 70 The Problem......Page 71 The State Machine Model......Page 73 They All Live Happily Every After…......Page 75 …And the Boys Live Especially Happily......Page 76 Another Robot......Page 77 Well-founded Partial Orders......Page 79 Terminating Games of Perfect Information......Page 81 Recursive Definitions......Page 85 Structural Induction on Recursive Data Type Definitions......Page 89 Induction on Trees......Page 90 Some Recursively Defined Functions......Page 92 Recursive Function Definitions......Page 93 Proving Properties of Recursive Functions......Page 94 Recursive Functions on Natural Numbers......Page 95 Ill-formed Definitions......Page 96 Induction in Computer Science......Page 97 Annuities......Page 98 The Value of an Annuity......Page 99 The Sum of a Geometric Series......Page 100 Infinite Geometric Series......Page 101 Examples......Page 102 Related Sums......Page 103 Formalizing the Problem......Page 104 Evaluating the Sum---The Integral Method......Page 107 More about Harmonic Numbers......Page 108 Finding Summation Formulas......Page 109 Double Sums......Page 110 Stirling's Approximation......Page 111 Little Oh......Page 113 Big Oh......Page 115 Theta......Page 116 The Exponential Fiasco......Page 117 Equality Blunder......Page 118 Matchings as Bijections......Page 119 Counting Functions......Page 120 The Pigeonhole Principle......Page 121 20 Questions and Binary Search......Page 122 Example: Weighing Coins......Page 123 The Sum Rule......Page 125 Inclusion-Exclusion Principle (special cases)......Page 126 Inclusion-Exclusion Principle (general case)......Page 128 Counting Primes......Page 129 Products of Sets......Page 131 Tree Diagrams......Page 133 A Problem Getting Dressed......Page 134 Playoff Outcomes......Page 135 Simple Permutations......Page 136 A Lower Bound for Sorting......Page 137 r-Permutations......Page 139 The Division Rule......Page 140 Combinations......Page 142 The number of r-Combinations (Binomial Coefficients)......Page 143 Some interesting special cases......Page 144 Hands with Four-of-a-Kind......Page 145 Hands with Two Pairs......Page 146 Four different ranks......Page 148 Reminders......Page 149 How the Trick Works......Page 150 Same Trick with 4 Cards?......Page 151 Hall's Theorem applied to the Magic Trick......Page 152 Hall's Marriage Theorem......Page 153 Proof of Hall's Theorem by Induction [Optional]......Page 154 Properties of Binomial Coefficients......Page 155 The Binomial Theorem......Page 159 Principle of Inclusion and Exclusion......Page 160 Counting r-Permutations with Repetition......Page 161 Permutations with Limited Repetition......Page 162 Multinomial Coefficients......Page 163 Counting r-Combinations with Repetition......Page 164 Triple-Scoop Ice Cream Cones......Page 165 Balls and Bins......Page 166 r-Combinations with at Least One of Each Item......Page 167 r-Combinations with Limited Repetition......Page 168 Data Compression [Optional]......Page 169 Modelling Experimental Events......Page 171 The Monty Hall Problem......Page 173 Assumptions......Page 175 Assigning Probabilities to Outcomes......Page 176 Intransitive Dice......Page 178 Basic Laws of Probability......Page 181 Carnival Dice......Page 183 More Intransitive Dice [Optional]......Page 184 Derangements [Optional]......Page 185 Conditional Probability......Page 186 Conditional Probability Examples......Page 187 A Two-out-of-Three Series......Page 188 An a posteriori Probability......Page 190 A Problem with Two Coins [Optional]......Page 191 A Variant of the Two Coins Problem [Optional]......Page 192 Medical Testing......Page 193 Confusion about Monty Hall......Page 195 Discrimination Lawsuit......Page 196 A false analysis......Page 197 The Law of Total Probability......Page 198 On-Time Airlines......Page 199 Probability that the First Player Wins......Page 200 The Sample Space......Page 201 The Definition......Page 202 The Independent Product Rule......Page 203 Disjoint Events vs. Independent Events......Page 204 An Experiment with Two Coins......Page 205 A Variation of the Two-Coin Experiment......Page 206 Example: Blood Evidence......Page 207 Definition of Mutual Independence......Page 208 A Red Sox Streak [Optional]......Page 209 An Experiment with Three Coins......Page 210 Pairwise Independence......Page 211 Solution......Page 212 Approximating the Answer to the Birthday Problem......Page 214 The Birthday Principle......Page 215 Random Variables......Page 216 Probability of Events Defined by a Random Variable......Page 217 Proving that Two Random Variables are Not Independent......Page 219 A Dice Example......Page 220 Mutual Independence......Page 221 Bernoulli Distribution......Page 222 Binomial Distribution......Page 223 A Winning Strategy......Page 224 The Space Station Mir......Page 226 Leader Election......Page 227 The Shape of the Binomial Distribution......Page 228 The tails......Page 229 25 Heads in 100 Tosses......Page 231 Transmission Across a Noisy Channel......Page 232 Two Equivalent Definitions......Page 233 Expected Value of One Die......Page 234 Modified Carnival Dice......Page 235 Expectation of Natural Number-valued Variables......Page 236 Mean Time to Failure......Page 237 An Expectation Paradox......Page 238 Expectation of a Sum......Page 240 The Hat-Check Problem......Page 241 The Chinese Appetizer Problem......Page 242 Expectation of a Binomial Distribution......Page 243 Conditional Expectation......Page 244 The Product of Independent Expectations......Page 245 A RISC Paradox......Page 246 A Probabilistic Interpretation......Page 247 A Simpler Example [Optional]......Page 249 Convergence Conditions for Infinite Linearity......Page 250 Solution to the Paradox......Page 251 Random Length Sums......Page 252 The Sample Space......Page 255 The Expected Number of Tries......Page 256 The Expected Number of Steps......Page 257 A Better Way to Build Systems......Page 258 What the Mean Means......Page 259 The Weak Law of Large Numbers......Page 260 Markov's Theorem......Page 261 Examples of Markov's Theorem......Page 262 Why R Must be Nonnegative......Page 263 Using Markov To Analyze Non-Random Events [Optional]......Page 264 Chebyshev's Theorem......Page 265 Example: Gambling Games......Page 266 Standard Deviation......Page 267 An Alternative Definition of Variance......Page 268 Expectation Squared [Optional]......Page 269 Dealing with Constants......Page 270 Variance of a Sum......Page 271 Variance of a Binomial Distribution......Page 272 I.Q. Example......Page 273 Estimation from Repeated Trials......Page 274 Birthdays again......Page 276 Size of a Poll......Page 277 Confidence Levels......Page 278 Better Polling......Page 279 Proof of the Weak Law......Page 280 Random Walks and Gamblers' Ruin......Page 281 The Unbiased Game......Page 283 A Recurrence for the Probability of Winning......Page 285 Intuition......Page 287 Duration of an Biased Walk......Page 289 Duration of an Unbiased Walk......Page 290 Quit While You Are Ahead......Page 291 Infinite Expectation......Page 292 The Probability of at Least One Event......Page 293 Probability of at least k events......Page 295 Example: Pick 4......Page 296 The constant in the exponent......Page 297 Proof of the Bound......Page 298 How to Build One Switch......Page 299 A Generalized Chernoff Bound......Page 300 Review of Markov, Chebyshev, Chernoff and Binomial bounds......Page 301 Poisson Random Variables......Page 303 Properties of the Poisson Distribution......Page 305 The Central Limit Theorem......Page 306 Strong Law of Large Numbers [Optional]......Page 308 A Failure of the Strong Law......Page 309
Год?Текстовое поле domain.books.year — год издания как в библиографии (например «2006»). Не путать с calendar_period_id: точная календарная дата задаётся отдельно, если нужна.
2002
Город издания?Место издания (domain.books.location_id → domain.locations, тип «город»). Из библиографической строки «М.» и т.п.
—
Серия?Название серии издания (domain.books.series, паритет LibGen Series). Не путать с parent_id — иерархия томов внутри многотомника.
—
Страниц?Количество страниц в этом издании. Для многотомников у каждого тома может быть своё значение.
—
Издатель?Издательская организация из справочника domain.corporate_names (publisher_id).
Категория?Основная тематическая рубрика библиотеки (primary_category_id → domain.categories).
—
Язык?Основной язык текста книги (primary_language_id → domain.languages).
английский язык
Страна?Страна публикации (publish_country_id → domain.locations), не место действия книги.
—
Уровень в иерархии?Глубина в дереве книг: 1 — верхний уровень (отдельное издание или корень серии), 2 и выше — том, часть или выпуск внутри родительской записи. Не путать с полем «Доверие».
1
Религиозная?Флаг religious_book: книга отмечена как религиозная литература в каталоге.
нет
На сайте?Флаг publish: карточка книги должна быть видна на публичном сайте Sudar.
да
Доверие?trust_level от −100 до 100: насколько системе можно доверять метаданным этой записи. «Авто» пересчитывает по году, издателю, месту издания, ISBN, ключевым словам, сторонним id и оглавлению.
10
Идентификатор сайта?Связь с core.identifiers: slug, URL-путь и файлы на сайте. Без него книга не привязана к публичной карточке.
—
Обновлено?Дата последнего изменения строки domain.books (updated_at), включая правки описания и метаданных.
15 нояб. 2026 г., 14:41
Разбор ещё не выполнен — запустите конвейер обработки книги.