算法和计算复杂度 3 Boolean Circuits
Non-uniform model of computation: Boolean circuit model. In contrast to uniform model like Turing machine. Boolean circuit: Fixed number of inputs. To study computation of arbitrary inputs, we need a family of Boolean circuits. Some Definitions 📖Definition of Boolean circuit. A Boolean circuit CCC with nnn inputs and mmm outputs consists of: A directed acyclic graph D=(V,A)D=(V,A)D=(V,A) where the in-degree of every node is at most 222. A labeling ℓ\ellℓ of all nodes g∈Vg\in Vg∈V with \ell(g) ...
算法和计算复杂度 2 Nondeterminism and Determinism
The sequence of transitions is called computation history. Non-deterministic Turing machine will crush also when there is no possible next step according to the transition relation. Non-deterministic Time and Space Complexity Worst-case definition of time and space to solve a issue by non-deterministic Turing machine. Let MMM be a non-deterministic Turing machine. For given input x∈Σ∗x\in\Sigma^*x∈Σ∗, timeM(x)time_M(x)timeM(x) is the maximum number of computation steps that MMM performs on in ...
算法和计算复杂度 1 Turing Machines, Time and Space
Theory of Algorithms and Computational Complexity Lecturer: Kristoffer Arnsfelt Hansen ☠️☠️☠️The most difficult (no “one of”) course in my master’s study.☠️☠️☠️ Brief Intro to TACC Study of efficient computation 1960s Hartmanis, Stearns - Time Hierarchy Theorem. Turing machine, register based machine can simulate each other. Turing Machines Turing machines - simple, and has some nice properties: Clean definition of complexity (time and space) Straightforward to non-determinism and randomness. ...
丹麦语 DU 3.2 13-14 Fortæl om ferier og oplevelser
Datid 3 种类型 Gruppe 1：词尾 -ede Gruppe 2：词尾 -te Gruppe 3：不规则变化，fx: tager - tog kan - kunne finder - fandt spørger - spurgte sidder - sad nyder - nød drikker - drak 情态动词 modalverber 的过去式 都是不规则变化 kan - kunne skal - skulle vil - ville må - måtte Esme på kunstmuseum udstilling -en -er -erne 展览 er spændt på at infinitiv 急切期待做某事 vente -r -de -t 等待 gå -r gik -et 走 gå ind 走进 omvisning -en -er -erne 参观 fortale -r fortalte fortalt 告诉，说出 flot 漂亮的，美好的 Solen skinnede, og himlen var helt blå. 阳光普照，天空很蓝。（有点 ...
随机算法 14 Markov Chains and Random Walks
Lecture notes by Elias Koutsoupias from Oxford Markov Chains Definitions A discrete-time finite Markov chain is a sequence of random variables X=X0,X1,X2,⋯X=X_0,X_1,X_2,\cdotsX=X0,X1,X2,⋯ taking values in a finite set of states {1,2,⋯ ,n}\{1,2,\cdots,n\}{1,2,⋯,n} s.t. ∀t∈N:\forall t\in\mathbb N:∀t∈N: Pr(Xt+1=j∣Xt=i)=Qi,j,\Pr(X_{t+1}=j|X_t=i)=Q_{i,j}, Pr(Xt+1=j∣Xt=i)=Qi,j, where Q=(Qi,j)Q=(Q_{i,j})Q=(Qi,j) is an n×nn\times nn×n stochastic transition matrix. XtX_tXt represents the state ...
随机算法 13 Nearest Neighbor Search with Different Distance Metrics
Recall Recall the problem of nearest neighbor search: Randomized ccc-approximate RRR-near neighbor search. Recall that given a set PPP of nnn points in Rd\mathbb R^dRd and parameters R>0,δ>0R\gt0,\delta\gt0R>0,δ>0. Also given a distance function dist:Rd×Rd→Rdist:\mathbb R^d\times\mathbb R^d\rarr\mathbb Rdist:Rd×Rd→R. For a query point qqq, if there is an RRR-near neighbor ppp of qqq (dist(p,q)≤Rdist(p,q)\le Rdist(p,q)≤R), we must report some point p′p'p′ that is a cRcRcR-near n ...
Fair Division 8 Strategic Aspects of Fair Divison
Objective: Investigate strategic aspects of fair division, considering Pure Nash equilibria and fairness. Activities: Review the paper Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness. Abstract What if the agents are strategic? Goal: whether there exist mechanisms that have pure Nash Equilibria. If so, what is the fairness guarantee for these equilibria? Focus on EF1, EFX. The answer is positive. 2 algorithms: round-robin (computing EF1 allocation). Its pure ...
西语学习 A1 Unidad 2 ¿Cómo estás?
Vocabulario gracias f.pl. 谢谢 amigo, a m.f. 朋友 director, ra m.f. 经理 teléfono m. 电话 bombero, a m.f. 消防员 副词 muy adv. 很 bien adv. 好 动词 estar intr. 在；处于 estar 的变位：estoy - estás - está - estamos - estáis - están 物主形容词（非重读，放在名词的前面） ⚠️物主形容词修饰复数名词时，词尾加 s 我的 mi 你的 tu TA的、您的 su 我们的 nuestro, nuestra 你们的 vuestro, vuestra TA们的 su 指示代词，“这个，这些” 单数 阳性 este 阴性 esta 复数 阳性 estos 阴性 estas 定冠词，表特指 单数 阳性 el 阴性 la 复数 阳性 los 阴性 las 练习 ¿Dónde está tu director? ¿Dónde está tu directora? ¿Dónde están tus directores? ¿Dón ...
丹麦语 DU 3.2 11-12 Planer for ferie og fridage
Efterårsferie sydpå 向南 副词 nordpå 向北 østpå 向东 vestpå 向西 lige nu 现在 herfra 从这里 bytur 城市游览 svamp -en -e -ene 蘑菇，真菌，海绵 teater -et, teatre, teatrene 剧院 gå i teatret 去剧院 eller sådan noget 相当于英语的 or something like that lad os bare gøre det 让我们这样做吧 复习表示建议、提议的表达 Hvad skal vi lave …? Hvad synes du, vi skal lave? Skal vi ikke + inf.? Vi kan f.eks. + inf. Vi kunne måske + inf. Jeg synes, vi skal/skulle + inf. Hvad siger du til at + inf.? Svar: Det kan vi godt. Jeg ved ikke rigtig. Det synes jeg ikke. N ...
数据挖掘 13 Sequence Segmentation and Similarities
How to segment a sequence of points with an efficient algorithms and how to find similar documents in a linear manner. 2 algorithm. The first is clustering a sequence to form kkk partitions with a dynamic programming. The second is an approximation that allows to compute pairwise distance avoiding O(n2)\mathcal O(n^2)O(n2). The idea is to use efficient signatures and hash the signatures in bands so as similar items will likely end up in the same bucket. Sequence Segmentation A sequence is a vec ...
