算法和计算复杂度 4 Reductions and Completeness
Reductions NP-completeness: by polynomial-time many-one reductions (aka Karp reductions) Studying completeness of P and NL: by log-space many-one reduction. Also too powerful for completeness inside L. 📖Definition 14 (Log-space reductions). Let L1⊆Σ1∗L_1\subseteq\Sigma_1^*L1⊆Σ1∗ and L2⊆Σ2∗L_2\subseteq\Sigma_2^*L2⊆Σ2∗ be languages. A log-space many-one reduction from L1L_1L1 to L2L_2L2 is a function f:Σ1∗→Σ2∗f:\Sigma_1^*\rarr\Sigma_2^*f:Σ1∗→Σ2∗ s.t. There exists a log-space Turing mach ...
德语学习 B2 Kapitel 6 Fit für ...
Inhalt Fit für den Onlineeinkauf Fit am Telefon Fit für die Kollegen Fit für die Prüfung 6-1 Fit für … (1) fit für Akkusativ 适合某事，胜任某事 Kurios 奇特的，奇怪的 6-2 Fit für … (2) der Quark 凝乳 das Eisen-/ 铁 Edelmetal 贵金属 die Analogie-n 类比，类推 die Denksportaufgabe-n 脑筋急转弯 6-3 Fit für den Onlineeinkauf (1) Was kaufen Sie in Geschäften? Was kaufen Sie im Internet? In Geschäften: Lebensmittel, Arzneimittel, Brillen Im Internet: Elektronische Geräte, Kleidung, Onlinekurs, Spielwaren, Tickets, Reise der Ko ...
算法和计算复杂度 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 ...
