算法和计算复杂度 16 Fast Fourier Transform
Algebraic Structure GF(pm)GF(p^m)GF(pm): Galois field of order pmp^mpm, ppp is prime. 伽罗瓦域是一个包含加法和乘法的代数结构，满足加法和乘法的交换律、结合律、分配律，每个元素都有逆元。 Zn\Z_nZn: Integers modulo n≥1n\ge1n≥1. Mm,n(R)M_{m,n}(R)Mm,n(R): mmm by nnn matrices over a ring RRR. 这个玩意是一个矩阵，只是其中每一个元素都来自环。乘法通常不满足交换律。 Mn(R)M_n(R)Mn(R): Mn,n(R)M_{n,n}(R)Mn,n(R). The Discrete Fourier Transform 数 字 信 号 处 理 The key to fast multiplication of integers and polynomials is the discrete Fourier transform. Roots of Unity e2πni=cos2πn+isin2π ...
丹麦语 DU 3.3 12 Jobansøgning og arbejdsmarked
Tekstsammenhæng i jobansøgninger På dansk har vi mulighed for at variere sætningsspidserne. Dvs. at mange andre led en subjektet kan stå først i sætningen. For eks. Jeg vil gerne bruge min fritid på at hjælpe andre. Jeg kan samtidig selv få mulighed for at træne mit dansk. Min fritid vil jeg gerne bruge på at hjælpe andre. Samtidig kan jeg selv få mulighed for at træne mit dansk. Tekst 2. har bedre sammenhængen. 不要老是写主谓宾的句子，这样太无聊了。需要变换一下语序，为了强调把其他成分放到第一位，然后动词第二位。 Den danske model forforstå ...
算法和计算复杂度 15 Fine-grained and Parameterized Complexity
Fine-grained Complexity Vassilevska Williams, “On some fine-grained questions in algorithms and complexity” (original paper), pages 1-9. Mimic NPNPNP-completeness, 3 Hypothesis SETH Recap Strong Exponential Time Hypothesis (SETH). For every ϵ>0\epsilon\gt0ϵ>0 there exists an integer k≥3k\ge3k≥3 s.t. CNF−SATCNF-SATCNF−SAT on formulas with clause size at most kkk and nnn variables can not be solved in O(2(1−ϵ)n)O(2^{(1-\epsilon)n})O(2(1−ϵ)n) time even by a randomized algorithm. 3-SUM 3-S ...
丹麦语 DU 3.3 11 Jobansøgning
Tekst-struktur i jobansøgning 写求职信，是 DU 3.3 的一大考点。 Jobansøgning Hovedoverskrift, der fortæller. Hvilken stilling, du søger. 标题写清楚要找什么职位 F.eks. Ansøgning om stilling som kok på restaurant ‘Blixen’ Att.: (attention) + titel, for- og efternavn på den, du skriver til. 这里要写完整收件人的头衔和全名 Skriv, hvad der motiverer dig, og hvad du kan tilbyde firmaet. 求职动机、你可以为单位提供什么 Vælg en overskrift med kompetencer, der matcher firmaets behov. Beskriv kort de kompetencer/erfaringer, du har fra tidligere job, projek ...
算法和计算复杂度 14 SAT Problem
Boolean satisfiability is prototypical NPNPNP-complete problem. There is no algorithm deciding SATSATSAT in worst case in polynomial time unless P=NPP=NPP=NP. We always assume that P≠NPP\neq NPP=NP. For SATSATSAT problem, SOTA algorithm uses time 2(1−1O(log(m/n)))nmO(1)2^{(1-\frac{1}{O(\log(m/n))})n}m^{O(1)}2(1−O(log(m/n))1)nmO(1). For special case of kSATkSATkSAT, there are faster algorithms, but all take time 2(1−ck)n2^{(1-\frac{c}{k})n}2(1−kc)n for some constant 0<c<k0\lt c\lt k0< ...
Fair AI/ML 6 Some Open Problems about Non-centroid Clustering
In this post, we focus on upper and lower bound of core where non-clusterings are. Let the loss (or cost) function for every data points be maximum distance between any other points and itself: ℓi(S)=maxj∈Sd(i,j).\ell_i(S)=\max_{j\in S}d(i,j). ℓi(S)=j∈Smaxd(i,j). We have known that a clustering in the exact core must exist given N,kN,kN,k. For the approximation of core: The Greedy Capture algorithm computes the upper bound of 222 in polynomial time. And it have the lower bound of 111. What ab ...
Efficient ReliK 4 Sampling Optimization
What is heur? By default, heur is set to binomial. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146def binomial(u: str, v: str, M: nx.MultiDiGraph, models: list[object], entity_to_id_map: object, relation_to_id_map: o ...
丹麦语 DU 3.3 10 Job og kompetencer
Jobannoncer ansvarsbevidst -, -e 负责任的，有责任感的 gå-på-mod -et 主观能动性 kundskab -en, -er, -erne 认知，知识 så hurtigt som muligt 越快越好 weekendvagt 值周末班 ansigt -et, -er, -erne 脸，面部 udadtil 外部的 præsentabel -t, præsentable 像样的，体面的 serviceminded -, -e 服务态度好的 selvstændig = selbständig 自主的，独立的 afvekslende = abwechselnd 交替的 gyldig -t, -e = gültig 有效的 opholds- og arbejdstilladelse -n, -r, -rne 居留和工作许可 afløser -en, -e, -ne 继承人，替代者 vikariat -et, -er, -erne 临时工 tiltrædelse -n, -r, -rne 担任，加入 forlængelse -n, -r, -rne 延 ...
算法和计算复杂度 13 Random Access Machine
More precise model Problem of integer multiplication. Registers can contain arbitrary integers. Consider repeated squaring to number 222. After just nnn multiplications, the resulting number is 22n2^{2^n}22n, a doubly exponential large number in nnn. This requires exponential number of bits. A RAM has an infinite sequence of registers each able to contain an arbitrary non-negative integer. Machine is controlled by a program consisting of a list of instructions. Registers can be added or subtrac ...
算法和计算复杂度 12 PCP-based Inapproximability
For MAXCLIQUEMAXCLIQUEMAXCLIQUE problem. A constant factor polynomial-time approximation algorithm doesn’t exist unless NP∈DTIME(2(logn)O(1))NP\in DTIME(2^{(\log n)^{O(1)}})NP∈DTIME(2(logn)O(1)), based on the theorem that NP⊆PCP((logn)O(1),(logn)O(1))NP\subseteq PCP((\log n)^{O(1)},(\log n)^{O(1)})NP⊆PCP((logn)O(1),(logn)O(1)). Use a different approach the final PCPPCPPCP theorem implies that a constant factor polynomial-time approximation algorithm for MAXE3SATMAXE3SATMAXE3SAT doesn’t exist ...
