算法和计算复杂度 8 Branching Programs and Barrington’s Theorem
NC1⊆L/poly⊆NL/poly⊆AC1NC^1\subseteq L/poly\subseteq NL/poly\subseteq AC^1NC1⊆L/poly⊆NL/poly⊆AC1. The model of branching programs that give a precise characterization of L/polyL/polyL/poly and NL/polyNL/polyNL/poly. Deterministic / non-deterministic branching program Boolean Branching Program Deterministic 📖Definition 32. A Deterministic Boolean branching program BBB with nnn inputs consists of the following: A directed acyclic graph D=(V,A)D=(V,A)D=(V,A), where the out-degree of all nodes is ...
丹麦语 DU 3.3 3 Sammenligning af forskellige kulturer
Sammenligninger sammenligning -en, -er, -erne 比较 Sammenligninger i 1. grad 原级比较 ikke så … som Eks: Tom er ikke så høj som Mads. 汤姆没有梅兹高。Tom ist nicht so groß wie Mads. lige så … som Eks: Poul er lige så høj som Mads. 汤姆和梅兹一样高。Poul ist so groß wie Mads. lige … (-e) Eks: Poul og Mads er lige høje. 汤姆和梅兹一样高。Poul und Mads sind gleich groß. Sammenligninger i 2. grad 比较级比较 -(e)re end Eks: Poul er højere end Tom. mere … end Eks: Tom er mere sporty end Poul. mindre … end Eks: Poul er mi ...
Fair AI/ML 0 Overview
This semester, I will do a project again with Iannis. I took some time to review the tutorial Fairness in AI/ML via Social Choice by Evi Micha & Nisarg Shah. Social Choice Theory: Aggregating individual preferences into “good” collective decisions Fairness in Social Choice 很熟悉了，可以快速掠过。 ⚠️这里考虑的是 DIVISIBLE ITEMS. EF, PROP Fair division: Agents NNN, divisible resources MMM, utility function uiu_iui. Non-negative utilities (good), non-positive utilities (chores). Proportionality, envy-freenes ...
丹麦语 DU 3.3 2 Normer og uskrevne regler
Høflighed og nedtoning 降低语气，表礼貌委婉 Generalisering: Danskerne er svære at komme i kontakt med. kan: Danskerne kan være svære at komme i kontakt med. 情态动词 kan 在此处表示一种可能性，不绝对。 mange/nogle/en del/de fleste: Nogle danskerne er svære at komme i kontakt med. 定量表达：并不是所有（人）怎么怎么样。 ofte/tit/normalt/nogle gange: Danskerne er nogle gange svære at komme i kontakt med. 频率副词：并不是 100% 会发生。 vist/nok: Danskerne er vist svære at komme i kontakt med. 表示不确定的副词：可能、大概 lidt/ret: Danskerne er lidt svære at komme i konta ...
丹麦语 DU 3.3 1 Ligheder og forskelle
lighed -en -er -erne 相同点 forskel -len -le -lene 不同点 tillid -en 信任 at lægge mærke til 注意到 Har du lagt mærke til, at det er begyndt at regne? Jeg har lagt mærke til, at du har fået en ny frisure. at undre sig over 想知道某事，惊讶于某事 Jeg undrer mig over, hvorfor toget er forsinket. Hun undrede sig over, hvordan det kunne ske. at vænne sig til 习惯于 Det tager tid at vænne sig til et nyt job. Jeg har vænnet mig til at stå tidligt op. 我习惯于早起。 Kulturmødet - ligheder og forskelle anderledes - - 不同的 adj ri ...
德语 阴阳中性词汇的辨别方法
通用方法 前缀 Ge- 凡是以 Ge- 开头的，并且表示“一类事物总称”的名词，100% 是中性的。 das Gebäude 建筑物 das Gericht 菜肴、法院 das Getränk 饮料 das Gemüse 蔬菜 das Gebäck 烘烤饼干 das Gepäck 行李 das Gespräch 谈话、对话 后缀 -um 凡是以 -um 结尾的名词，100% 都是中性的 das Studium 大学课程 das Stipendium 奖学金 das Museum 博物馆 das Kriterium 标准 das Zentrum 中心 das Datum 日期、数据 das Wachstum 增长 das Visum 签证 后缀 -schaft 凡是以 -schaft 结尾的名词，100% 阴性，毫无悬念，类似于英语中的后缀 -ship，表示“一种抽象的关系”。 die Wissenschaft 科学 die Wirtschaft 经济 die Nachbarschaft 邻里关系 die Freundschaft 友谊 die Bereitschaft ...
算法和计算复杂度 7 Bounded Depth Boolean Circuits
What if Boolean circuits has bounded depth? Depth of Boolean circuit: the length of a longest path from an input gate to an output gate. It’s a model of parallel computation where depth corresponds to parallel time. Parallel model of random access machine PRAM 痛苦的计算几何课的回忆 📖Definition of SIZE−DEPTHSIZE-DEPTHSIZE−DEPTH. Let S:N→NS:\mathbb N\to\mathbb NS:N→N and d:N→Nd:\mathbb N\to\mathbb Nd:N→N. SIZE−DEPTH(S(n),d(n))SIZE-DEPTH(S(n),d(n))SIZE−DEPTH(S(n),d(n)) is the class of languages computed by ...
Codeforces Round 963 (Div. 2) 部分题目总结
本次比赛 链接。说实话出的比较糟糕，题目难度的梯度非常不均匀。 A, B, C 题没什么好说的，跳过。 D. Med-imize 题目大意 给定一个包含 n 个 int 的数组 a，给定 k。在 a 中，每次选择长度刚好为 k 的任意的连续子数组进行删除，删除至 a 长度小于等于 k 为止。求删除操作结束后数组 a 最大可能的中位数值。 解题思路 二分搜索答案 + 动态规划。 当输入数组长度小于等于 k 时，答案就是当前数组的中位数。 ❓如何在不排序的情况下求出一个数组的中位数呢？二分查找。 对每一个给定的值 x，建立另一个和 a 一样大的标签数组 b。 当 x<=a[i] 时，标记 b[i]=1；反之 b[i]=-1。 这样通过判断 b 数组和的正负性，我们就能判断 x 是否比中位数小了。 当 n>k 时，同理进行二分搜索答案。为了检查当前值是否小于最优可能解，我们只需使用动态规划求出 b 数组最大的和，检查其正负性。 ❓如何用动归求 b 数组最大的和呢？ 注意到每次删除完成后数组的长度为 m=((n-1)%k)+1。 注意到删除完成后的数组 a' 中的每 ...
算法和计算复杂度 6 Randomized Computation
What if Turing machine models have access to a source of randomness? This would allow to compute more in same time/space, at the price of possibly not giving correct answer with small probability. Current consensus: Randomization only gives Polynomial saving in time Constant factor saving in space Because of hardness-based pseudo-random generator. Exponential time: E=DTIME(2O(n))=UL−SIZE(2O(n))E=DTIME(2^{O(n)})=U_L-SIZE(2^{O(n)})E=DTIME(2O(n))=UL−SIZE(2O(n)). (By corollary 2) Recall that SIZE ...
新坑预告——《安徒生童话》丹麦语原文精读
在童年的梦境中，我们曾徜徉于安徒生笔下的神奇世界。他的故事不仅构建了我们幼年的幻想，也深深触动了我们的内心。如今，当我重拾这些经典童话，并用丹麦语的原汁原味去品读，那份久违的感动再次涌上心头。透过丹麦语的细腻表达，我希望与你们分享那些在翻译中可能被忽略的细节与韵味，揭开每一个故事背后的语言魅力与文化底蕴。 开启新坑的目的 这个全新项目不仅是我对丹麦语学习热情的延续，也是对童年回忆的深情追溯。通过精读安徒生的经典童话，我希望在积累更多丹麦语单词和地道表达的同时，重温那些陪伴我们成长的故事。这不仅是语言学习的旅程，更是一次文化与情感的深度体验。 童年记忆中的经典 从《丑小鸭》的蜕变，到《卖火柴的小女孩》的动人心魄，这些故事早已成为我们共同的记忆。以下是我小学初中时在语文课堂上涉及到的童话故事： 人教版小学语文 二年级下册——《丑小鸭》Den grimme ælling 六年级下册——《卖火柴的小女孩》Den lille Pige med Svovlstikkerne 人教版初中语文 七年级上册——《皇帝的新装》Kejserens nye klæder 精读形式与内容 ...