All public logs
Jump to navigation
Jump to search
Combined display of all available logs of TCS Wiki. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).
- 14:58, 17 April 2023 Etone talk contribs created page 概率论与数理统计 (Spring 2023)/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...")
- 11:36, 13 April 2023 Etone talk contribs created page 组合数学 (Fall 2023)/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...")
- 13:06, 12 April 2023 Etone talk contribs created page 概率论与数理统计 (Spring 2023)/Average-case analysis of QuickSort (Created page with "[http://en.wikipedia.org/wiki/Quicksort '''快速排序'''('''Quicksort''')]是由Tony Hoare发现的基于比较的(comparison-based)排序算法。该算法的伪代码描述如下(为方便起见,假设数组元素互不相同——更一般情况的分析易推广得到): '''''QSort'''''(A): 输入A[1...n]是存有n个不同数字的数组 if n>1 then '''pivot''' = A[1]; 将A中<pivot的元素存于数组L,将>pivot的元素存于...")
- 14:25, 29 March 2023 Etone talk contribs created page 组合数学 (Fall 2023)/Pólya's theory of counting (Created page with "== Groups == A group <math>(G,\cdot)</math> is set <math>G</math> along with a binary operator <math>\cdot</math> which satisfies the following axioms: * ''closure'': <math>\forall g,h\in G, g\cdot h \in G</math>; * ''associativity'': <math>\forall f,g,h\in G, f\cdot(g\cdot h)=(f\cdot g)\cdot h</math>; * ''identity'': there exists a special element <math>e\in G</math>, called the '''identity''', such that <math>e\cdot g=g</math> for any <math>g\in G</math>; * ''inverse''...")
- 12:45, 16 March 2023 Etone talk contribs created page 组合数学 (Fall 2023)/Sieve methods (Created page with "== Principle of Inclusion-Exclusion == Let <math>A</math> and <math>B</math> be two finite sets. The cardinality of their union is :<math>|A\cup B|=|A|+|B|-{\color{Blue}|A\cap B|}</math>. For three sets <math>A</math>, <math>B</math>, and <math>C</math>, the cardinality of the union of these three sets is computed as :<math>|A\cup B\cup C|=|A|+|B|+|C|-{\color{Blue}|A\cap B|}-{\color{Blue}|A\cap C|}-{\color{Blue}|B\cap C|}+{\color{Red}|A\cap B\cap C|}</math>. This is illu...")
- 17:35, 11 March 2023 Etone talk contribs created page 概率论与数理统计 (Spring 2023)/Karger's min-cut algorithm (Created page with "= Graph Cut = Let <math>G(V, E)</math> be an undirected graph. A subset <math>C\subseteq E</math> of edges is a '''cut''' of graph <math>G</math> if <math>G</math> becomes ''disconnected'' after deleting all edges in <math>C</math>. Let <math>\{S,T\}</math> be a '''bipartition''' of <math>V</math> into nonempty subsets <math>S,T\subseteq V</math>, where <math>S\cap T=\emptyset</math> and <math>S\cup T=V</math>. A cut <math>C</math> is specified by this bipartition as...")
- 16:43, 11 March 2023 Etone talk contribs created page 概率论与数理统计 (Spring 2023)/Polynomial identity testing (Created page with "=Polynomial Identity Testing (PIT) = The '''Polynomial Identity Testing (PIT)''' is such a problem: given as input two polynomials, determine whether they are identical. It plays a fundamental role in ''Identity Testing'' problems. First, let's consider the univariate ("one variable") case: * '''Input:''' two polynomials <math>f, g\in\mathbb{F}[x]</math> of degree <math>d</math>. * Determine whether <math>f\equiv g</math> (<math>f</math> and <math>g</math> are identica...")
- 08:31, 3 March 2023 Etone talk contribs created page 组合数学 (Fall 2023)/Generating functions (Created page with "== Generating Functions == In Stanley's magnificent book ''Enumerative Combinatorics'', he comments the generating function as "the most useful but most difficult to understand method (for counting)". The solution to a counting problem is usually represented as some <math>a_n</math> depending a parameter <math>n</math>. Sometimes this <math>a_n</math> is called a ''counting function'' as it is a function of the parameter <math>n</math>. <math>a_n</math> can also be tre...")
- 13:22, 16 February 2023 Etone talk contribs created page 组合数学 (Fall 2023)/Basic enumeration (Created page with "== Basic Enumeration == The three basic rules for enumeration are: *'''The sum rule''': for any '''''disjoint''''' finite sets <math>S</math> and <math>T</math>, the cardinality of the union <math>|S\cup T|=|S|+|T|</math>. *'''The product rule''': for any finite sets <math>S</math> and <math>T</math>, the cardinality of the Cartesian product <math>|S\times T|=|S|\cdot|T|</math>. *'''The bijection rule''': if there exists a bijection between finite sets <math>S</math> a...")
- 10:26, 16 February 2023 Etone talk contribs created page File:Stanley-2e.jpg
- 10:26, 16 February 2023 Etone talk contribs uploaded File:Stanley-2e.jpg
- 07:28, 13 February 2023 Etone talk contribs created page File:Probability and Computing 2ed.jpg
- 07:28, 13 February 2023 Etone talk contribs uploaded File:Probability and Computing 2ed.jpg
- 07:18, 13 February 2023 Etone talk contribs uploaded a new version of File:Grimmett probability.jpg
- 07:16, 13 February 2023 Etone talk contribs created page File:Grimmett probability.jpg
- 07:16, 13 February 2023 Etone talk contribs uploaded File:Grimmett probability.jpg
- 07:14, 13 February 2023 Etone talk contribs created page File:概率导论.jpeg
- 07:14, 13 February 2023 Etone talk contribs uploaded File:概率导论.jpeg
- 07:04, 13 February 2023 Etone talk contribs created page 概率论与数理统计 (Spring 2023) (Created page with "{{Infobox |name = Infobox |bodystyle = |title = <font size=3>概率论与数理统计<br> Probability Theory and <br> Mathematical Statistics</font> |titlestyle = |image = |imagestyle = |caption = |captionstyle = |headerstyle = background:#ccf; |labelstyle = background:#ddf; |datastyle = |header1 =Instructors |label1 = |data1 = |header2 = |label2 = |data2 = 尹一通 |header3 = |label3 = Email |data3 = yinyt@...")
- 05:23, 13 February 2023 Etone talk contribs created page File:TheBook-6ed.jpeg