和我一样的数字控？Sugar Shikao~

又是一个四十代的叔叔。小小的眼睛，戴着眼镜，拍照时超严肃。薄薄的嘴唇，有次听Live音轨某段长达4秒像被掐住脖子般的笑声着实吓了我一大跳。声音有些沙，丝毫谈不上温润，有种我难以形容的粗颗粒磨砂质感。还带点恣意、随性，或者调侃的意味。心情好的时候听起来会觉得调皮，有趣。心情不好的时候听起来会觉得刺耳，闹心。

十足的才子，多产，不仅自销。却似乎从不曾红得通透的样子，总也见不到他的通告。词曲皆通。擅于玩弄各种音乐元素的混合搅拌，写些奇怪的歌词，用些异世界的词藻。作品的题目里经常出现数字，分数、日期、时间或者其他无意义乱敲等等等。

认识须贺是因为看了《Honey & Clover》发现某人居然和Spitz平摊了插曲曲目觉得挺厉害、后来看《xxxHOLiC》听OP的声音好耳熟曲子节奏好有趣一看居然又是某人，心想算了，既然有缘，给你个机会让我喜欢你吧。然后。。恩。

须贺写的曲子总是很丰富，能听到各种风格在一起打架。我不太爱好电子乐，却很喜欢须贺写的。有一种玩耍的心态。调子有时会很扭捏，乍一听有想马上关掉的冲动。也可以用诡异来形容。怎么说呢，不太流畅，总猜不到他下一小节会怎么写怎么编曲用什么样的方式唱。也可以说满是新意。普通速以下的曲子相对入耳些，只是杀伤力太大。他这样的嗓子，唱什么都觉得动情。

 

须贺发高音的方式很独特，有些像喝醉酒扯着嗓子唱歌的大叔。声音真得不得了，能感觉到声带绷紧后颤抖的频率，抖抖抖就像他笑起来的样子。须贺写的词有时会很晦涩，有时会很冷清，透着令人窒息的孤独感，和他的声音一起，打击得我无力还手。像是眼前有一条路，一步一步地走着，却总没有尽头。身边的人不断路过，有快有慢，我出声，却连自己也什么都没有听到。
坐公交的时候听他唱歌，窗外的人和车和房子和灯光变成一些大大的色块不断向后飞跃。车停。有人下车。如果下雨，我就会觉得没由来的伤感。
[7月7日]是这样的歌。[夏陰～なつかげ～]也是。还有[Happy Birthday]，是一首遇上什么伤心事时听都没得商量直接让人掉眼泪的歌。

 

 

最喜欢他的一张专辑是[Sugarless]，也是我曾经有过的所有Blog名字的来源。这似乎也是须贺卖得最好的一张专辑，也似乎是须贺最慢节奏的一张专辑。有几首虽谈不上快乐却可以闭上眼睛跟着左右摇摆的曲子。须贺絮絮叨叨，呢喃着一些不着边际的往事。那些无比意识流的歌词，在昏黄色灼热的午后不断穿行的思绪。偶然觉得安静，仿佛空气停止流动。偶尔又觉得胸闷而烦躁，电吉他蛮很的高音便开始肆虐。有些混沌。然后又说慢下来慢下来吧，我们正在长长的坡道上夕阳照着影子稀疏而温暖。

很想知道一些他对于生活的看法，因为须贺风光前似乎曾经很不幸，东大毕业却在小广告公司拿很低的薪水，经济窘迫。有这样经历的人，似乎不是分外努力便是就此沉沦。不过，对于我这样的局外人，只要能他还能继续写歌继续唱，就想抱着感谢的心情继续听下去。说到底，也只不过在哪个不知道的地方远远地观望他的路人而已。也许，大家都孤独。（我也学他意识流，哦也~）

※推荐
推荐3首歌。Room201。Happy Birthday。夜空ノムコウ。网上找到的[夜空ノムコウ]版本居然是须贺和YUI合唱的，真让人惊喜。其实还有首有名且有趣的[19才]，现今还做着我的手机铃声，只是排在第四位。

2009年终盘点

今日小雨。湿哒哒粘糊糊的，红茶包也有些潮气。趁着复习的中场休息，做一下09的年终盘点。盘点是每年必做的，数数听过什么歌、看过什么片子、去过什么地方、买了什么东西，还有花了多少钱，当然这个就不贴出来了，秘密啊。

※音乐
09年L团的各位大叔们还在玩SOLO，正经的单曲一枚也没有。BLESS不算，1.27才release，再好听也是要算在10年的；Hurry Xmas双小鹿版也不算，理由同去年，想抢钱明说嘛，还在Super Live上说应Fans的要求再发行，Fans的要求是你们几个快点并回来别到处沾花惹草好不好，海豆子你说谎不脸红。不过，今年圣诞的Goods还是要小赞下的，小鹿手办和帽子都很可爱（扯远了）。

# 新添的Artists：
シド / DREAMS.COME.TRUE / 吉田拓郎 / レミオロメン / Sukima.Switch
Lisa.Hannigan / Heinz.Holliger / Travis
# 删去的Artists：
N.A.
# 第一耳就爱上的歌：
Yui：[Again]（钢炼OP1，唱的时候背不下歌词总跟不上她的快嘴巴）
绚香：[梦を味方に] [みんな空の下]（恭喜结婚，10年好好休养，早日归来）
JUJU with JAY'ED：[明日がくるなら]
ステレオポニー：[泪のムコウ]（没记错的话，是高达00的OP之一，几个小姑娘歌写的不错，但现场有待加强）
スキマスイッチ：[全力少年] [水色のスカート]（第一次听是在玩太鼓达人的时候，前奏太悠扬以致开唱后有些跟不上节奏，真难，不过好听，后来找到作为插曲的片子[东京糖衣巧克力]也很有特点）
flumpool：[星に願いを] （Live时不断下坠的流星背景真震撼）
Sukima Switch：[ゴールデンタイムラバー] [雫]（钢炼最近的OP，歌词里有一句“How Many？需要多少代价来交换？”真是切题）
UVERworld：[美影意志] [アイ・アム Riri]（其实AwakEVE碟里几乎所有的歌都很赞，非要挑出一些的话，[美]的旋律很流畅，[Riri]的歌词有一句Rap后的平调“それは　それは　悲しみのストーリー”唱的我心里直发寒）
ゆず：[逢いたい] [虹] （也许大抵叫[虹]的曲子我都会喜欢吧。柚子今年Best Artist唱抢拍了> <|||，听说是设备的问题）
いきものがかり：[YELL]（今年最好的励志曲。不似[みんな空の下]忧伤、比[虹]更有深度。Super Live上和高中生的合唱很感人）
遊助：[ひまわり] （歌是好歌，词是好词，但现场待磨练）
レミオロメン：[粉雪]（其实我第一次听这歌是小田爷爷唱的）
Innocence Mission：[Beautiful changes] [500 Miles]（两首念念叨叨的歌~）
Lisa.Hannigan：[I Don't Know] [Ocean and a Rock]（声音很丰富的乡村音乐）
Muse：[Resistance]
# 新收的常听大碟：
UVERworld：[AwakEVE]（我并不因为它也带awake字眼而赞赏它，Takuya∞的声音的确很棒）
flumpool：[Unreal]（白金碟。08年11月release的，我收的晚了。赞赞赞~）
Lisa Hannigan：[Sea Sew]
Muse：[Resistance]
一张从VeryCD扒下来的VA碟：[The Music From Beautiful Angel]
吉田拓郎、DREAMS COME TRUE、福山大叔的几张补完的精选
今年收了好些Mozart的东西，几本想听的歌剧、一张10CD的Ingrid Haebler老太太的[Mozart Complete Works for Piano]、一张10CD的Mozart诞辰250年时的庆生碟、Jeno Jando的钢琴协奏曲、还有各种版本的K.314（Heinz Holliger老头吹得最好~）
其他还有Hifetz的几张贝多芬小提琴协奏曲、一张Maria Kligel、Ilya Kaler等等的[BRAHMS: Double Concerto for Violin &Cello;SCHUMANN: Cello Concerto in A Minor]（赞的）、一套30CD的拿索丝企鹅评鉴三星极品全收藏（想着VeryCD要被封火急火燎地收的，还没听完）等等
还有一张很有趣的OST [Nodame Cantabile Best 100 Collection Box]收录了Nodame有趣的乱蓬蓬组曲^^
-------------------------------
大致就是这样。今年因为忙，听的歌有些少，也没怎么关注新出的大碟们。看来10年要是闲下来，得做很多补完计划。不过，看各种年终Live的样子，今年似乎没出其他什么十分出彩的歌，难道也是因为金融危机？

※影像
这个就更加有些少了。好多连载的新番追到一半因为忙就给忘了，再闲下来的时候就懒得再看了，《天地人》是一个，《东京地震8.0》又是一个。忙碌有时也不知是不是好事。10年因为福山大叔的关系想要从头到尾地追《龙马传》，可它偏偏到现在还没有字幕片源（大河剧看无字的话太辛苦，方言土话太多了），老天是让我从此不看片，好好学习天天向上吗？还是想让我去看美剧。。

# 夏之岚
首先画风很独特，尤其在处理光影时坚硬的轮廓线，突兀，但却很能抓眼球，有些像彩色玻璃的感觉，其实也贴切，夏天的光就是如此直白的。其次是OP，虽然曲子一样，可是居然每集的歌词都不一样，而且写得很大胆很有趣。最后才是剧情、节奏和各种各样奇妙的人物。新奇是这片子带给我最大的感受，它很特别。
# 轻音少女
腾讯盘点的时候把它归入宅部，有些搞不懂，我一点不宅的说。和草莓棉花糖一样气质的片子，全片男人少得可怜。音乐元素，几首原创曲都不错。笑点也很充分，看这种片子会很快乐。其实今年我看完了[初恋限定]，还觉得是挺好的消遣，不过这么宅男向的片子就不列了。
# 钢炼FA
BONES的作品很少有不值得看的。他们本身推翻前部钢炼要重拍就已让我很纠结，虽然水岛精二有些扯。这期的本子是按照漫画来写的，剧情也许说得通很多，但人设为啥要改呢，头发为啥是金色轮廓线的呢，为啥还偶尔画走形缺钱吗。哎，可能是我太习惯一作了。不过，今年还是会继续追的，年番就是辛苦。
# 化物语
好吧。我承认，新房昭之是个好监督。这么既叫好又叫座的片子，不看可惜了。
# 续夏目友人帐
还是前作一样清新的感觉。亮点是黑白喵咪老师和脸上长爬虫的捉妖帅哥~
# 东之伊甸
大饼同志推荐之一。短。监督讲故事的能力很强大，节奏很紧凑，悬念抓得也很牢，虽然结局有些难懂。
# Coraline
其实我也老把它念作卡洛琳，的确长得像嘛。巧的是今年几部不错的动画都是木偶动画。这部特别的地方在眼睛，像日本人讲究名字一样，故事设定里只要眼睛被剥夺换做纽扣，就永远也回不到现实世界。色彩设定也很出彩。
# 夏日大作战
大饼同志推荐之二。言简意赅就是宅男宅女拯救世界的故事。出彩的地方是对虚拟世界的设定，关于盗取很多ID就会不断变大的具象化很有趣。
# Mary & Max
4月的片子。澳大利亚产。我12月才看。对人物的刻画很细腻。友谊万岁。据说是导演半自传式的片子，那猜猜他是里头的谁？
# 飞屋环游记
Pixar大作。一个关于一个退休的老头、一个黄帽子小胸章控和一只曾经会说话的短腿狗狗牵着一坨彩色气球下面挂了个房子打败了一个养了很多说话狗狗的坏人探险家拯救了一只五彩斑斓长嘴长脚大尾巴鸟的故事。很开心并且有些温暖的故事。另，皮肤的材质做得真棒，不愧是Pixar。
# The 9
色调有些灰。故事也有些灰。不过小人们各自的构造都挺有趣，拉链实在是个很奇妙的东西。

# 疯狂的赛车
今年看的第一本电影。难得的国产好电影。难得的从一开始没有让我猜出结局的好电影。
# 南京！南京！
我和Cmm、Q殿最后一次一起去电影院，还3个人看了一场变相包场的《东邪西毒》，虽然我不喜被90后像极了的王家卫。在新开的近江电影大世界，去的路上还路过Cmm出生的卫生院。我记得这些事情比电影清楚。最后说一句，电影不错，至少它能上映很不错。
# 第九区
我花了1.5个礼拜断断续续地看完了它。对种族间关系的探讨很深刻很有内容可以挖掘，尤其是特意用仿记录片的方式剪辑，导演想让观众思考的意图十分地明显。从技术上讲实在很诧异它居然是一部小成本片。另，大虾长得真不好。再另，今年好些片子都有9，是因为09年吗？
# 2012
这片子我在电影院看了两次，一次中文边上太吵一次英文外面开始下雨夹雪。场面很震撼。事后对2012是否末日的深究有些有趣。
# Hard Candy
06年的片子。很不知如何形容的一部片子。连剧情我也无法用一句话描述。它很复杂。一个未成年少女使计杀死了诱骗她并诱杀她朋友的成年男子？太简单了。中途一段阉割手术的心理描写十分出色。
# The Red Violin
98年的片子。讲一支也许是受了诅咒的红色的小提琴的各个主人们的故事。也很复杂。似乎是说，音乐是要用生命去体验的。
# Orlando
今年年中的时候挑了好些Tilda Swinton的片子看。Orlando是其中挺特别的一本。幻想色彩浓厚，讲了一个将近1600年的故事。对Swinton个人魅力的诠释也很充分，她实在是一个十分有气质的女人。
# …太多了，我不列了，累死了

# 白色巨塔
日版的。属于补完计划。很经典。对社会的看法，就剧集而言，十分深刻。手术镜头还是不敢看。
# LOVE SHUFFLE
很欢乐的一本爱情剧集。适宜茶余饭后和朋友一同笑笑看看。Q殿推荐。
# 一公升的眼泪
补完计划。我没流眼泪。不过，还是赞下众演员的敬业演出和编剧的感人不懈。
# 龙樱
第一本在PSP上看了的剧集。总在晚上。总会看得热血沸腾。然后后悔应该早看到这片子，当年高三就该好好学习天天向上。
---------------------------------
以上。我觉得我写这日志写得都快虚脱了。好片无限量，我写不完啊。。

※移动
今年去过的地方也很少，还是因为忙>< 。去了几次上海看展看演唱会。去了几趟北京呆了好久好久好久却哪儿也没去，只待在满是烟尘的工地上。唯一称得上旅游的就只有暑假随团去了趟洛阳和西安，看了看向往已久的古建筑们和美女们，当然还有坑里的泥人们，吃了很多清真美食，末了回来的时候还看了一眼都快3岁的龙凤胎（我还是弄不清楚我和他们什么关系，只明白是亲戚）。

※新置物品
这个我就不多写了，不然真的要虚脱了。手都有写发抖了。这一部分，总之很多很多。新购PSP3000一台、白色木兰台灯一座、新杯子若干、衣服一打、裤子一坨等等等等。

以上。终于完了。

[备考笔记] THEORY OF COMPUTATION

好课。本科大四的时候还主动选修了的课。老师高高的。挺帅。却挑了个实在不怎么好的时间上课。周一大早。我总醒不来，醒来了也想着去了反正迷糊还是多睡会养好精神下午好干活就又躺下了。然后转眼就要考试了。再看书，那些本科时不懂的依旧不懂。却又有些大四时备考数值分析时热血沸腾的感觉。

对那些曾经Make Me无比Confused的概念和理论一一罗列解析：

• 可数无穷Countably Infinite及对角化论证Diagonal Argument
  这是计算理论里第一个十分纠结的概念。可数无穷很难在脑子里成像，书上给出的定义是“可数无穷集合A与N之间存在一个双射f ”，也就是说，A的元素与N存在一一对应的关系。我们可以像数自然数一样枚举它，如果你活得像宇宙一样长，就可以永远抱着数完它的信心。
  Cantor的对角化原理可以用来证明某集合是不可数的，通常假设某集合是可数的，并罗列其与N间的双射关系为一列，那么若集合不可数，则可以按照对角原则构造一些元素，使其属于该集合但按照其构造规则不能被罗列。WIKI上给出了十分详细的证明，关于可数无穷集的幂集和实数的不可数问题。
  那么，我们可以对不可数无穷做以下描述：就是那些比可数无穷还要长的数列们，即使你活得像宇宙一样长，也还是放弃吧。
   
• 确定型有穷自动机DFA与非确定性有穷自动NDFA的等价
  等价，指的是其接受相同的语言。如果对于某类语言，有一台NDFA按照非确定的规则转换状态接受它，那么就存在一台DFA以NDFA每读入一段输入串后的可能状态集合为状态，按照确定的规则接受它。并且，这样的构造是指数的。
   
• 正则Regular与非正则语言以及泵定理Pumping Lemma
  正则语言可以用表达式写出来，可以被FA接受，其中可能用到组合字符串是可以穷举的；非正则语言是难以预料的，只能用文字来表述，比如根据前端决定后段的字符串。
  泵定理描述正则语言中某些字串可以被无限重复（Kleene）的特性，相应地，可以用来反证某些语言是非正则，即假设其正则，但举例一个带n的特殊字符串，其长度大于n，无论怎么分解为xyz，y≠e，|xy|≤n，但重复y段i次后得到的xy^iz不属于该语言。（PS：其实泵定理只对不可穷举且存在环的正则语言成立。）这里有两个技巧：第一是如何选一个特殊的字符串，a^nb^n、ww^r之类是最常想到的；第二是如何证明“无论怎么分解”，通常最简单的方法就是分情况讨论。当然，证明本身就带有艺术性，需要因地制宜。
  正则语言在并、连接、Kleene、补、交下封闭的，也可以此反证语言非正则，如交，使某语言与某正则语言相交得到非正则语言。将封闭性和泵定理结合，是一种比较方便的证明非正则的方法。
   
• 等价类和状态最小化
  一个正则语言的等价类为它本身、续尾后能被接受的字符串和续尾后不能被接受的字符串。
  状态间的等价，≡是说对于状态p和q，想要到达最终状态，要走的路是一样的（当然，走不通的路也是一样的）。带下标n的≡则是说如果只走n步或更少，那状态p和q是≡的。那么其实，≡就是≡下标∞。
  用状态最小化算法寻找FA的标准型状态，就是从下标0开始，不断分裂寻找等价状态（以相同的字符串走到终点），直到不可分。
   
• 下推自动机PDA的转移关系们
  ((p, a, β), (q, γ)) 当状态为p且输入带读入a且β在栈顶时，抛出β，推入γ，且转换状态为q；
  ((p, a, e), (q, b)) 当状态为p且输入带读入a时，推入b，且转换状态为q；
  ((p, a, b), (q, e)) 当状态为p且输入带读入a且b在栈顶时，抛出b，且转换状态为q；
  ((p, e, e), (q, e)) 当状态为p时，转换状态为q。
   
• 上下文无关语言Context-free与非上下文无关语言以及泵定理二世
  上下文无关语言CFL是一种可以从某一个种子开始向两边无限蔓延开的语言，生成什么字串只与文法相关，而与种子当前的上下文无关。
  泵定理二世基于语法分析树描述CFL中某些推导规则可被无限重复（S→aSb）的特性，可用来证明某些语言非上下文无关，即假设其上下文无关，但举例一个带n的特殊字符串，定义n与φ(G)之间的关系使得字符串长度大于φ(G)，分解为uvxyz，v≠e，y≠e，重复v、y段i次后得到的uv^ixy^iz不属于该语言。其技巧与泵定理一世大同小异。
  CFL在并、连接、Kleene下封闭，交和补下不封闭。CFL包含正则语言，其与正则语言的交仍是CFL。因此，也可用封闭性证明。
   
• Chomsky范式
  Chomsky范式要求每条规则的右边必须小于2，见wiki。普通CFL可按如下步骤转换为Chomsky范式：
  1. 对所有的结束字符串a，引入一个非借助状态A，增加规则A→a，那么X→a就变为X→A；
  2. 消去e规则：a) 寻找所有可能推导出e的状态集合Λ，包括X→e，Y→X，Z→XY；
                         b) 对所有含有n个属于Λ的状态的规则，替换为2^n条新规则，
                             如X→AYZBY，Y∈Λ替换为X→AYZBY、X→AZBY、X→AYZB和X又AZB；
                         c) 消去所有e规则。
  3. 分割所有长规则（右边大于2），如X→ABCD变为X→YD、Y→ZC和Z→AB。
  4. 消除规则中的单链，即若存在规则X→Y，而Y总是推出Z，且Z有规则Z→a，则替换X→Y为X→a。
  用动态规划的方法确定字符串是否能被某CFG输出，其前提是该CFG以备Chomsky化。
   
• 判定Decide与半判定Semidecide、递归Recursive与递归可枚举Recursively Enumerable、递归函数
  对于w∈L，图灵机M始终生成接受格局；对于w∈L，M始终生成拒绝格局。这时，就称M判定L，而L是递归的，即可判定的。若只满足前半部分，则称M半判定L，L是递归可枚举的，即可半判定的。
  对于所有w∈Σ*，有M(w)=f(w)，即M在输入w上停机并在带上写f(w)，称M计算f，f为递归函数。
  半判定的M不是算法。存在非递归的递归可枚举语言。
  如果一个问题和它的补都是递归可枚举语言，则其实递归语言。
   
• 几种扩展图灵机与标准图灵机间的等价性
  k带图灵机：标准图灵机M'将带形式化地分为2k条轨道（间隔排序），其中k条用来记录k带图灵机M相应条带上的信息，另k条来用来模拟带头的位置。M的t步，M'需要O(t*(|x|+t))步来完成，|x|为输入的长度。
  双向无穷带图灵机：可以用2带图灵机模拟，再推到标准图灵机，模拟花费线性时间，因为这种图灵机每步只有一条轨道是活动的。
  k带头图灵机：将标准图灵机的带形式化地分为k+1条轨道，1条用来记录信息，其余用于模拟带头的位置。那么，每步的模拟将带来两次扫描，一次确定带头位置，一次改变符号或移动带头。这样的模拟需要花费平方时间。
  非确定型图灵机：由于非确定性图灵机可能产生的格局是有限的，设最大为r，那么设计3带图灵机，第1条带存储输入w且永远不变使得每种计算可在相同的输入上重新开始，每一次计算按照{1, 2,.., r}*生成的顺序转移格局，第2条拷贝第1条的数据赞着第3条中记录的顺序模拟计算，两次模拟计算间生成新的顺序存储于第3条中。这样的模拟至多会在r+r^2+…+r^n次失败尝试后，才会产生对应NTM的选择。因此，这样的模拟需要花费指数级的时间。
   
• 通用图灵机对任意图灵机的模拟
  对任意一台图灵机M=(K, Σ, δ, s, H)，可以通过二进制编码的方式描述其所有的状态、符号和状态转移表。其每个状态表示为以q开头，长度为i，2^i≥|K|的二进制字符串；每个字符表示为以a开头，长度为j，2^j≥|Σ|+2（2为←和→符号）的二进制字符串。那么状态转移表就可表示为相应的多个二进制四元组，并以字典升序排列，如(q, a, s, a)表示为(q01, a100, q00, a100)。注意：停机状态不会出现在任意一个四元组的第一分量上，因此在四元组中搜不到的格局就是停机格局。
  那么，设计这样一种3带机器U'：初始化时，第1条带写入输入字符串w，第2条带写入上述形式描述的“M”（应该只是四元组集），第3条带写入q0^i（初始状态）。在每一步对M的模拟中，U'搜索第2条带直到发现“第一分量与第3条带相同”“第二分量与第1条带相同”的四元组。若发现，则“把第3条带上的状态改为第三分量”“完成第四分量编码的操作（写第1带或左右移）”；若未发现，即停机。
  最后，用标准图灵机U模拟U'，就得到了通用图灵机。
   
• 停机问题是递归可枚举的，但是非递归
  任何可以归约到停机问题的问题都是不可判定的，即没有算法。
   
• P类与NP类
  P类问题是存在确定型图灵机在多项式时间O(n^k)内能解决的问题；
  NP类问题是存在不确定型图灵机在多项式时间O(n^k)内能解决的问题，即确定性图灵机需要指数时间O(c^(n^k))。
  P类问题是NP类的子集。
  NP完全问题是最难的NP问题，所有NP问题都可以归约至它，也就是说，NP类等于P类，当且仅当NP完全问题属于P类。
   
   
  # 老师ppt上的两张图，很具象地表达了NP、P、停机问题、SAT、RE、RE补等之间的关系
   

• COOK定理Cook–Levin theorem
  Cook定理说，SAT（Boolean Satisfiability）是NPC问题。简单地说，如果对某一个布尔表达式B.E.，存在使其布尔运算结果为1的组合，其就属于SAT。显然，SAT是一个NP问题。那么，对于任意一个NP问题，即存在一个NTM在P(n)时间内解决它，只要找到其归约到SAT的方法（存在多项式时间的映射F），就可以证明SAT是NPC的。
  我们可以将NTM接受该NP问题的过程画成一张P(n)*P(n)的表格，那么，我们可以定义一个布尔表达式F来表述该表格，F∈SAT当且仅当表格对应的输入被NTM接受。F=φ(cell)∧φ(start)∧φ(move)∧φ(accept)。φ(cell)是对表格中每个单元的值的要求，φ(start)是对表格初始状态的要求，φ(move)是对其转移过程的要求，φ(accept)是对其接受格局的要求。wiki上给出了另一种形式的F定义，或者说是要求的划分，证明过程也很详细。但是无论如何定义，其都有一个准则，即F能够准确地涵盖表格的所有内容，包括初始格局、接受格局、转移的中间格局等等。F=1将生成所有NTM的接受表格。并且，生成F本身的算法复杂度是O(P(n)^2)。
  类似的，SAT可以归约到3SAT，其也是NPC问题。
  Cook定理给出了第一个NPC问题，可以用来证明其他问题是NPC问题（把SAT归约到该问题），不过构造，实在是门技巧，还需要极多的灵感。

午后的声音。Spitz~

对音乐一直保持着先闻声再识人的习惯。往往听一首歌很久很久以后才会去翻歌手的名字找他的履历，至于记住相貌更是几个月以后的事情了。其实不止对歌手吧，对身边的普通人也是这样的。高中的时候花了两年才把全班同学的脸和名字对号入座，结果才保持了一年就又分开了，再到现在，就连名字也有些模糊了。不知道这算不算是我的生理缺陷。

Spitz算是唯一一个我先识人再闻声的。Spitz是一种小狗的名字，狐狸犬类，小型，分布于芬兰、德国、日本。日本银狐犬Japanese Spitz，毛是纯白色的，据说对主人特别地依赖但是对陌生人却神经质地多疑。当年瞎逛的时候见到一文谈到Spitz小犬的育养方法顺便说到了日本有只乐队就叫Spitz。突然就觉得好有趣。于是就。。。恩。

相比L团，Spitz绝对是支朴实无华的乐队，编曲风格也明亮得多，就连行事也低调得一塌糊涂，宣传活动也很少参加。用Vo.草野正宗的话说，“我们不像是一级的乐队”，“是像副食小吃性质的乐队”。虽然也是日本乐届的传奇人物，但就算是在鼎盛时期他们也不曾大红大紫到抽筋的地步，不过还是属于单曲初登场NO.1在公信榜上徘徊的人。

Spitz的歌大多是歌颂青春的。这个主题。。。的确有点老套，但是草野唱来却从没有感到过丝毫的恶俗。就算是俗套，也是完美的俗套，就像白雪公主和白马王子幸福地生活在一起的故事。听歌的时候总觉得有风的感觉，暖暖的，想要闭上眼睛和曲子一起慢慢地左右摇摆。应该叫陶醉吧。Spitz的歌最适合在有阳光的午后听，要走在有树荫的路上，晃着小包；地面有白色的线的话，就沿着一直走下去，看看可以到那里。都是些快乐的歌，轻轻的鼓点，轻轻的吉他声，仿佛他们对于生活从来都没有什么不满，一直都是很乐观的样子；偶尔有些忧伤，也是细细地藏着，不似樱花，倒有风一样的豁达。

草野的声音在众多歌神面前实在不算出众，有点沙，没有太多爆发力；但配上Spitz的音乐，却很神奇地扣人心弦。一曲过后，空白的静音处，总还有些什么东西在那里回荡着。没有震撼，却是动人的温柔。很多的温暖在里面。

给Spitz称号大多是日本民谣摇滚诗人团体。草野的歌词，即使在我这个日语半吊看来，也是美得一塌糊涂的。有人把草野比作歌坛的村上春树，是想赞叹草野的文采吧。但有时却不太能把握词的主线，有种“只是在表达某种情绪，其实什么也不想说”的感觉。草野自己也说过，写歌其实就是带一个小本子在身上想到的句子就随时写下来，再串在一起，再推敲斟酌许许，便就成了，之类的话。听到他这么说的时候觉得很放松，原来草野的歌诞生在停停走走断断续续的旅行中，那么当然，听的时候也可以轻松些，多多地感受它散发出的随意的灵性。

     

对音乐的执着是好乐队的天性，也往往最能打动人心。Spitz也是，Laruku也是，还有Nirvana、H.I.M、Muse、Green Day等等无法穷举的各位们，个性里都有相当的“固执”在里面。队员间往往会分开好久各自写歌、练习或者汲取灵感，当然还有过私生活，攒到快要满溢的时候再聚到一起，摊开几十首甚至一百多首歌的谱子，边上放着预选录好的小样，然后举手争论再举手，挑不出了就再补，最后留下的10+首才成为下一活动阶段会发布的作品。有的做成单曲，有的收入专辑，流转到我们的手上和耳朵里。对于精致的音乐品质的追求，即使不能打榜也要坚持自己的想法的勇气，相比之下，真的足以让某些平均几个月就发一张专辑的所谓歌手无地自容。

当然，说些题外话，Major乐队的早期作品其实都是市场和他们自己的个性博弈下寻找均衡的产物，只有到后来渐渐大牌了Member们也渐渐想开了成熟了，才有了更多的资本和力量坚持自己的信念，这也就是常说的“听到了成熟的曲风”的时候。

 

拿Spitz和L团比较的话，Laruku们多少有些王样的味道，live的时候也要在高高的舞台被膜拜；Spitz则更容易亲近些，有些邻家哥哥谈吉他唱歌的味道。很难说哪种更让人喜欢，事实上，Spitz多的是亲和力，而Laruku多的是控制力，总觉得听他们的歌思想很容易被控制XDD。对Spitz的喜欢可以放在心里一年一年慢慢地发酵，但是换到Laruku身上，其实狂热更多些，不在live上狂喊他们的名字，就实在无法想到其他方法可以表达得淋漓尽致。

好在两者，我都不偏不倚地喜欢着。

※推荐
推荐3首歌。一首做了我将近半年手机铃声Q殿也十分喜欢的[夜を駆ける]。一首质朴温暖单曲封面是只林中的小梅花鹿的[若葉]。最后一首，Spitz的名曲[Robinson]，午后红茶CM曲，贴切到美妙的曲子、声音和香味。

 
 

---

这文章以前在BAIDU空间发过，带来了第一次来自搜索引擎的访问。今年有个很大的愿望就是把“亲爱的人们”写完，这个“宏大的目标”曾经因为BAIDU空间的废弃而一度搁置让我觉得可惜。有爱就要大声说出来。所以，还是从这篇对Spitz的爱开始，谈谈我心里那些无比亲爱的人们。

[论文笔记] A Developer's Guide to Silhouette Algorithms for Polygonal Models

Paper: Tobias Isenberg, Bert Freudenberg, Nick Halper, Stefan Schlechtweg, Thomas Strothotte, A Developer's Guide to Silhouette Algorithms for Polygonal Models, IEEE Computer Graphics and Applications, July 2003

---

本文是一篇就从3D Polygonal模型自动生成轮廓线问题展开的综述。算是读得挺细。断断续续一周有余。

问题描述：轮廓线，也就是绘画上说的线稿，用于勾勒物体的形状、阴影等，以区分于背景和其他物体。本文着眼于讨论从Polygonal模型自动生成轮廓线的诸多算法。
文中定义轮廓线为silhouette，分为counter、crease、border和self-intersection四种：counter是前景最外围的轮廓线，区分其于背景；crease指物体上的折皱等，如正方体的边；border针对非闭合的模型，指那些只与一个polygon相邻的边；self-intersection当一个模型的两个polygon相交时出现。轮廓线可以数学地定义为法线与视线相垂直的点集，如下图所示：
  
但不幸的是，我们只有面的法线定义，而边上的点由于被多个面共享，其法线定义是暧昧不清的。因此，从计算的角度，轮廓线被定义为：模型上同时被正向和背向Polygon共享的边的集合（应该是指counter吧）。

轮廓线算法通常需解决两个主要的问题：检测当前视点的轮廓线集合和判断这些轮廓线的可见性。有以下几类算法：

• Image Space Algorithms
  这类算法通常利用传统渲染技术中的图像缓冲区（如color、z-buffer、normal等），运用图像处理技术扩大其中的不连续性（边缘检测技术），以寻找轮廓线。其结果是一个与成像分辨率相关的像素矩阵。典型算法如：Saito和Takahashi的z-buffer、Hertzmann的normal-buffer以及Deussen和Strothotte在这基础上的应用pen-and-ink等。
    # z-buffer
    # z&normal-buffer
  这一类的方法易于实现，而且通常很快，并且能够自动地找到self-intersection类的轮廓线，也具有通用性和鲁棒性；但是，用户能够控制的参数很少，并且最后得到的轮廓线没有解析表述，这使得后续处理如风格化等很难展开。
  这类生成的轮廓线没有明确的边界，轮廓线上像素的灰度取决于缓冲区中边界特征的强度，而这也使得这一类的轮廓线无需烦恼线条锯齿的问题；另一个特征是其精确到像素，也就是说一些不足一像素的细节将会被隐藏，但这单从视觉的角度而言是不重要的。
  
  
• Hybrid algorithms 
  这类算法通常需要在物体空间上作一些变换（位移等），然后也是利用渲染过程中的图像缓冲区（z-buffer）生成轮廓线。其结果与上一类方法相同，也是一个像素矩阵。典型算法如：Rustagi的stencil buffer算法，需四次渲染，每次将物体沿正负x/y轴移动一个像素，那么内部的像素就会有4个stencil值，而轮廓线上的像素则会有2-3个stencil值，而外部的像素则为0-1个stencil值，以此为区分，这种方法只能生成contour；
  Rossignac和Emmerik的算法基于z-buffer，通过将物体沿视线方向移动并调整wireframe的线条粗细，分别绘制wireframe和z-buffer来视线，这种方法对其他种类的轮廓线也有效；
  Raskar和Cohen的算法也基于z-buffer，先在白底上画正向面，这样z-buffer中就填充了正向面的深度值，再以轮廓线颜色画背向面，这样只有同时属于正向和背向面的轮廓边能够被画出来（深度值相等），这种方法可以画出指定等宽的轮廓线（通过在第二部放大背向面得到）；
  其余还有在三角面片周围增加一圈边缘、基于暗色环境贴图的算法等等。
              
    # Raskar和Cohen的back-front face方法                                 # Gooch的基于暗色环境贴图方法（很有艺术感）
  这类方法具有很高的可控性，也更具风格化。这类方法较上种较慢，需要做物体空间上的变换，但也是实时或准实时的。得到的轮廓线具有明确的边界，但也带来了锯齿走样的问题。并且由于是像素矩阵的表达方式，这些轮廓线只精确到像素，也不能很方便地适用于风格化后处理。此外，这类方法还存在一些由于z-buffer的精度而带来的数值问题。
  
• Object space algorithms
  这类方法完全基于物体空间，提供对轮廓线的解析表述，可以方便地应用风格化后处理。这种方法不同于前两种，分轮廓线检测和可见性判断两步进行。
  
  轮廓边检测：
  - Trivial method  此类算法是轮廓边检测的基础算法，分两步：1. 将polygon分为正向和背向两类；2. 找出那些有且仅被一个正向面和一个背向面共享的边。此算法很简单、易于实现，对正交投影和透视投影都适用，也能找到所有的轮廓线，但是它没一帧都需要查看每一个面的朝向和每一条边，其算法复杂度与模型的复杂度线性相关，在没有硬件支持的情况下，其只能适用于简单模型的渲染。
  - Subpolygon silhouettes  此类算法主要是为了改善多边形轮廓的人工痕迹，使得轮廓线更逼近于真实物体。此算法是以多边形无限逼近的自由曲面为基础来考虑轮廓线的。计算顶点法线与视线间的点积，由于曲面本身法向的连续性，就会存在+/-符号的突变。对于那些两顶点点积符号不同的边，使用线性插值生成点积为零的点，并连成轮廓线。这种方法生成的轮廓线更自然，也更适用于后处理。如下图所示：
            
  # subpolygon silhouette算法示意                                               # 算法结果示意
  - Precomputation methods  此类算法主要是为了改善检测算法的计算速度，通过事先做一些预处理的方式。如：
  Gooch等将模型面的法向量映射到一个高斯球上，并在球的中心放置与视平面平行的面。这样，面间共享的边就可以用法向量连起的弧线表示，而与球中心的面相交的弧线对应的边就是轮廓线。这种方法节省了每帧判断面朝向的时间，只需判断弧与面是否相交（弧本身是预处理的），如下图。为了减少相交判断的计算量，可以采用层级细分、或者将球映射到外切正方体的方法等；
               
  # Gooch的高斯球算法示意                                                       # 算法结果示意
  Sander等人建立了一种存储边信息的层级搜索树（边储存在节点上），面片根据节点间的层级关系成类。每帧搜素完全背向和完全正向的面片类，相关的边则被剔除，剩余的则是轮廓边；
  另外，还有Hertzmann和Zorin、Pop等人基于对偶空间Dual Space的预处理方法（忒高深），以后再作讨论。
  - Stochastic method  此类算法以空间和时间的连续性为前提，先随机选取一些边并用Trial Method检测其中的轮廓边，之后检测这些已知轮廓边附近的边是否为轮廓边直至画出一条完整的轮廓线，下一帧也只检查上一帧附近的边是否轮廓边（短时间内模型不会变化太多）。这种方法速度较快，是实时的，但是只能检出完整轮廓边集中的一部分。
  
  线条可见性判断：
  可见性判断是计算机图形学的经典问题，一些传统的可见性判断方法（如z-buffer等）在此依旧适用。作者按照对象将这部分的算法分为Image、Object Space以及两者的混合体Hybid这三类。
  - Image space  这类算法基于z-buffer等可见性判断，像素级别精度。
  - Object space  这里有很多算法，不只解决线可见性的问题。作者在此处提到了一个有趣的概念QI（Quantitaitve Invisibility），即对一个点而言挡在它和视点之间的正向面的个数。QI为0的点可见，其他不可见。简单情况下，只有当边与轮廓线相交时QI值才会改变，如下图所示。边的初始QI值可通过光线追踪的方法以某一点为视点建立，根据其是否穿越轮廓线来判断QI值的增加或减少。Markosian、Herzmann和Zorin等人分别就QI做了算法速度和扩展应用方面的研究。这些算法均提供精确的可见性信息，但是其计算复杂度也相比Image space大些。
      # 这是一条在物体后方的线
  - Hybrid  这类算法是前两者的结合，提供一种既快又有解析表示的解。如Northrup和Markosian的方法，其对每个三角面片和轮廓边着色，以z-buffer为基础渲染一张ID buffer。每一帧，ID buffer被读出，并搜罗其中所有出现了的轮廓边ID，以此为可见集合。Isenberg基于类似的原理给出了基于z-buffer的算法，并且由于z-buffer在数值上有时并不稳定，其主张将附近8邻加入决策。这类算法是Image space和Object space在速度和精度上的权衡。

新年

2009年的最后一个晚上。一夜浅眠。做了些梦。
早晨醒来的时候，头有些涨疼。但心里想着新年的第一天要是睡懒觉了这一年都会持续这种恶性循环的生活，于是就起来了。

去了趟邮局。确认它开着。搭讪了帅帅的温柔的邮局的包裹GG。买了3张4块5的邮票。

到实验室的时候房间的门还锁着，我兴奋地摸钱包开门，想着要做2010年出现在教一实验室的第一人。可下一分钟我就发现，我似乎把卡忘在了玻璃门的里面。真窘。辗转各邻居实验室搭讪工作中的GG们帮我开门，无果，这东西真是让人恼火地先进。遂去找老付，说实话我真不想新年见到的第一个熟人是那“关门”的。所以好在没有找到。不过遇见了老付的博士老婆和他的狗，于是我进了实验室。还是幸运的第一个。很开心。

坐下来给阿喵、Qjj、Cmm和我自己写明信片。10点钟的时候冯粮城来了。他是我2010年见到的第一个熟人（我和老付的老婆不熟，和他的狗更不熟）。

中午的时候去寄了卡片。我朝着邮筒说了三声拜托。拜托别寄丢快快地到她们手里保佑她们在海外一切顺利（邮筒君：我又不是土地庙XD）。

2010年，依旧许和去年一样的两个愿望。希望一切顺利。希望世界和平。