User contributions for Etone
Jump to navigation
Jump to search
24 April 2024
- 03:0203:02, 24 April 2024 diff hist +1,091 组合数学 (Spring 2024) →Concepts current
- 02:5702:57, 24 April 2024 diff hist +27,151 N 组合数学 (Fall 2024)/The probabilistic method Created page with "== The Probabilistic Method == The probabilistic method provides another way of proving the existence of objects: instead of explicitly constructing an object, we define a probability space of objects in which the probability is positive that a randomly selected object has the required property. The basic principle of the probabilistic method is very simple, and can be stated in intuitive ways: *If an object chosen randomly from a universe satisfies a property with posi..." current
- 02:5702:57, 24 April 2024 diff hist +157 组合数学 (Spring 2024) →Lecture Notes
22 April 2024
- 03:1403:14, 22 April 2024 diff hist +5,139 N 概率论与数理统计 (Spring 2024)/Weierstrass Approximation Theorem Created page with "[https://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theorem '''魏尔施特拉斯逼近定理''']('''Weierstrass approximation theorem''')陈述了这样一个事实:闭区间上的连续函数总可以用多项式一致逼近。 {{Theorem|魏尔施特拉斯逼近定理| :设 <math>f:[a,b]\to\mathbb{R}</math> 为定义在实数区间 <math>[a,b]</math> 上的连续实值函数。对每个 <math>\epsilon>0</math>,存在一个多项式 <math>p</math> 使得对..." current
- 03:1303:13, 22 April 2024 diff hist +7,005 N 概率论与数理统计 (Spring 2024)/Threshold of k-clique in random graph Created page with "在 Erdős-Rényi 随机图模型 <math>G(n,p)</math> 中,一个随机无向图 <math>G</math> 以如下的方式生成:图 <math>G</math> 包含 <math>n</math> 个顶点,每一对顶点之间都独立同地以概率 <math>p</math> 连一条无向边。如此生成的随机图记为 <math>G\sim G(n,p)</math>。 固定整数 <math>k\ge 3</math>,考虑随机图 <math>G\sim G(n,p)</math> 包含 <math>K_k</math>(<math>k</math>-团,<math>k</math>-clique)子图..." current
- 03:1203:12, 22 April 2024 diff hist +8,968 N 概率论与数理统计 (Spring 2024)/Two-point sampling Created page with "= 利用线性同余方程构造两两独立的随机变量 = 令<math>p</math>为一质数。考虑模<math>p</math>余数构成的集合<math>[p]=\{0,1,\ldots,p-1\}=\mathbb{Z}_p</math>。众所周知,当<math>p</math>为质数时,<math>\mathbb{Z}_p</math>为对模<math>p</math>加法和乘法运算闭合的'''有限域'''。 我们现在构造一系列值域为<math>[p]</math>的'''两两独立'''('''pairwise Independent''')且'''均匀分布'''('''uniforml..." current
- 03:1203:12, 22 April 2024 diff hist +325 概率论与数理统计 (Spring 2024) →Lectures
15 April 2024
- 14:5814:58, 15 April 2024 diff hist +750 概率论与数理统计 (Spring 2024) →Concepts
- 14:5714:57, 15 April 2024 diff hist +155 概率论与数理统计 (Spring 2024) →Lectures
- 14:5514:55, 15 April 2024 diff hist 0 概率论与数理统计 (Spring 2024) →Lectures
- 14:5414:54, 15 April 2024 diff hist +189 概率论与数理统计 (Spring 2024) →Lectures
12 April 2024
- 09:0209:02, 12 April 2024 diff hist −1 组合数学 (Spring 2024) →Lecture Notes
- 09:0109:01, 12 April 2024 diff hist +186 组合数学 (Spring 2024) →Lecture Notes
9 April 2024
- 13:2713:27, 9 April 2024 diff hist +14,440 N 组合数学 (Fall 2024)/Existence problems Created page with "== Existence by Counting == === Shannon's circuit lower bound=== This is a fundamental problem in in Computer Science. A '''boolean function''' is a function in the form <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>. [http://en.wikipedia.org/wiki/Boolean_circuit Boolean circuit] is a mathematical model of computation. Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , x_n</math>. A circuit h..." current
- 13:2613:26, 9 April 2024 diff hist +17,231 N 组合数学 (Fall 2024)/Cayley's formula Created page with "== Cayley's Formula == We now present a theorem of the number of labeled trees on a fixed number of vertices. It is due to [http://en.wikipedia.org/wiki/Arthur_Cayley Cayley] in 1889. The theorem is often referred by the name [http://en.wikipedia.org/wiki/Cayley's_formula Cayley's formula]. {{Theorem|Cayley's formula for trees| : There are <math>n^{n-2}</math> different trees on <math>n</math> distinct vertices. }} The theorem has several proofs, including the bijectio..." current
- 13:2613:26, 9 April 2024 diff hist +87 组合数学 (Spring 2024) →Lecture Notes
- 13:2413:24, 9 April 2024 diff hist +80 组合数学 (Spring 2024) →Lecture Notes
8 April 2024
- 08:4208:42, 8 April 2024 diff hist +985 概率论与数理统计 (Spring 2024) →Concepts
- 08:4108:41, 8 April 2024 diff hist +11,838 N 概率论与数理统计 (Spring 2024)/Average-case analysis of QuickSort Created page with "[http://en.wikipedia.org/wiki/Quicksort '''快速排序'''('''Quicksort''')]是由Tony Hoare发现的排序算法。该算法的伪代码描述如下(为方便起见,假设数组元素互不相同——更一般情况的分析易推广得到): '''''QSort'''''(A): 输入A[1...n]是存有n个不同数字的数组 if n>1 then '''pivot''' = A[1]; 将A中<pivot的元素存于数组L,将A中>pivot的元素存于数组R; \\保持内部元素之..." current
- 08:4008:40, 8 April 2024 diff hist +126 概率论与数理统计 (Spring 2024) →Lectures