文明競逐與衝突－原住民的文化問題

悠久文明－原住民文化

• 約 15000 年以前移入台灣
• 南島語系、祖靈信仰
• 文化特色：屋架構築、火耕、黥面、輪舞…等
• 音樂、工藝與神話文學
• 各族各部落間有不同的祭典文化

根據以前讀的歷史，台灣目前出土最古老的是長濱文化，時間至少在 15000 年前。而產出的古物到底能不能證明是否是原住民的祖先？雖然在文化特質上相當相似，即便如此，能說明的是有密切關聯。

南島語族的語言高達 1200 種，相比漢語、英語可說是毫不遜色，可以說是雄霸海洋的偉大民族。其文化特色有屋架構築，常聽到的有石板屋、以竹、茅草、檜木搭建半穴居，火耕，在生活習慣上都是依靠大自然所擁有的。

• 清領時期：
• 封山：土牛番界
• 開山撫番：破庄滅族、喪身滅社
• 日治時期：
• 理蕃：政壓、同化、皇民化

從清領時期開始，密切地接觸外來的文化與新住民。分別在清領時期有所謂的封山，避免原住民和漢人之間的衝突，或者是作為怕漢人與原住民相結反清。

而到清領後期，開山撫番主要為開闢道路，積極地經營與原住民之間的關係。其中當時最有名的是開拓的道路－八通關古道。而在隨後的日治時期也受到所謂的理番，也就是霧社事件發生的時機點，關於細節可以在電影賽德克拉萊中看到。

• 國民政府～
  認為「 山地同胞 」遲早會被同化為與一般的漢人無異，當時並不認為原住民是個問題。如果是種不正視其存在，落入一種傲慢態度。
  • 「民族自決」
    人民可以自由決定他們的政治地位，並自由謀求他們的經濟、社會和文化的發展。對於 現代國際體系 中，處理原住民事務的原則。
  • 「原住民族基本法」
    為保障原住民族基本權利，促進原住民族生存發展，建立共存共榮之族群關係。 落實不佳 。
  • 「原住民族政策白皮書」
    民國 99 年擬定， 更凸顯漢人與原住民之間的差異 。

在國民政府遷台後，民生問題就越來越受到漢人所掌管。

一開始認為 山地同胞 ，光是這一 同胞 一詞就帶有一點點的認同感，即使原住民不這麼認為，所以並不認為原住民是個問題。這表示著什麼？如果是種不正視其存在，落入一種傲慢態度是有可能的，而不去認為是問題，也帶有一點多元文化的精神。

在 民族自決 一詞出現後，對於現代的國際體系中，民族自決對於處理原住民事務的原則，政府也依序做了幾項政策。其中「原住民族基本法」為保障原住民族基本權利，促進原住民族生存發展，建立共存共榮之族群關係。雖然基本法定義的早，但是實施上仍然沒有執行力。

而隨後在 99 年擬定「原住民族政策白皮書」，更加地區分了漢人與原住民之間的差異，也有人說擴大 漢人沙文主義 的優越意識。

為什麼這一段時間會開始注意到原住民？甚至還分給它們原住民身分？其一，為了顯示出自己國家的文明，按照民族自決的原則實施政策，其二，更可以做為執政者的政見，這一無傷大雅的政策，不就是撥點尊重認同給他們，就能討好他們，更能獲得大量的支持。這也是一種 操弄手法 ，正如同支持同志婚姻於美國，可以作為一個文明的現象。

做一點不同的舉動，就覺得文明就可以顯得更高尚。

文明衝突－蘭嶼的小七決策

• 漢人身分－劉克襄說道
  「慎思啊！小七，別繼核廢料後，又成為漢人帶給蘭嶼的另一個惡靈！」認為小七進來勢必以物質思維、貨幣數據，取代傳統以物分享、回饋與共勞的社會結構。
• 在「了解對方」之後，才能共同決定別人的前途，但網路自由、資訊豐富不足作為「了解對方」

小七便利商店在蘭嶼開店的時候，引起相當多的討論，其實小七一開始也不是漢人社會中的一部分，歷經好幾年的虧損才發展到現在的受人歡迎，一開始不被看好的 7-11 引入台灣，正好比討論 7-11 是否引入蘭嶼。

在這場討論中，主要由漢人身分的專家 ? 與當地人相互對話，其中以漢人身分的劉克襄為例

劉克襄：「蘭嶼和其他離島差異甚大，它並不屬於漢人社會。反而擁有一個獨特的海洋生活體系，自成複雜的生態生命觀，以及豐厚的自然知識庫。當其菲律賓的近親大量流失舊有智慧時，他們仍完整保留，足堪為世界罕見的文化遺產。可它又是如此地脆弱，如其地理位置，被台灣緊緊宰治著命運。假如小七進駐了，一定很快就會擊跨所有雜貨舖，讓它們大量消失。小七能像達悟人經營的雜貨舖那樣可以賖賬？小七的門口可以賣飛魚乾？小七會讓自己做為交換村民生活資訊的平台？小七能以企業公益的身份，融入達悟族文化？」

不屬於漢人社會又能表示什麼，罕見的文化遺產總是這麼脆弱嗎？自認漢人文化內的產物一定會取代他們原有的文化，不就是一種自視甚高的態度？以為自己所處的文明，一定可以勝過於蘭嶼文化。害怕這罕見文化遺產的消失，卻也認為自己的文化甚高，保留這文化的意義不就是做給別人看嗎？過度「替別人著想」的行為，好比要特別做出與別人不同的行為，強調自己的 階級 比較高。

過度！就是！多管閒事！

難道，漢人的眼中的蘭嶼只有碧海藍天、獨木舟的美麗風景才算是蘭嶼？而 7-11 在蘭嶼開設就這麼不堪入目嗎？

外來人希望遠離都市叢林，來蘭嶼看到的是一派天然不受現代文明汙染的淨土，但蘭嶼人本身是不是覺得有家便利商店會方便許多呢？究竟這塊海天淨土是為都市人凍結的擺飾，還是當地人必須俯仰其間的生活空間？

本島也有很多台灣美景，也在周圍建設不少旅宿啊，針對蘭嶼就不予許這樣。對蘭嶼的不信任感，是認為他們沒辦法處理這樣的文明不是，又是在強調自己有多文明了。

助教： 把大自然跟鄉土美化，「從開元港往北，沿環島公路接近朗島村時，海邊出現一間白浪板屋的雜貨舖，叫達悟超商。超商前設有一蘭嶼傳統涼亭，四五個部落的女人坐在上面吹風聊天。」然而這種美化也是不切實際的，因為他無視了當地的困苦與基本建設的匱乏。

題外話：我們可以從資訊中認識他們蘭嶼人，他們也能藉由 7-11 了解外界所有的文化資訊不是嗎 (蘭嶼小孩想吃薯條，卻不知其何物)？蘭嶼目前真的有小七，也在前一陣子九月多時，遇到鳳凰颱風，甚至便利商店的貨架被一掃而空。

• 「一定要把我們當作稀有動物觀賞嗎？」
  文明的傲慢 ？價值不由外地人決定。
• 關於擔憂的文化困境
  蘭嶼人表示「長久文化習慣難道經不起外來入侵？如果真經不起，可見也沒多大特色。」
• 比起核廢料場，小七來得有誠意，何時何地到來都有說明。只有小七有文化考量，放置核廢料造成的利益關係要從何談起，決策來源仍屬於佔有多數的文化。

上山種芋頭、出海捉飛魚，這些都是蘭嶼雅美人長久以來的生活秩序。

蘭嶼小孩過得每天吃山珍海味的日子，文化習慣相當長久，有脆弱到無法自己解決外來的入侵嗎？
在蘭嶼人口中道出「一定要把我們當作稀有動物觀賞嗎？」看出，漢人的專家們不斷地評估與討論，這外界的聲音已經讓他們覺得他們成為稀有動物的存在。

這不就是傲慢嗎？要求別的文明要過什麼樣的生活、擁有什麼樣的資源 …蘭嶼人當然要小心謹慎，找出最有利於自己的生存策略，但把他們想得這麼弱，其實也是一種漢人中心的自我膨脹。

總之，是否會造成困境，還是蘭嶼人最清楚。歡不歡迎「小七」的問題，留給當地人來評論吧！

小七登陸蘭嶼雖然只為當地帶來 12 個職員的工作機會，但比起台電核廢料場，至少明明白白告訴社會：「8月8日準時開幕」，不會掛羊頭賣狗肉，硬是將核廢料場扯成魚罐頭工廠。1 萬家小七對蘭嶼的傷害，也比不上一個核廢料廠。

因一個小七引起的討論比不上過往的核廢料廠，這利益之間到底要怎麼批判，原來他們的特色價值的利益必須要因為漢人而存在？放置核廢料的利益關係又要從何談起？不正也是原住民才 50 多萬人，佔多數的漢人政府的決策，有如大我天朝般，接受恩賜吧！

說台灣多元文化，並不代表多元文化的精神在於必須要有多區隔，這區隔更顯示階級高下之分，掩飾主流文化的支配現象而已！

• 文化入侵、破壞早已不是第一例，民宿增加、核廢料、台東農會超市 … 等，那些有造成破壞的部分，最清楚的還是當地人。
• 漢人身分－劉克襄
  「我是為你好」論證下提供單方面意見
• 在這事件，可以提供意見，但絕非價值的指導者。

其實台東農會超市早就進軍蘭嶼了，但至今並沒有破壞達悟族的飛魚季，或是拼板舟文化，傳統文化顯然並不會因為便利超商或超市而受到影響。

「有空調又明亮的便利商店開在陳舊灰暗的雜貨店附近，搶走客人」這個畫面對於身為現任都市人的我們來說，實在是太具體、太吸睛。作為「文化破壞」的亮點，它可能讓我們難以察覺蘭嶼文化改變的其他面相。

一位達悟大哥說：「其實最大的破壞，當觀光客大批湧入的時候，就是一種破壞了。」

在這事件，可以提供意見，但絕非價值的指導者。「我是為你好」論證，是基於對方的福祉出發，為對方指出該走的方向。在於萬一對方表示異議，論者會如何回應。

文化交流－豐年祭典的尊重

• 阿美族豐年祭有 文化傳承 的功能，同時作為感謝上蒼保佑風調雨順，感念祖靈庇護，代表尊老敬祖 族性
• 部落的祭典有其莊嚴與神聖性，並非官方觀光、酬庸的商品，這並非 文化交流 的本意。
• 「有意想參訪的朋友，帶著尊重的心，我們很歡迎，帶著 高姿態 的心，獵刀很快會吻你的脖子。」－ 「豐年祭不是給觀光客看」　張震嶽發言延燒　

觀光客進入部落參觀慶典時要尊重現場的指導，不要干擾和破壞，應該秉持尊重的態度，部落的祭典不是活動，有其莊嚴和神聖性，觀光客不要因為要拍照而影響祭典進行；可以將祭典和活動分開，讓遊客可以參加活動，但是原住民也可以保有祭典的原貌，不受干擾。

大張旗鼓地為各縣市原住民宣傳他們的活動，活動與祭典之間界線越來越模糊，本意也越來越偏離。記住的是祭典並非官方觀光、酬庸的商品，這並非文化交流的本意！

在花蓮，近幾年興起的後山王東崑萁，為花蓮縣帶來龐大的觀光財。舉辦一系列的活動，展現花蓮縣特色，也因此在舉辦各種活動中給予金錢上的補助。

當然原住民活動是不可缺的一角，辦任何活動都有錢賺，甚至每一次辦活動非得要召喚外地族人回來不可，在用金錢補助活動上，是否呈現漢人認為原住民的豐年祭文化具有投資價值，是一個不錯的消費商品，花點錢，就能帶來更多的周邊利益。

他們的特色，被用「多元文化」的藉口，放置在觀光業的一環中，更是剝奪他們對自我祭典的掌握權，難道必須要因為一張海報上的活動時間而運行傳統祭典？

在某一次的活動中，不小心越界，產生出 要求舉辦祭典­的阿美族青年交互蹲跳 的荒唐行為，原住民祭典一直以來都只有年長者可以命令年輕人，沒有權力地位的身分概念，身為協辦的政府，也不能隨意地命令它們。

其實這種荒唐事情不只一例，曾經也舉辦花蓮原住民族聯合豐年祭，以文化交流的本意，召集來自大陸許多少數民族進行交流，結果大陸少路民族卻占了大多數的表演行程，中間還有特地安排 “縣長進場”，大約 10 來分鐘，難不成「縣長爬進場？」網友如此戲稱，這時間堪比一個表演節目。

當然這樣想有點對這件事情全方面的恐懼，文化交流只是按著流程跑這麼簡單？活動契機也許不錯，但是彈性限制仍有待考量。

情感受限－布農族打耳祭

• 打耳祭從早期獵鹿、山豬，因獵物減少而以抓豬增加祭典娛樂，祭典對於他們具有團結精神的教育意義。
• 外人情感門檻限縮下 ，原住民行為受到外部約束。
• 立法院要求取消抓豬比賽，否則砍原民會預算，往後射耳祭活動也不予補助。「射耳祭禁抓豬 布農族抗議」

布農族早期與山林為伍，是最懂得環保及愛護動物的民族。因獵物減少而以抓豬增加祭典娛樂，其實他們一開始的活動並不是抓豬，而是真的拿弓箭射獵物的耳朵。

抓豬競賽有一定規則，一個村落抓一頭豬，時間最短的優勝，裁判看過後，這頭豬就可以扛回各部落與村民共享。抓豬不僅在訓練年輕人抓豬技巧，更重要的是傳承團結和分享的文化。

只因為政府無法看它們做出這樣野蠻的行為，就這麼限制它們。看不下去的情感，也正表示外人情感門檻限縮下，原住民連帶地受到牽連。以 Elias 的話來說而言，這種看到別人做出的行為，心中會感到難堪，用嬌貴引起的「不舒服感」，因為台灣各個角落發出「感到不舒服」，所以它們就野蠻、不文明了嗎？

當然並不是，這種極端的情感驗證了強烈追求自己階級的優越性！

• 原住民抓豬活動、漢人供神豬，為何單獨原住民抓豬受到限制？習慣幕後隔絕的漢人文化。
  *「我們原住民的祭典不該被保留，很野蠻？那你們供神豬的就是文化？豬塞餵成那樣然後殺了供祭所以是高尚的哦？」-「射耳祭抓豬比賽被禁　紀曉君：你們的供神豬就是文化？」
• 原住民出國表演，會被稱作 台灣之光 ；但想維護傳統儀式時，卻被指成是 野蠻 的行為。

原住民抓豬活動、漢人供神豬，為何單獨原住民抓豬受到限制？習慣幕後隔絕的漢人文化。漢人特地把打耳祭的抓豬活動拿來說嘴，就是故意挑剔的行為！

紀曉君在臉書砲轟：「我們原住民的祭典不該被保留，很野蠻？那你們供神豬的就是文化？豬塞餵成那樣然後殺了供祭所以是高尚的哦？」到底是做出別的文明所期盼的行為？還是遵循自我文明的規則發展下來？身為一個文明成長下的人，要求別的文明長成什麼樣子就是一種傲慢！

近乎病態的愛護動物 是否是崇洋媚外、為了向西方世界 (ex. 綠色和平組織) 表示我們跟他們站在同一陣線、跟他們同樣等級，而產生之好似討好、尊崇國際制度的行動，為了表示我們與西方世界一樣進步文明而寧願拋棄自己的傳統也要高規格要求 愛護動物 ？

助教： 這些傳統慶典不再具有原住民社會連繫感情與文化傳承的意義，而變成可以被漢人社會消費的商品，當這個「豐年祭」或「射耳祭」的商品形象因為「過度野蠻、血腥」，不符合漢人的文明價值(也就是失去賣相，沒辦法被消費時)我們就不再講「尊重原住民的多元文化」，而是要他們「取消抓豬比賽」。

其他地區的原住民

• 不同地區的原住民與其處境發展
  • 日本北海道愛奴人 (Ainu)
  • 美洲印第安人
  • 澳洲土著－失竊的一代 (Stolen Generations)
  • 紐西蘭毛利人

在各國也都有原住民的存在，即使是民族精神很強烈的日本人，也存在北海道的愛奴人，直到 1986 年前都否認他們的存在。藉由很多電影宣傳、強勢文明的歷史經歷，我們也才知道有美洲印第安人（分支馬雅、阿茲特克、印加文明）、澳洲土著、紐西蘭毛利人 … 等。到底怎麼樣才算是原住民？有人認為具有演化化石才算是原住民，那事實上很多文明化石存證相當困難，這樣就稱不上原住民了？

其他地區的原住民－愛奴人

• 日本北海道與俄羅斯境內皆存在
• 1869 年 (明治天皇) 「蝦夷地」更名「北海道」
• 1899 年「北海道舊土人保護法」──制度化歧視
• 1992 年 12 月聯合國集會
  日本政府：「享有自己的文化，實踐自己的宗教，以及使用自己的語言是被我國憲法所保障的每個人的權利。但在聯合國《人權規約》中規定意義的少數民族，在我國不存在。」
• 2008 年正式被列為日本原住民族

1869 年，愛奴人居住地被正式納入日本的行政範圍，同時被命名為習慣的「北海道」，被政府沒收的土地成了新住民的居地，逐漸地外來人口增加，使得愛奴人真的變成 “少數民族”。

隔了 30 年後，才制定對於它們的保護法，也與之前講的類似，制訂保護法等同於凸顯彼此之間的差異，是一種制度化歧視。再隔 100 年後，愛奴人在聯合國集會發表演說，要求制訂新法，但日本政府卻採用 “我國憲法” 保障每個人的權利回絕，「我國」這一詞對於少數民族存在嗎？真的是同一國嗎？「我國」這一詞呈現甚麼樣的態度？

再中間過程中，日本政府雖然修訂保護法，但是落實情況並不理想，日本長時間以「單一民族國家」的姿態現身，純粹也許很重要，更是一個進步的文明象徵。在近 2008 年，才正式將愛奴人為「日本原住民族」任何人權保護、社會地位、民族文化等內容才受到保障。

仔細想想，我們漢人對於台灣原住民的接觸與認知還不算晚。

其他地區的原住民－澳洲土著

• 「失竊的一代 (Stolen Generations) 」
• 1909 年至 1969 年年間（部份地方持續至 1970 年代）實行之「同化政策」長達 60 年。
• 兒童被永久性地帶往白人家庭或政府機構「白化」自身語言和文化被剝奪。
• 1997 年總理 約翰‧霍華德 (John Winston Howard)：「這是上一代政府的錯」
• 2008 年 2 月 13 日，總理 陸克文(Kevin Michael Rudd) 在澳洲國會上正式道歉，承諾改善原住民 生活水平 ，提高 識字率 、平均壽命 … 等。

而澳洲土著的情況也類似，長達 60 年的同化政策，認為他們「低賤無知」及「將會消失」，必須同化，將原住民兒童永久性帶到白人家庭下照顧，迫使它們忘記原本的語言與文化。到了 1997 年時，以「這是上一代政府的錯」為理由拒絕道歉，再隔 10 年，才正式向原住民道歉。並且承諾改善當今原住民的 生活水平 。

所謂的 生活水平 又是用什麼方式？從發言的原文中看到，任何在政府機構、兒童照料的資源的提升，真的是得以求償了嗎？這一點值得省思。原住民有要求 平等 嗎？而平等的方式是用補償與另一個文明站在同一起點？

結語

• 「原住民的問題其實是 新住民 的問題」
• 「當沒有原住民問題時，就是沒原住民詞的時候」

「原住民的問題其實是新住民的問題」也許只是先來後到的概念，但也絕非這麼簡單，之前海協會長來台參訪時，說「中華民族同根」，原住民鬧出一句話「我們是南島語系的，誰跟你中華民族同一根，我這根跟你那根又不一樣！亂扯！」不同根的幽默言論。新住民相較於原住民晚到，因為彼此之間的文化差異，必須用原住民、新住民區隔開來，為什麼要區隔？一種認同感的需要，但這種差異性不應講究高下之分，也不該視為一個問題。

當初國民政府對山地同胞的「不視為問題所在」，最理想的方式，當然是不視為問題，並作為公民的一份子，相互協調之間的關係、經濟、資源分配。但現實中是很難達成的目標，假使一個人具有多重身分、國籍時，這顯然會有些問題，認同感應放置哪一方？即使只有單一身分的原住民，彼此之間仍有地位之差等差異，而受到不同的對待。

當我們不去討論原住民問題時，回過頭來看的就是彼此之間的階級、其他差異問題，當遇到一個更嚴重的問題時，很容易將破碎細小的差異忽略而靠攏在一起，反之當問題消失時，則因之前的靠攏引起衝突，因衝突而分化。因果關係難分難解。

報告心得

公平、正義、資本、中國

這次報告的困難度之高，感謝陳思瑀助教的指導。這份報告在兩三度討論完全被推翻重來，其一論點的背景知識不足，其二缺少足夠的批判立論，其三論點偏頗不全。本組沒有此類型的專業，以多數理工人，使用習慣的二分法在此報告相當危險。

無論如何，這篇報告應照著 Huntington 和 Elias 的論調下去觀察較為妥當。不乏會缺少多方的歷史評論，而從現代批評的歷史逆推。最後淪為心得報告。

如果單純拿別人的資料來報告，缺少自我的評論或獨特的闡述觀點，這隨處可得的資料，也不用上台報告。

日劇破案天才切利略－「事出必有因」，正是面對自己不熟識的事物時，採用的第一態度，當然根據自己的價值觀所產生的評論只好先往內心世界藏了。

中間還有談到人情網路的重要性，看人臉色的內心世界的建造，比起一學期的通識小組報告，顧及四年的人情網路的系上活動更為重要不是。而且，要求不同系的同學一起來做報告，這種要求別的文明做出我們文明所期盼的行為，就是一種傲慢。

Chapter 13

Design Theory for Relational Databases

名詞定義

• Functional Dependencies

  • 定義
    X -> Y is an assertion about a relation R that whenever two tuples of R agree on all the attributes of X , then they must also agree on all attributes in set Y .
  • 特性
    • X->A₁A₂ … A_n holds for R exactly when each of X->A₁, X->A₂,…, X->A_n hold for R.
      例子 Drinkers(name, addr, beersLiked, manf, favBeer)
      FD : name -> addr favBeer & beersLiked -> manf
      name -> addr favBeer = name -> addr and name -> favBeer .

• Keys of Relations
  換句話說 superkey 可能是複合的好幾個 key 構成，因此 key 一定也是 superkey，不論 superkey 或者是 key 都可以決定所有的 attribute。特別注意，key 是最小單位，因此 key 的子集不會是 key。

  • superkey
    K is a superkey for relation R if K functionally determines all of R.
  • key
    K is a key for R if K is a superkey, but no proper subset of K is a superkey.
  • 例子 Drinkers(name, addr, beersLiked, manf, favBeer)
    FD : name -> addr favBeer & beersLiked -> manf
    得到 {name, beersLiked} 是一個 superkey，發現 {name} 和 {beersLiked} 不是 superkey，得到 {name, beersLiked} 是一個 key。

• Inference Test
  如何找到 inferring FD？所謂的 inferring FD 就是藉由遞移關係得到的 FD，可以由原本集合中的幾個 FD 推斷出來，因此這些 inferring FD 不是必要存在的。那就先把 Y -> B 移除，再由剩下的 FD 組合，查看是否存在可以推論出 B 的可能，如果任何情況都推不出 B，則 Y -> B 不是 inferring FD。
  We are given FD’s X1 -> A1, X2 -> A2,…, Xn -> An , and we want to know whether an FD Y -> B must hold in any relation that satisfies the given FD’s.
  例子 If A -> B and B -> C hold, surely A -> C.

• Closure Test
  遞移閉包測試。
  An easier way to test is to compute the closure of Y , denoted Y+ .

  • Basis: Y+ = Y.
  • Induction: Look for an FD’s left side X that is a subset of the current Y+ . If the FD is X -> A, add A to Y+ .

Relational Schema Design

schema design 目標是避免異常、冗餘。

Goal of relational schema design is to avoid anomalies and redundancy.

• Update anomaly :
  更新異常，當一個事實改變時，只會發生一次修改，而不會發生很多次的修改。意即針對一個關聯屬性修改，最多更動一個 row (entity)，不會更動數行的 row。
  one occurrence of a fact is changed, but not all occurrences.

• Deletion anomaly :
  刪除異常，當一個 row 移除時，確定合法的事實被移除。如果發生關聯上屬性移除，但該屬性本應該存在，卻遭到移除而不存在資料庫中，就這麼地憑空消失。
  valid fact is lost when a tuple is deleted.

• Boyce-Codd Normal Form
  無論怎麼找 FD，都會發現到 FD 的 left hand side X 都是 superkey，那麼 R 就是一個 BCNF 。
  We say a relation R is in BCNF if whenever X ->Y is a nontrivial FD that holds in R, X is a superkey.

  • nontrivial means Y is not contained in X.
  • a superkey is any superset of a key (not necessarily a proper superset).
  • 例子 Drinkers(name, addr, beersLiked, manf, favBeer)
    FD : name -> addr favBeer & beersLiked -> manf
    In each FD, the left side is not a superkey. Shows Drinkers is not in BCNF.

• Decomposition into BCNF

1
2
3
4
5
6
7

BCNF_Decompose(R, FD)
	find X s.t.: X != (X+) != [all attributes] // X is one of FD's left hand side
	if (not found) then “R is in BCNF”
	let Y = (X+) - X
	let Z = [all attributes] - (X+)
	decompose R into R1(X union Y) and R2(X union Z) 
	continue to decompose recursively R1 and R2

Third Normal Form

接續上面的 Decomposition，將會產生一些問題。拆分上不合乎常理，發生過度的拆分，這問題發生在於給定的 FD 格式。

舉個例子 (street address, city, zip code)

• FD : AB -> C and C -> B.
  Example: A = street address, B = city, C = zip code.
• There are two keys, {A, B} and {A, C} .
• C -> B is a BCNF violation, so we must decompose into AC, BC.
• 顯然地 AC 有很嚴重的問題，既不存在 A -> C 也不存在 C -> A。

避免此問題

• An attribute is prime if it is a member of any key. 也就是 attribute 是某一 key 的 subset。
• X -> A violates 3NF if and only if X is not a superkey, and also A is not prime.

接續上個例子 (street address, city, zip code)

• There are two keys, {A, B} and {A, C} .
• Thus A, B, and C are each prime.
• Although C -> B violates BCNF, it does not violate 3NF.

properties of a decomposition

最後，來看看得到的 3NF 和 BCNF 給予什麼特性？

There are two important properties of a decomposition:

• Lossless Join :
  it should be possible to project the original relations onto the decomposed schema, and then reconstruct the original.
• Dependency Preservation :
  it should be possible to check in the projected relations whether all the given FD’s are satisfied.

資料不失真，保證可以藉由投影、Join 將分解的 schema 組合成原本的資料。同時所有的相依關係仍然保留，可以把原本 FD 都滿足所有的 schema。

Chapter 12

E/R Model

Entity-Relationship Model 實體關係模型

The E/R model allows us to sketch database schema designs.

協助描繪資料庫 schema 設計，藉由 E/R model 映射到資料庫的 Relation model。

名詞定義

• Entity = “thing” or object.
  實體，對應到現實生活中的名詞，例如蘋果 mac2013、微軟 win8、 … 等。單指一個、一件實體存在。
• Entity set = collection of similar entities.
  很多類似的實體產生的集合，例如計算機、員工 … 等實體集合。
  Similar to a class in object-oriented languages.
• Attribute = property of (the entities of) an entity set.
  屬性，通常是一個數值的呈現，例如計算機的運算能力、員工薪資、 … 等。
  Attributes are simple values, e.g. integers or character strings, not structs, sets, etc.

繪製 E/R Diagrams 時，呈現方式

• Entity set = rectangle.
  實體集合使用矩形圖表示
• Attribute = oval,
  屬性使用橢圓表示，並且連到實體集合，表示這些實體集合都具有這些屬性特徵。
  with a line to the rectangle representing its entity set.

• Relationships = diamond.
  用菱形連接兩個以上的實體集合，表示實體集合之間的關係。
  A relationship connects two or more entity sets, with lines to each of the entity sets involved.

• Relationship Set
  The “value” of a relationship is a relationship set, a set of tuples with one component for each related entity set.
  For the relationship Sells , we might have a relationship set like:

• Multiway Relationships
  Our three binary relationships Likes , Sells , and Frequents do not allow us to make this distinction.

• Rounded arrow = “exactly one,”
  實心箭頭表示確切對應一個關係，如果一個人會喜愛好幾種酒，其中最愛某一種。
  i.e., each entity of the first set is related to exactly one entity of the target set.

• Roles
  Label the edges between the relationship and the entity set with names called roles.
  例如丈夫、妻子之間的關係、夥伴之間的關係。

• Subclass = special case = fewer entities = more properties.
  從物件導向來說，一個繼承關係，得到的 Subclass 會繼承原本的 Class 的特徵、關係，有可能會具有額外的特徵。
  Let us suppose that in addition to all the properties (attributes and relationships) of beers, ales also have the attribute color . Isa triangles ( is a 的三角形) indicate the subclass relationship. Point to the superclass (指向父類別).

  • 比較 OO 和 E/R 對 subclass 的定義
    也就是說，OO 只會用 is a 描述一個 subclass 的繼承關係。但在 E/R model 中，isa 相當一個欄位，用來描述它是哪一個子類別，也就是說在紀錄時，如果它在某一個子類別時，那麼在父類別中也會記錄到它。
    • In OO, objects are in one class only. Subclasses inherit from superclasses.
    • In contrast, E/R entities have representatives in all subclasses to which they belong.
      • Rule : if entity e is represented in a subclass, then e is represented in the superclass (and recursively up the tree).

• Key
  Key 是一個 attribute 的集合構成，得到 f(Key) = at most one entity 。繪製時，使用底線 (underline) 於作為 key attribute 表示。
  is a set of attributes for one entity set such that no two entities in this set agree on all the attributes of the key.

• Weak Entity Sets
  為了去辨識某個實體，必須倚靠一對一、或者多對一的關係，來確切地找到某個實體。
  Entity set E is said to be weak if in order to identify entities of E uniquely, we need to follow one or more many-one relationships from E and include the key of the related entities from the connected entity sets.

  • 例如 Player(name, nubmer) - Plays_on -> Team(name)。當知道 Team 是哪一個時，才能辨識出 Player，否則名稱跟號碼可能會在不同隊中出現重複的。因此 Player 就是一個 Weak Entity Sets 。

• Weak Entity-Set Rules
  A weak entity set has one or more many-one relationships to other (supporting) entity sets.
  並不是每一個 relationship 都是 weak entity set 需要的支持。然而被需要的 relationship 必然擁有一個 rounded arrow 。
  The key for a weak entity set is its own underlined attributes and the keys for the supporting entity sets.
  例如在之前的例子，可以使用 (player) number 和 (team) name 作為 Player 的 key。

Design Techniques

• Design Techniques
  • Avoid redundancy.
    避免冗餘
  • Limit the use of weak entity sets.
    限制 weak entity set 的使用
  • Don’t use an entity set when an attribute will do.
    如果能使用一個 attribute 表示，則無需增加一個 entity set 單獨表示一個 attribute。

分別對應以下幾點。

• Redundancy = saying the same thing in two (or more) different ways
  存在用好幾種方法說一件事情，或者提及某個屬性。

• Entity Sets Versus Attributes
  對應實體集合的屬性，要符合以下兩點，屬性應為很多實體共同擁有的名稱，並且擁有至少一個 nokey 屬性，或者屬於 many-one 或 many-many 關係中，many 那一方的 entity set。
  An entity set should satisfy at least one of the following conditions:

  • It is more than the name of something; it has at least one nonkey attribute. or
  • It is the “many” in a many-one or many-many relationship

• Weak Entity Sets 使用須知

  • 避免濫用，通常能夠創建一個 unique ID 來表示一個實體。
  • 當真的找不到一個普遍性的 unique ID 時，才會逼不得已使用 Weak entity set.

From E/R Diagrams to Relations

關於對應的名詞如下，轉換時找 attribute 時，E/R Diagrams 中的 relationships 也會成為一個 relation ，attribute 的找法，可以從關聯的 entity set 的 key 或者是關係的定義本身。

• Entity set -> relation.
• Attributes -> attributes.

• Relationships -> relations whose attributes are only:

  • The keys of the connected entity sets.
    將相連的實體集合的 key 值都拿來作為 attribute。
  • Attributes of the relationship itself.

• Combining Relations
  結合 Relation，減少 Relation 的個數，將多對一的 relationships 表單，而實體集合屬於 many 的那一方，則可以把 one 那一方結合在一起。切記一定要是多對一，如果是多對多則會造成冗餘發生。

  • The relation for an entity-set E
  • The relations for many-one relationships of which E is the “many.”
  • Example: Drinkers(name, addr) and Favorite(drinker, beer) combine to make Drinker1(name, addr, favBeer).

• Handling Weak Entity Sets
  解決 weak entity set 轉化成 relation 時，必然要為它準備一個 complete key 來辨識不同實體於關連到不同的實體集合。如果一個 supporting relationship 不具有 attribute，而且屬於一個冗餘的紀錄，那麼把 relationship 另一方 “one” 的 entity set 的 key 值加入到 weak entity set 所創建的 relation。
  從之前的例子，把球隊名稱 team(name) 加入到 Player(number, name) 中，變成 relation Player(number, team_name, name)，這是在之前的 Combining Relations 中，就已經得到的結果，因此就可以忽略。

  • Relation for a weak entity set must include attributes for its complete key (including those belonging to other entity sets), as well as its own, nonkey attributes.
  • A supporting relationship is redundant and yields no relation (unless it has attributes).

• Subclasses: Three Approaches

  • Object-oriented : One relation per subset of subclasses, with all relevant attributes.
    父類別和子類別分開，各自成為一個 relation。
  • Use nulls : One relation; entities have NULL in attributes that don’t belong to them.
    把子類別的屬性上提，如果父類別不存在該屬性則填入 null。
  • E/R style : One relation for each subclass:
    存在父類別和子類別的 relation，但是共同屬性都會在父類別中，子類別只保留 key 和新增加的屬性。
    • Key attribute(s).
    • Attributes of that subclass.

Problem

stackoverflow : Decomposing a relation into BCNF.

資料庫講到正規化，針對 1NF, 2NF, 3NF 的做法。正規化的目的
－要避免資料重複或相互矛盾的情形，並使資料庫在使用時能更有效率、更容易維護。

關於 1NF, 2NF, 3NF 的細節操作就上網查吧。也就是在還沒正規化前，可能會遭遇到

• 修改一個 f(x) = y 值時，可能修改非常大量的 row，因為有可能 f(x, z) = y，無用相依關係的 z 很多。
• 刪除某個元素時，造成 y 值沒有被任何相依，導致 y 的資訊無法存入資料庫。 … 如此類推。

現在給定 relation 和 functional dependencies，正規化它們！

舉個例子：(直接從 stackoverflow 的例子來說)

• Relation : R(A, C, B, D, E)
• Functional dependencies (FD): A -> B, C -> D

Functional dependencies 簡單來說就是一個決定性的一對多、或者是一對一的相依關係，可以根據 LHS (left hand side) 決策 RHS (right hand side)，當然 function dependencies 的訊息只有部分，也暗示著具有遞移關係。因此例如 A->B, B->C 則可以推論出 A->C 。

定義 X+ 為 X 的遞移閉包，因此假設知道 A->B, B->C 則 {A}+ = {A, B, C} ，假設知道 AB->C 則 {A, B}+ = {A, B, C}

回到例子，每一步要找到違反 BCNF 規則 (violates BCNF) 的 R’ 進行拆分。怎麼樣才算違反 BCNF 規則？可以找到一個 X != X+ != [R’ all attributes] ，就可以對 R’ 進行拆分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Step 1:
S = {ABCDE}       
	R' = ABCDE, 
	find {A} != {A, B} != {A, B, C, D, E}, 
	R1 = (X+) = {A, B}
	R2 = R' - ((X+) - X) = {A, C, D, E}
Step 2:
S = {ACDE, AB}
	R' = ACDE,
	find {C} != {C, D} != {A, C, D, E}, 
	R1 = (X+) = {C, D}
	R2 = R' - ((X+) - X) = {A, C, E}
Step 3:
S = {ACE, AB, CD}
	// NOT FOUND END.

在程式實作 (非人工) 的時候，如何找到 X 滿足上述的條件很重要，由於 X 是所有變數的 subset 情況，相當於 O(2ⁿ) ，很多項目是無用的。假如 R’ = ABE ，針對 X = AC 是無效的操作，基本上只要拿所有 function dependencies 的 X = LHS 進行測試即可？這貪心的做法應該是對的。

1
2
3
4
5
6
7

BCNF_Decompose(R)
	find X s.t.: X != (X+) != [all attributes]
	if (not found) then “R is in BCNF”
	let Y = (X+) - X
	let Z = [all attributes] - (X+)
	decompose R into R1(X union Y) and R2(X union Z) 
	continue to decompose recursively R1 and R2

說真的，老師上課講的練習答案還有錯，講算法時也不夠確切，真不知道教授怎麼教的，還是我沒認真上課。當教授發現全班答題有極端的相似錯誤時，到底是我們學不好？還是他沒教好？教授一點都不會反思。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5 2
A->B
C->D
6 3
AC->B
C->D
A->EF
6 6
AB->C
BC->AD
D->E
CF->B
BC->A
BC->D 
5 3
AB->C
DE->C
B->E

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

A->B
S = {AB, ACDE}
C->D
S = {AB, CD, ACE}
  
C->D
S = {CD, ABCEF}
A->EF
S = {ABC, CD, AEF}
  
AB->C
S = {ABCDE, ABF}
D->E
S = {ABCD, DE, ABF}
  
AB->C
S = {ABD, ABCE}
B->E
S = {ABC, ABD, BE}

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <assert.h>
using namespace std;
#define INF 0x3f3f3f3f
// stackoverflow Database: Decomposing a relation into BCNF
void parsingStmt(string s, string &l, string &r) {
    size_t pos = s.find("->");
    l = s.substr(0, pos);
    r = s.substr(pos + 2);
}
int toBitmask(string s) {
    int ret = 0;
    for (int i = 0; i < s.length(); i++) {
        assert(s[i] >= 'A' && s[i] <= 'Z');
        ret |= 1<<(s[i] - 'A');
    }
    return ret;
}
void printBitmask(int state) {
    for (int i = 0; (1<<i) <= state; i++) {
        if ((state>>i)&1)
            putchar(i + 'A');
    }
}
vector<int> LHS, RHS;
int findFD(int i) {
    int ss = i;
    for (int j = 0; j < LHS.size(); j++) {
        if ((LHS[j]&i) == LHS[j])
            ss |= RHS[j];
    }
    if (ss != i)
    	return findFD(ss);
    return ss;
}
vector<int> decomposing(vector<int> state, int fdlhs, int fdrhs) {
    vector<int> ret;
    for (int i = 0; i < state.size(); i++) { // X->Y
        int X = fdlhs, Y = fdrhs&state[i];
        if (Y != state[i] && (X&state[i]) == X && Y && X && X != Y) {
            ret.push_back(state[i]^X^Y);
            ret.push_back(Y);
        } else {
            ret.push_back(state[i]);
        }
    }
    sort(ret.begin(), ret.end());
    ret.resize(unique(ret.begin(), ret.end()) - ret.begin());
    return ret;
}
void printResult(vector<int> &ret) {
    printf("S = {");
    for (int i = 0; i < ret.size(); i++) {
        printBitmask(ret[i]);
        if (i != ret.size() - 1) {
            printf(", ");
        }
    }
    puts("}");
}
int main() {
    int n, m;
    string s;
    while (cin >> n >> m) {
        LHS.clear(), RHS.clear();
        for (int i = 0; i < m; i++) {
            cin >> s;
            string lhs, rhs;
            parsingStmt(s, lhs, rhs);
            LHS.push_back(toBitmask(lhs));
            RHS.push_back(toBitmask(rhs));
        }
        vector<int> ret;
        int update = 0;
        ret.push_back((1<<n) - 1);
        do {
            update = (int) ret.size();
            for (int i = 0; i < m; i++) {
                ret = decomposing(ret, LHS[i], findFD(LHS[i]));
                if (ret.size() > update) {	
					printBitmask(LHS[i]);
	            	printf("->");
	            	printBitmask(RHS[i]);
	            	puts("");
	                printResult(ret);
                	break;
                }            
            }
            update = ret.size() > update;
        } while (update);
    }
    return 0;
}

Chapter 10

10.1

In Section 10.1 we solved the problem of finding all horizontal line segments in a set that intersect a vertical segment. For this we used an interval tree with priority search trees as associated structures. There is also an alternative approach. We can use a 1-dimensional range tree on the y-coordinate of the segments to determine those segments whose y-coordinate lies in the y-range of the query segment. The resulting segments cannot lie above or below the query segment, but they may lie completely to the left or to the right of it. We get those segments in O(logn) canonical subsets. For each of these subsets we use as an associated structure an interval tree on the x-coordinates to find the segments that actually intersect the query segment.

a. Give the algorithm in pseudocode.
b. Prove that the data structure correctly solves the queries.
c. What are the bounds for preprocessing time, storage, and query time of this structure? Prove your answers.

給 n 個水平線段，詢問垂直的線段與那些水平線段有相交，輸出所有有相交的線段。

a. Algorithm:

1. 對 n 個線段建造 interval tree，使用課本上 CONSTRUCTINTERVALTREE(l) 的做法。
2. 對 interval tree 上每一個 node 建造 Priority Search Tree，node 依照 x 劃分，分別對 node.x 的左右兩側建造 PST，距離 node.x 越遠的端點，其優先權越高，左右子樹依照 y-value 分兩堆。
3. 詢問調用 QUERYINTERVALTREE(v, qx)，得到相對應的 ndoe 後，查找每個 node 下的 Priority Search tree 與線段相交，調用 QUERYPRIOSEARCHTREE()。

b. Prove that the data structure correctly solves the queries.
上述的作法與 axis-parallel rectangular query window 相同。而此問題的詢問是 axis-parallel rectangular query window 的 subset，一個線段的詢問是 qx = qx’ 的情況，故得證。

c. What are the bounds for preprocessing time, storage, and query time of this structure? Prove your answers.

preprocessing time : O(n log n)
store space : O(n)
query time : O(log n + k)

前處理因 interval tree 最慘 T(n) = 2 T(n/2) + O(n) ，建造 PST 只需要 O(n) ，每個線段最多在兩個 PST 中，得到記憶體空間最多為 O(n) 。詢問最多為 interval tree 的深度 O(log n)

10.2

Let P be a set of n points in the plane, sorted on y-coordinate. Show that, because P is sorted, a priority search tree of the points in P can be constructed in O(n) time.

類似 bottom0up heap construction，已知 bottom-up heap 可在 O(n) 時間內完成。

假設最後的樹高 H，第 i 次的 bottom-up 會調整 2^H-i 個元素，每個元素最多下降 i 層。則

雖然要求左右子樹的 y 值要符合左小、右大，但由於已經根據 y 排好，bottom-up 時，保證調整的 shiftdown 操作會符合其性質。

10.6

Let I be a set of intervals on the real line. We want to be able to count the number of intervals containing a query point in O(logn) time. Thus, the query time must be independent of the number of segments containing the query point.

a. Describe a data structure for this problem based on segment trees, which uses only O(n) storage. Analyze the preprocessing time, and the query time of the data structure.
b. Describe a data structure for this problem based on interval trees. You should replace the lists associated with the nodes of the interval tree with other structures. Analyze the amount of storage, preprocessing time, and the query time of the data structure.
c. Describe a data structure for this problem based on a simple binary search tree. Your structure should have O(n) storage and O(logn) query time. (Hence, segment trees are actually not needed to solve this problem efficiently.)

有 n 個 [l_i, r_i]，詢問一個點 x 被多少個區間包含，輸出為一個整數。

a. 使用 segment tree 儲存所有的 interval。

對於其 node(u) 會 cover(l, r) 的區間，紀錄有多少區間 cover(l, r)，最多有 2n 個葉節點，樹節點最多 4n 個，每個 node 只有一個額外的整樹紀錄區間個數。然而一個區間最多被拆分 O(log n) 個，依序插入需消耗共計 O(n log n) 時間。

preprocessing time : O(n log n)
query time : O(log n)
store space : O(n)

b. 使用 inteerval tree 處理 interval。

對於每個 node 分別對左右兩側建造平衡樹，這個平衡樹要支持某數字是第 k 大或第 k 小的操作。對於一個 node 而言，會有數個區間交 node.x，假設詢問點 qx 在 node.x 左側，則根據左側的平衡樹，查找 qx 是第 k 小，用以回報個數。每一個區間對多在 2 個平衡樹中，故空間複雜度為 O(n) 。

preprocessing time : O(n log n)
query time : O(log² n)
store space : O(n)

c. 使用 simple binary search tree。

1. 將 n 個線段的端點，共計 2n 個丟入 binary search tree。
2. 每一個 node 紀錄有多少個區間包含它，如果 node 是某個線段的右端點，則無視此區間的包含情況。
3. 對於每個詢問 qx，輸出 node = lower_bound(qx) 的包含結果。

將所有端點排序後，會得到 [a₀, a₁, a₂, …, a_2n]，每一個 node 的資訊是 [a_i, a_i+1) 的區間包含訊息。簡單地說，切成最小塊的相鄰資訊，與 segment tree 反過來的概念。

前處理使用 line sweep algorithm 掃描線算法，來找到每一個端點被多少個線段包含。掃描線算法需要 O(n log n) ，binary search tree 只需要 O(n) ，查找 lower_bound 只需要 O(log n) ，保證最多 2n 個端點，樹最多使用 O(n) 個空間。

preprocessing time : O(n log n + n) = O(n log n)
query time : O(log n)
store space : O(n)

10.7

a. We want to solve the following query problem: Given a set S of n disjoint line segments in the plane, determine those segments that intersect a vertical ray running from a point (qx,qy) vertically upwards to infinity. Describe a data structure for this problem that uses O(nlogn) storage and has a query time of O(logn+k), where k is the number of reported answers.
b. Now suppose we only want to report the first segment hit by the query ray. Describe a data structure for this problem with O(n) expected storage and O(logn) expected query time. Hint: Apply the locus approach

給定 n 個不相交的線段，詢問一點開始的射線，射線方向向 y 軸正向，輸出所有交到的線段。

a. 使用 segment tree，依照所有的端點的 x 值，接著對於每個 node 建造以 y 值得 binary search tree，儲存數個線段，因為不相交，保證 binary search tree 在 [xl, xr] 區間的所有線段都是單調的。每個線段最多切成 O(log n) ，故使用空間 O(n log n) ，詢問 O(log n + k) ，只須訪問 O(log n) 個節點，從 binary tree tree 最遠的開始往下輸出即可。

b. 只找第一個碰到的線段，使用 trapezoidal map 找到 point location，走訪 DG 其最後一個 segment below 的情況就是輸出結果。已知 trapezoidal map 在隨機增量算法中，expected size of search structure O(n) ，expected query time O(log n) 。

Chapter 11

11.1

In Chapter 1 we defined the convex hull of a set P of points as the intersection of all convex sets containing the points. In the current chapter we saw another definition: the convex hull of P is the set of all convex combinations of the points in P. Prove that these two definitions are equivalent, that is, prove that a point q is a convex combination of points in P if and only if q lies in every convex set containing P.

首先 convex combinations 指得是 $q = \sum_{i = 1}^{n} \lambda_{i} p_{i}, \lambda_{i} \geq 0, \sum_{i = 1}^{n} \lambda_{i} = 1$，證明 q 會在所有的凸包集中，也就是 q 點相當於任抓幾點出來，會在這幾點形成的凸包中，公式計算類似物理上的質心計算。

(=>) $q = \sum_{i = 1}^{n} \lambda_{i} p_{i}, \lambda_{i} \geq 0, \sum_{i = 1}^{n} \lambda_{i} = 1$. Prove q lies in every convex set containing P.

• Base :
  $n = 2, q = \lambda_{1} p_{1} + \lambda_{2} p_{2}$, q lies on segment p₁p₂, which must be a subset of every convex set containing p₁, p₂.
• Suppose:
  $n \le k$ 均成立，當 n = k + 1 時，$\lambda_{k+1} = 0$ 必定成立。
  $$\begin{align} & q = \lambda_{1} p_{1} + \lambda_{2} p_{2} + ... + \lambda_{k} p_{k} + \lambda_{k+1} p_{k+1} \\ & = (1 - \lambda_{k+1}) \left [ \frac{\lambda_{1}}{1 - \lambda_{k+1}} p_{1} + \frac{\lambda_{2}}{1 - \lambda_{k+1}} p_{2} + ... + \frac{\lambda_{k}}{1 - \lambda_{k+1}} p_{k} \right ] + \lambda_{k+1} p_{k+1} \\ & = (1 - \lambda_{k+1}) ({\lambda_{1}}' p_{1} + {\lambda_{2}}' p_{2} + ... + {\lambda_{k}}' p_{k}) + \lambda_{k+1} p_{k+1} \\ & \text{where } {\lambda_{i}}' = \frac{\lambda_{i}}{1 - \lambda_{k+1}}, \lambda_{1} + \lambda_{2} + ... + \lambda_{k} = 1 - \lambda_{k+1} \\ & \sum_{i = 1}^{k} {\lambda_{i}}' = \sum_{i = 1}^{k} \frac{\lambda_{i}}{1 - \lambda_{k+1}} = \frac{1}{1 - \lambda_{k+1}} \sum_{i = 1}^{k} \lambda{i} = 1 \end{align}$$
  Hence, the point ${q}' = \sum_{i=1}^{k} {\lambda_{i}}' p_{i}$ is convex combination of p₁, p₂, …, p_k, q’ lies every convex set containing the them.
  $$q = (1 - \lambda_{k+1}) {q}' + \lambda_{k+1} p_{k+1}$$
  every convex set containing p₁, p₂, …, p_k, q’. Since it also contains p_k+1 the set must contain q as a convex combination of two points.
  (<=) Prove q lies in every convex set containing P => $q = \sum_{i = 1}^{n} \lambda_{i} p_{i}, \lambda_{i} \geq 0, \sum_{i = 1}^{n} \lambda_{i} = 1$
  In particular, q lies in the smallest convex set, the convex hull of P. Triangulate the convex hull, q must lie in one of the triangles $\triangle p_{1} p_{2} p_{3}$. Connect q to p₁, p₂, p₃. This partitions the triangle into tree smaller ones.
  $$\left\{\begin{matrix} \triangle p_{1} p_{2} p_{3} = A \\ \triangle q p_{2} p_{3} = A_{1} \\ \triangle q p_{1} p_{3} = A_{2} \\ \triangle q p_{1} p_{2} = A_{3} \\ A = A_{1} + A_{2} + A_{3} \end{matrix}\right. \Rightarrow q = \frac{A_{1}}{A} p_{1} + \frac{A_{2}}{A} p_{2} + \frac{A_{3}}{A} p_{3}$$
  得證。

11.2

Prove that the worst case running time of algorithm CONVEXHULL is O(n3), and that there are sets of points where a bad choice of the random permutation makes the algorithm actually need Θ(n3) time.

CONVEXHULL 共有三層 for loop.

• LINE 7 如果每次的新加入的 p_i 都在 convex hull 外面，即 F_conflict(p_i) 非空。
• LINE 10 $e \in \pounds$，而最多有 i - 1 個，投影的情況下，最多 i 個點都在凸包上，因此最多產生 i - 1 個 facets。
• LINE 18 對每個新加入的 facets 最多增加 n - i 個 conflict 點。

故最慘 O(n³)。

11.6

Describe a data structure that allows you to test whether a query point q lies inside a convex polytope with n vertices in R3. (Hint: Use the results from Chapter 6.)

快速判斷一個點是否在 3D convex hull 中。

• 方案一：3D point location by 3D trapezoidal map. 感覺非常難做，弄出很多柱狀體。
• 方案二：convex hull 最多會有 3n - 6 個面，最多有 3n - 6 個面不等式，判斷是否全在同一側 O(n) 。
• 方案三：將做好的 3D convex hull，將所有點投影到 x-y 平面，每一個梯形區域會由 2 個 convex hull 的面覆蓋，要不沒有面。對於投影的 2D 建造 trapezoidal map。query 一個點 q 時，先投影到 x-y 平面，找到所在的梯形區域，針對兩面的不等式進行判斷。預處理 O(n log n) ，詢問 O(log n) 。

11.8

Describe a randomized incremental algorithm to compute the intersection of half-planes, and analyze its expected running time. Your algorithm should maintain the intersection of the current set of half-planes. To figure out where to insert a new half-plane, maintain a conflict graph between the vertices of the current intersection and the half-planes that are still to be inserted.

• 維護半平面 hi 與 Sj 的相交資訊。

• add half-place
  繞外部 (半平面的另一側的凸包邊) 的 edge e，將 h_conflict(e) 移除掉 intersection(e, h_conflict(e)) in $\bar{h_{i}}$。
  期望值的複雜度依賴中間過程中產生的交集點個數。

• 假設 c(H, h) 表示 inter(H) 和 h 的 conflict vertice 個數。
  則 $\sum_{i = 1}^{n} \left [ \frac{2}{i} \sum_{h \in S \setminus S_{i} }{c(H, h)} \right ]$－所有的花費。
  $$E[c(S_{i}, h_{i})] = \frac{1}{n-i} \sum_{h \in S \setminus S_{i} } c(S_{i}, h) \\ \Rightarrow \sum_{i = 1}^{n} \left ( \frac{2}{i} \sum_{h \in S \setminus S_{i} }{c(H, h)} \right ) = \sum_{i = 1}^{n} \left ( \frac{2}{i} \sum_{h \in S \setminus S_{i} }{E(S_{i}, h_{i-1})} \right ) \\ = \sum_{i = 1}^{n} \left ( \frac{2}{i} (n - i) E(S_{i}, h_{i-1}) \right ) = \sum_{i = 1}^{n} \left ( \frac{2(n-i)}{i} E[\text{# of vertices destroy ed at i+1}] \right )$$
  對於每一個 vertice v 被創建的時間為 tc(v), 被移除的時間 td(v)。
  $$\sum_{i = 1}^{n} \left ( \frac{2(n-i)}{i} E[\text{# of vertices destroy ed at i+1}] \right ) \\ = \sum_{v} \frac{2(n - td(v) + 1)}{td(v) - 1} \le \sum_{v} \frac{2(n - tc(v)) + 2}{tc(v)} \\ \le \sum_{n}^{i=1} \frac{2(n - i) + 2}{i} E[\left |v \mid tc(v) = i \right |] \\ = \sum_{n}^{i=1} \frac{2(n - i) + 2}{i} \times 2 = O(\sum_{n}^{i=1} \frac{n}{i} - 1) = O(n ln n)$$
  得證。

single value function 的意思？問問 劉寶鈞 老師 吧！

課程心得

強烈建議遠離 此課程，分析如下描述， 劉寶鈞 老師強烈建議把定義背得一模一樣，最好不要翻譯，因為很難達到一樣的水平，也很難說好。資料庫歷史悠久，因此歷史課程會持續一陣子，課程內容並沒有相當多的實務經驗。老師秉持著數年專業，保證嚴格批閱所有考卷。

如果沒人抱怨，我來說說這鬼畜的經歷，絕不能讓其消散。

期中考分析

保證題目描述與錯字 100% 複製考卷

1. 傳統檔案系統為何不能共享 而資料庫如何做到可以共享？(10 分)
   傳統檔案系統的資料存在各自的電腦中，而且格式不一，有相當大的重複資料，由於各自管理所需要的資料，更新時間也會不一致，因此在共享的支援相當不利，共享的結果不一定是最新、不能同時匹配在不同的電腦中的資料。
   資料庫系統將資料集中化管理，收集到同一個系統中，並且藉由 SQL 中的 DML 支持使用者進行共享資料的存取、檢索，由系統管理同一時間多名使用者對資料的存取。
   上述為零分作答，劉寶鈞老師說明若沒提到 SCHEME DATA 一律零分。

2. 以 Relation Model 為例 說明 Data Model 之三要素。(10 分)
   略說－有 資料表示法、資料的操作、約束條件，舉幾個例子便可完事。
   此題作答還算正常，但是沒有舉例子大致上會被扣到慘不忍睹。

3. 比較說明 DDL 及 DML。(10 分)
   略說－Data Definition Language、Data Manipulation Language，分別是定義資料庫、資料表用的，另一個是對使用者詢問、操作資料。
   此題作答還算正常，但是沒有舉例子大致上會被扣到慘不忍睹。

4. 何謂 3-value logic ？並證明 P OR (NOT P) = 1 在 2-value logic 是成立的，但在 3-value logic is not always true。(10 分)
   3-value logic 分別為 true, false, unknown。

在 2-value 中

在 3-value 中

用 0 表示 false, 1 表示 true, 1/2 表示 unknown，AND = MIN, OR = MAX, NOT = 1 - x。
=> P = 1/2, P OR (NOT P) = MAX(0.5, 1 - 0.5) = 0.5 = unknown。

unknown 不屬於 true，因此 3-value 在 P OR (NOT P) = 1 not always true。
以上作答零分，劉寶鈞老師在考卷上對 unknown 用紅筆寫了 What ? 一開始直接零分，之後才勉為其難拿到五分。投影片上面也這麼寫的，到底在 What ? 什麼勁，你自己拿出來講的東西上都這麼寫，寫下去分數還沒有？

1. 寫出若含 NULL value 五個 single value function 的規則。(10 分)
   WHAT the fuck about single value function ?
   略列表 AND OR NOT EQUAL PRODUCT 的幾種情況。
   上述為零分作答，劉寶鈞老師說明 single value function 的要寫出 aggregate function。我問老師「為什麼不直接寫 aggregate function？」老師回答道「就是故意不這麼寫。」

2. 寫出 SQL query 之 SELECT, FROM, WHERE, GROUP BY, HAVING 之義意。(10 分)
   錯字直接按表抄，這一題原本對於 HAVING 的解釋不夠完善，掛掉直接只剩下五分。WTF，五個定義錯一個就直接砍一半分數？對於 HAVING 只有寫提供 WHERE 無法進行 aggregation function 的判斷條件，必須與 GROUP BY 一起使用。這樣難道錯了嗎？GROUP BY 都解釋了，你還說我錯？

結語

我不是肚子裡的肥蟲，一定是我蠢得無可救藥，拿了不及格的成績？

很久沒有衝動想要殺人，這下子又開始想殺人。

助教不替老師改考卷，讓老師這樣改考卷行嗎？

我是個壞學生，這門課真的氣死人，出口罵髒話根本不足以洩憤。

主題－攻擊欲的轉變

不知何時開始，人們對於暴力行為開始無法容忍，逐漸地喪失對於暴力的經驗。曾經也打過架，恨不得把對方殺了，即使捶得再大力也弄不出傷口來，也許被馴化的怒火無法傷害任何人，只剩下精神上的威嚇。拿刀殺人的場景不是在電視情節中，就只能在夢裡、幻想裡去想這些。

同類相互攻擊在大自然中常見不過的事，為什麼在人類身上卻逐漸消失？沒錯！因為我們有穿越好幾世代的外部記憶體－文化。

攻擊欲

曾經的人們為了生活，長久時間的定居，明天在哪都不曉得。只要一戰爭，贏了高興，輸了什麼都沒，生命就是這麼地短暫，中古世紀曾有一段話「看見死亡才能安心、吃得好、睡得好」那是在什麼樣的生存條件下，活著不是殺死對方，又是被殺、被壓迫的日子。面對死亡才能安心，這才是真正的活著！「 未知死，焉知生 」古人說得有道理。

為什麼至今仍有黑道白道之分？當白道無法解決的事情，黑道顯得更有威震力，看看「日本黑道山口組」在許多電影情節中，黑道的存在反而凸顯了到底是傾聽社會聲音做事？還是聽從自己的本能。社會給予的牢籠，促使我們不做暴力的行為，隱藏自己的情感，然而這些情感去哪了？

沒有暴力的行為，如何表示自己的不滿？敵意？產生出的無力感、關係冷漠、義憤，用另外一種方式宣洩自己的攻擊欲，「 如果這些世界不接受我，那就摧毀這個世界吧！ 」沒了直來直往的暴力世界，卻產生出兩個極端的世界，被壓抑著暴力的人們何時會爆發呢？

殘暴的必要性－對敵人寬厚，就是壯大對方，未來必有危害，「斬草不除根，春風吹又生」不殺行嗎？用仁慈看那個世界，你就是找死！然而現今的攻擊欲，單純的攻擊欲也傷不了任何人，用武器所需要的技術越來越高，沒有技術也殺不死人，這片高牆越來越高厚呢。

陽剛

起初所謂的陽剛只得是什麼？不正是那殘暴的事實嗎？現今看看那些陽剛的定義，早已經被陰柔化，受到捧吹的帥哥又是在古時的男人嗎？追求性別平等的代價，造成暴力的消失，如果還要展現自己的暴力，只能迂迴表達自己那一身的肌肉。

行刑

既然沒法殺人，公開行刑正是大眾娛樂，一個人被處刑，整座城市的人都在看，這是為什麼？在電影情節中，殺人的血腥畫面是否令人振奮？追求安心才是本能！

現在有很多不殺人的行刑，例如剝奪尊嚴，相當於利用羞恥感、價值觀的攻擊，文化的禁忌－身體的隱蔽性，這還不讓人精神崩潰嗎？讓一個人不成人形的方式很多，精神是如此地脆弱。

死亡

過去人們很難活長，活到三、四十歲就算有幸，也因為戰爭死亡相當常見，如果人們對死亡感到悲傷，豈不是沒辦法過生活？整年都要哭天喊地的，你能說他們無情嗎？不行，他們本應該這麼做，否則沒辦法前進。

古人很容易 認命 ，對於前途未卜的不安，明天還能活著嗎？戰爭就在那麼一夕之間開打，生計被土地綁著，想走也走不了。有一夜沒一夜的的恐懼，「 今宵有酒今宵醉 」死了就什麼都沒了，為何不現在享用？總是 盤算未來 ，那是你們現代人的奢侈。

血濃於水，資產階級興起後，家族之間的私鬥相當常見，衝突一來，不少家族因此滅絕。信得過的人只有血緣關係的人，不要說為何當官的都想找自己人，找不同處境的人，不怕在背後被人捅一刀嗎？(不論豬隊友)

活在當下，並非沒有遠見、逃避現實 ，誰知道明天在哪？那等絕望，你還有盤算未來的本錢嗎？

剝奪

如何表示對別人的不滿？當下只剩下視覺的攻擊，作為一個活在現代的人，動手動腳就已經輸一半，觸覺已被作為侵略他人身體的領域，嗅覺則不能作為認識人的方法 (因為那如野獸一樣)。

視覺已成為唯一攻擊欲的發揮。觀賞球類運動也是如此，作為球迷欣賞支持的隊伍侵略，但自己除了看，什麼事情都不能做，一旦做了就是不文明的舉動。

暴力遊戲會使得人暴力嗎？愚蠢的人們啊，在怎麼轉換情感，也不可能百分百的宣洩。

魅力化

論吸血鬼、狼人的暴力魅力化，腐女們準備好了嗎？

以下開放暴動。本文 … 略。

著重目標

即使 Unigram 效果已經相當不錯，基於人類日常對話的模式，絕非單詞相依無關，藉由好幾個連詞表示出不同的意思是常有的事情，探討 n-grams (n > 3) 對於當前的語意分類器的強化、優化。

已知問題

當 n-grams (n > 3) 時，語意的模糊性質會提高，可能同時把正反兩面的詞放置在一起，如此一來這一組的利用價值並不高，在計算分類上會將精準度稀釋，同時對於記憶體的負荷也會增加 (必須記錄各種組合，例如化學元素與化合物的數量大小關係)。

接著 n-grams 通常是用在英文處理精準度比較好，因為 單詞分明 (藉由空白隔開)，對於機器而言中文句子並不存在詞 (token)，都是一堆字元 (character)。

研究顯示： 漢字順序並不一定影響閱讀

請看下述文字－研究顯示：漢字序順並不定一影閱響讀。

對於中文自然語言處理，斷詞的重要性、語意處理上有額外的研究領域，在這裡暫時不談論這些。也許可以談談看不考慮順序的 n-grams，型態從 tuple 變成 dag。

分類器

分類器分成線上訓練、離線訓練，就已知得到目前 SVM 仍然在實務上的效果是最好的，在這裡不談論 SVM，一部分原因是 SVM 太慢。

下面是在不同領域的分類器構思，線上訓練、線性調整。大多數的分類器都必須定義特徵，對於每一個要分辨的項目是否存有這一個特徵 (boolean)，而在部分可允許模糊的模型，可以利用權重 (float) 表示特徵強弱。

類神經網路

Passive-Aggressive Algorithm

對於感知機的內容所知不多，每加入一筆結果，將劃分的依準疊加上預期的法向量，成為新的劃分依準線。大多依靠數學的微積分來完成，並非完全相信新加入的結果，因此會有一個計算的權重，來權衡影響的大小。

訓練流程：

自然語言

Language Modeling

就如上課內容所講的

用 Good Turing 的方式去 smoothing 那些從未在模型中出現的詞語，它們是有機會的，絕非是機率 0。

機器學習

Winnow algorithm

設定一個閥值作為是否存在此分類的依據，隨後根據閥值調整相關數據的參數大小。

簡單來說，當判斷錯誤時，將相關的 (它有的) 特徵係數權重調整，將其變大使得納入分類中、或者將其變小踢出分類中。

調和

為了加入 n-grams (n > 3) 的機制，必然要學習 忘記 、 無視 的才能，才能將垃圾訊息給捨去掉。同時也是降低記憶體的耗存的方法，這裡無法像人類有辦法根據時間將單詞組合抽象化，等到哪天 HTM 腦皮質學習算法 成功實作，相信在取捨上會更為流暢。

對於每一個特徵給予分數，保留前 K 好的特徵進行訓練，其餘特徵捨去，至於要保留的 K 大小將由實驗結果進行測試。

分數計算：

• A：同一分類下，該屬性使用的資料筆數
• B：在其他分類下，該屬性被使用的資料筆數
• C：同一分類下，該屬性不使用的資料筆數
• D：在其他分類下，該屬性不被使用的資料筆數
• t：屬性
• c：分類

結論

論文中提到，分別去了 50K、100K、200K 個分數高的 n-grams，又分別在 n = 3, 4, 5, 6 下進行測試，效果有那麼一點點地提升。

接著就是考驗我們期末 Project 要怎麼體現這篇論文的思路、擴充。

主題

跨國的文明競逐與衝突－原住民的文化問題

報告核心－文明的傲慢

「原住民」稱呼為何而來？

正因為我們是侵略者！他們才是 真‧台灣人 。

AcFun 線上看－《賽德克巴萊》

在評論中大陸人這麼說

• 「為什麼他們不說國語？」
• 「一隻豬發生的血案？」
• 「他們才是真台灣人啊。」

要求弱勢族群做出相同的行為－那就是一種 傲慢 。

文化差異

漢人文化需要競爭，做任何事情都需要競爭，而原住民只要在工作上能夠溫飽就能快樂過活，藉由唱歌舞蹈等表現方式來闡述他們的快樂，及時行樂整是他們的天性，說他們懶惰不上進才是我們的傲慢。相較於競爭，他們是互助合作的生命共同體，在那種生存環境下，農耕、狩獵都要互相幫忙，你說競爭下的快樂帶給多少回饋？

如何表現自己的英勇事蹟？奮勇殺敵、狩獵得到的 骸骨 作為一個能力階層。即使如此，敬老尊賢是重要的文化，年齡階層而非能力階層。做為一個活在漢人社會的人而言，能力若決定一生，而談快樂？雖然能力不如人，難道就培養不出比自己厲害的人？也許虎媽就是這麼來的。

佩刀難道錯了嗎？佩刀是因為生活所需，也是我們地位的象徵。憑什麼要求不能帶刀，那你們帶刀又是什麼意思，相比中古世紀騎士可以制裁的對象，低層社會人們只能對自己以下的對象進行攻擊。

融入現代社會

• 第一階段－原住民成年人
  從成年人開始步入社會，雖然一開始會接受很殘酷的生活適應，還必須使用 漢姓 ，論名字對自尊的重要性，即使謀求到工作，並且逐漸適應生活所需。(有多少人能失去自己的名字？)
• 第二階段－孩子教育
  由於長時間活在漢人社會，孩子學習也就必須上小學，然而文化的成長背景不同下，做為父母能教導什麼給孩子？就因為環境不同，知識理解的差異所引來歧視，難道就是錯的嗎？
• 第三階段－傳統繼承
  村落沒有新血、沒有傳承，不就是鼓勵他們進入漢人社會的原因嗎？

什麼樣背景的人用什麼方式學，不是比較好理解嗎？學習成績不好沒什麼好擔心，只是規格面向不同。不懂不是問題，只是要換的方式。

保有精神

我們的信仰、精神，藉由血緣牽連在一起。

矛盾所在

• 用很多補償條款鼓勵原住民進入我們漢人社會，但又希望他們保有他們自己的文化？

鼓勵改變，但卻又希望不變？(你們這群人到底想怎樣！)

• 武力較強的文明使得我們成功掠奪這塊土地，而這種文明真的是文明嗎？難道不就是個野蠻人？
• 想想印地安原住民的文化，真的是所謂低於來自被歐洲驅逐的人們所擁有的嗎？
• 如果你們所說小七是文明的象徵？想要成為你們所說的文明文化有錯嗎？

反問小朋友：「沒有漢堡和薯條，你們都吃什麼？」小朋友答說，就吃海裡抓的九孔和龍蝦。

• 文章中見到蘭嶼小孩吃山珍海味，那豈不是反了？依照生活的飲食水準，到底是誰過得奢侈？

世界原住民

當年英國統治的殖民地眾多，要不是他們可以退回祖國，那群人也是相當龐大的原住民。然而我們仗著人數眾多，無法退出的處境，厚臉皮地活在這片土地。不是中國對待少數民族的方式，他們在同一個文化脈絡下分支成長，即使不能理解，也能知道自己是同一脈人，已經磨得相當長久的時間。

縱使看著別國對待本國原住民的方式，例如：規劃保護區、歸還土地… 等，同時也表明了曾經使用過的暴力，他們的處境與我們台灣不同，他們有原本的家可以回，而我們必須對抗其他國家的勢力，必須與原住民站在同一條船上，也許對待他們的方式相比別國來說殘酷，一旦我們的立場被別國 (如中國，他們又會怎麼對待原住民？) 取代，那到底是誰殘酷？

被消費的文化

文明化造就觀光行為

觀光是大多數人的娛樂，也因此造就服務業的產生。談談服務業與文明化的關係

這個新的公民身分的尊貴性，首先意味著華人社會本來以長幼輩分及遠近
親疏為基礎的傳統人際關係階序必須被鬆動，好讓尊貴的自豪自信得以越過這
些差異位置所包含的舉止規範和情感限制，而成為所有主體都可以近用的現代
情感特質。在這方面，第一個重要的結構性發展就是台灣產業結構劇變後的服
務業人際互動模式，以及隨之在日常生活中不斷重複的互動消費實踐，它們都
使得新規訓不再只是外加的強制和要求，而得以徹底融入主體的生活活動與內
在自我情感。

這深入探討可能要問一下何春蕤老師，總之身處服務業的情感，肯定是原住民們所無法理解的，一開始覺得他們好客，不知不覺地商業化他們，直到他們的好心被利用，才逐漸地被厭惡。

反思

當我們對外說出「我們台灣人」到底是指那些人？是活在這片土地上的所有人？那接下來的話就是共同意識嗎？正因為要對外證明我們是個國，才急切地想要讓所有活在這片土地上的人，至少有一個共同意志？

我們用更殘酷的方式生存，剝奪那些活在幕後的人的生存條件與資源，真的有比原住民文明嗎？追求文明結果，竟是雙面刃？

探討

在各國文化的核心目標不同時，它們對待原住民的方式也有所不同，到底是給予相同地位？還是給予空間適性發展？我想這牽涉到－到底有沒有必要活在「社會」牢籠，他們明明不用看處在強勢文化人們的臉色，自給自足活得很好，為何他們要踏入我們的文化？

也許以前原住民的人數與文化有關係，為了生存不得不離開原本的文化，背負著必須學習更多文化知識的壓力。這種不對稱的學習，真的造就我們欺壓原住民了嗎？

文化模式與人口承載量

造成必要的出走的主因。根據人口普查統計，至今原住民已經從日治時代的七萬多人暴增到五十多萬人，它們的生活習性支撐這麼多人嗎？

看待偏見

偏見有時也是一種讚美 。即使是你所認為不文明的舉動，不就是正因為做了你做不到的事情？

文化分工

唱歌、表演真的是唯一生存之道？原住民未來若要發展特色，難道唱歌表演就是唯一了嗎？在很多原住民歌手的興起下，就只能朝著同一個方向嗎？

學校教育

窮鄉僻壤的村落，書上這麼多內容壓根沒見過，為何而學？遵守什麼規矩？

補償條例

一個跨世代的心態，但要知道強勢文化下也有弱勢成員，而生存的價值是因為他們的需求而存在，有時給予環境正表示處於文明的鑑賞期。

生活教育

生活就是最好的教育，有人走得出去，也一定會有人走不出去，為了 部落 而走的民族精神？

器具演進

從人工到電動－難道有人畫畫一開始就學電繪嗎？沒什麼大驚小怪的，會電腦打字就不會寫字了嗎？

Chapter 7

7.1

Prove that for any n > 3 there is a set of n point sites in the plane such that one of the cells of Vor(P) has n−1 vertices

證明一個點個數 n > 3 的 Voronoi diagram，存在一個 cell 具有 n - 1 個頂點。

如圖所示，一個點放置在圓心，剩餘的 n - 1 個放置在圓周上。則中間的 cell 必然有 n - 1 個頂點。

7.3

Show that $\Omega (nlogn)$ is a lower bound for computing Voronoi diagrams by reducing the sorting problem to the problem of computing Voronoi diagrams. You can assume that the Voronoi diagram algorithm should be able to compute for every vertex of the Voronoi diagram its incident edges in cyclic order around the vertex.

證明 Voronoi diagram 的 lower bound $\Omega (nlogn)$，藉由 reduce 到 sorting problem。

關於 reduce 證明，將一個簡單、約束較少的問題 A，藉由一個合適的轉換，變成一個困難問題 B 的 subset，已知 A 的 lower bound，則 B 的 lower bound 至少與 A 相同。

1. 假設排序 n 個整數 $x_{1}, x_{2}, ..., x_{n}$
2. 轉換成 $(x_{1}, 0), (x_{2}, 0), ..., (x_{n}, 0)$ 將所有點放置在 x 軸上，並且額外增加一點 $(\infty, 0)$。將 n + 1 個點找到 Voronoi diagram，對於 $(\infty, 0)$ 的 cell 而言，恰好邊都是由另外 n 個點對應的 cell 構成 cell edge (相鄰)。假設儲存邊的順序為順或逆時針，則邊的順序等價排序結果。

最後如上圖所示，又已知轉換需要 $O(n)$，sorting $\Omega (nlogn)$，則 Voronoi diagram 的 lower bound $\Omega (nlogn)$。

7.5

Give an example where the parabola defined by some site $p_{i}$ contributes more than one arc to the beach line. Can you give an example where it contributes a linear number of arcs?

如上圖所示，$p_{i}$ 拉出的拋物線 (parabola) 有可能提供多個弧 (arc)。(最左側的點提供 2 個弧)

一個點 $p_{i}$ 存有的 arc 數量與 cell($p_{i}$) 的頂點數量線性相關。由 exercose 7.1 得到最多 $O(n)$ 的頂點。同理 arc 數量最多 $O(n)$。

beach line 上的 arc 數最多為 Voronoi diagram 的 edge 數，又 Voronoi diagram 的 edge 最大數為 $3n - 6$，也因此最多為 $O(n)$

7.10

Let P be a set of n points in the plane. Give an $O(nlogn)$ time algorithm to find two points in P that are closest together. Show that your algorithm is correct.

Algorithm:

1. 建造 Voronoi Diagram by fortune’s algorithm－$O(nlogn)$
2. 對於每一個 cell($p_{i}$) 檢查鄰居 cell($p_{neighbor}$)，計算 $distance(p_{i}, p_{neighbor})$ 的結果。Voronoi diagram 的 edge 數 $3n - 6$，每一條 edge 檢查只需要 $O(1)$。－$O(n)$

證明：每一個點所張開的 cell 只會與相鄰的 cell 最近，否則不符合 Voronoi diagram 的定義。

7.14

Show that the farthest point Voronoi diagram on n points in the plane has at most 2n−3 (bounded or unbounded) edges. Also give an exact bound on the maximum number of vertices in the farthest point Voronoi diagram.

• 歐拉公式：$v - e + f = 2$
• 一個頂點至少三條邊。
• farthest point Voronoi diagram 的最多有 n - 2 個頂點。
  • 對於每一個頂點而言，通過其相鄰 cell 對應的點的外接圓，其圓包含所有平面點。
  • 這種圓最多 n - 2 個。
• 從隨機增量算法中得知，插入一個點時，最多增加一個 vertex (繞行時，會刪除對於 cell 相交兩個線段之間的所有 vertex，這種 vertex 至少一個，並且增加與線段的交點 1 個)。 $v(3) = 1, v(n) = v(n-1) + 1 \text{ for } n > 3$
• 考慮增加一個虛點，連接所有 unbounded edge
  $v - e + f = 2 \Rightarrow (n-2+1) - e + n = 2 \Rightarrow e = 2n - 3$。

Chpater 9

9.2

The degree of a point in a triangulation is the number of edges incident to it. Give an example of a set of n points in the plane such that, no matter how the set is triangulated, there is always a point whose degree is n−1.

對於任意三角化的結果，總會有一個點的 degree = n - 1。

• 此點一定能用一條線區隔所有剩餘點。
• 剩餘 n - 1 個點，一定能滿足任兩點的連線不遮蔽其他的點。

example：n - 1 個點落在 $y = e^{x}$ 上，且 $x < p$，另外一點在 $(p, q)$

9.4

Prove that the smallest angle of any triangulation of a convex polygon whose vertices lie on a circle is the same. This implies that any completion of the Delaunay triangulation of a set of points maximizes the minimum angle.

對於所有頂點共圓的凸多邊形，任何的三角化的最小角度都會相同。

1. 任何三角形必然是圓上三點。
2. 任何凸邊形的邊都會是一個三角形上的邊
3. 三角形的邊都是圓的弦，並且對應角度正比弦長大小。
4. 凸多邊形的最小弦長是多邊上的邊，又因一定會在三角形上，任何三角化一定包含這個最小角。

9.7

Prove that all edges of DG(Pr) that are not in DG(Pr−1) are incident to pr. In other words, the new edges of DG(Pr) form a star as in Figure 9.8. Give a direct proof, without referring to algorithm DELAUNAYTRIANGULATION.

對於新增加的邊 $e$，只會與新加入的點 $p_{r}$ 相連。

• 從 Voronoi diagram 等價 Delaunay triangulation，加入點的 cell，不會使其他兩個 cell 從沒相鄰變成相鄰。

• 對於 $\Delta(p_{i}, p_{j}, p_{k})$ 之間加入 $p_{r}$，由於 $C(p_{i}, p_{j}, p_{k})$ 內部不存在任何點，$C'(p_{i}, p_{r})$ (兩點當直徑)，得到 $C' \subseteq C$，且 $C'$ 內部不存在任何點，確定 $\bar{p_{i} p_{r}}$ 屬於 Delaunay 上。同理 $\bar{p_{j} p_{r}}$、$\bar{p_{k} p_{r}}$。

• 由於 $\Delta(p_{l}, p_{i}, p_{j})$ 原本是 Delaunay 上，如果 flip $\bar{p_{i} p_{j}}$，得到 $C(p_{i}, p_{r}, p_{l}) \subseteq C(p_{l}, p_{i}, p_{j})$、$C(p_{j}, p_{r}, p_{l}) \subseteq C(p_{l}, p_{i}, p_{j})$，確定 $\bar{p_{r} p_{l}}$ 屬於 Delaunay 上。

• 也因此，對於增加的三角形進行檢查時，每次已經保證該三角形其中兩邊一定屬於 Delaunay 上，同時必然有 $p_{r}$，flip 的邊一定會接到 $p_{r}$ 上。遞迴得證。

9.11

A Euclidean minimum spanning tree (EMST) of a set P of points in the plane is a tree of minimum total edge length connecting all the points. EMST’s are interesting in applications where we want to connect sites in a planar environment by communication lines (local area networks), roads, railroads, or the like.

1. Prove that the set of edges of a Delaunay triangulation of P contains an EMST for P.
2. Use this result to give an O(nlogn) algorithm to compute an EMST for P.

對於歐幾里得距離的平面最小生成樹。

1. 證明 EMST 的 edge set 被 Delaunay triangulation 的 edge set 包含。(參考 wiki)
   目標： every edge not in a Delaunay triangulation is also not in any EMST

   • 最小生成樹的性質：任何一個 cycle 上的最重邊將不會在最小生成樹中。

   • Delaunay triangulation： If there is a circle with two of the input points on its boundary which contains no other input points, the line between those two points is an edge of every Delaunay triangulation.

     對於鈍角三角形，最大邊必然不在 EMST 中，然而對於 Delaunay triangulation 性質，必須考慮他們兩點的 boundary (shared Voronoi edge) 是否存在。

     假設 p, q 之間沒有邊於 Delaunay，則對於任意通過 p, q 的圓都存在點 r 在圓內，從性質中發現 r 到 p, q 的距離一定小於 p q 之間的距離。同時在 EMST 中，p q r 三點會構成鈍角三角形，其中 p q 是最大邊，p q 之間必然沒有邊。

2. 找到 EMST 的 $O(nlogn)$ 算法
   Algorithm:

   1. 利用 Delaunay triangulation 找到所有邊－$O(nlogn)$
   2. 最多有 3n - 6 條邊，利用 MST 中的 kruskal’s algorithm－$O(ElogE)$
   3. $E = O(3n-6) = O(n)$，得到 $O(nlogn)$ 的做法。

9.13

The Gabriel graph of a set P of points in the plane is defined as follows:
p q Two points p and q are connected by an edge of the Gabriel graph if and only if the disc with diameter pq does not contain any other point of P.

1. Prove that DG(P) contains the Gabriel graph of P.
2. Prove that p and q are adjacent in the Gabriel graph of P if and only if the Delaunay edge between p and q intersects its dual Voronoi edge.
3. Give an O(nlogn) time algorithm to compute the Gabriel graph of a set of n points

Gabriel graph：任兩點之間為直徑的圓內若沒有其他點，則兩點之間有邊。

1. 證明 subgraph 關係。

• 根據 Theorem 9.6 (1) 任三點圓內 $C(p_{i}, p_{j}, p_{k})$沒有其他點，但是 $C(p_{i}, p_{j})$ 內部可能存有其他點 (如單純的 n = 3 的鈍角三角形)。找到 $e_{p_{i}, p_{j}} \notin Gabriel \text{ but } e_{p_{i}, p_{j}} \in Delaunay$
• $C(p_{i}, p_{j})$ 內部沒有其他點，則兩點之間必然有 shared Voronoi edge，符合 Theorem 9.6 (2)。得到
  $\text{ if }e_{p_{i}, p_{j}} \in Gabriel \text{ , then } e_{p_{i}, p_{j}} \in Delaunay$，得證 $g(P) \subseteq DG(P)$。

1. 如果 $\bar{pq}$ 經過多個 Voronoi edge，則 $\bar{pq}$ 上一點 x 滿足 $$\bar{xr} < \bar{xp}, \bar{xr} < \bar{xq} \\ \Rightarrow \angle rpx < \angle prx, \angle rqx < \angle xrq \text{(triangle)} \\ \text{let } \angle rpx = a, \angle prx = c, \angle rqx = b, \angle xrq = d \\ \Rightarrow a + b + c + d = 180^{\circ} \\ \Rightarrow c + d > 90^{\circ}$$

符合圓內角性質，點 r 一定在圓內，得證 $e_{p_{i}, p_{j}} \notin Gabriel$。

1. 在 O(n logn) 時間內完成。
   Algorithm：

   1. 利用 Delaunay triangulation 找到所有邊－$O(nlogn)$

   2. 將 $e_{p{i}, p{j}} \in DG(P)$ 進行測試是否有點落在 $C(p{i}, p{j})$－$O(n)$

      只需要拿鄰居進行檢測，鄰居最多 2 個 (共邊的三角形)。

9.14

The relative neighborhood graph of a set P of points in the plane is defined as follows: Two points p and q are connected by an edge of the relative neighborhood graph if and only if

1. Given two points p and q, let lune(p,q) be the moon-shaped region p q lune(p,q) formed as the intersection of the two circles around p and q whose radius is d(p,q). Prove that p and q are connected in the relative neighborhood graph if and only if lune(p,q) does not contain any point of P in its interior.
2. Prove that DG(P) contains the relative neighborhood graph of P.
3. Design an algorithm to compute the relative neighborhood graph of a given point set.

整體而言類似 9.13。

1. 若 p, q 之間沒有邊，則
   $$\exists r : d(p, q) > \underset{r \in P, r \neq p, q }{min} max(d(p, r), d(q, r)) \\ \exists r : d(p, q) > d(p, r) \text{ and } d(p, q) > d(q, r)$$
   AND 就是做交集操作，不知道該怎麼寫才好。
2. 與 9.14 依樣畫葫蘆，只是 $lune(p, q) \subseteq C(p, q)$，則更暗示 $\text{ if }e_{p_{i}, p_{j}} \in G \text{ , then } e_{p_{i}, p_{j}} \in Gabriel$
3. 速度是 $O(n^{2})$，沒辦法單純看鄰居進行檢查。拿每一條邊進行 O(n) 窮舉。不過在分散式計算，整體是 O(n)。