廣告

32 thoughts on “

  1. 我想強調的是:微分拓樸、圖論,兩個是不同的公理系統。

    按照數學家(你應該是學這行的吧)的習性,那麼首先要有聯繫這兩個領域的理論。比方說,平面圖一定可以embedding到平面流形嗎?或者反過來,平面流形取finite set一定可以得到平面圖嗎?這都要推導。

    就好比「處處連續處處不可微」那種噁心的東西一樣,依照公理系統仔細推導,說不定其中有些例外。

    因為我沒有學過「拓樸圖論」,所以沒有辦法回答。不過我認為兩者之間應該會有一些相關理論才對。(不過我對這種東西完全沒興趣。我又不是數學家,我只是個整理算法的民科。)

    直觀來看,圖和流形很顯然可以變來變去。至於那個直觀是不是完全正確的,那就要靠你啦。

  2. 你用一個stereographic projection就可以把一個平面圖打到球面上了啊
    因為stereographic projection是個homeomorphism(事實上是diffeomorphism) 我也可以把球面圖打回成平面圖
    事實上在一些平面圖相關的證明會用到(打到球面上再打回平面)的手法
    這種手法可以把任何一個face打到外面去

  3. Robertson–Seymour theorem的用途乍看是確保graph embedding之後,一些基本性質還在。接著可以正式引進graph embedding,把流形跟圖論聯繫在一起。最後再來一個stereographic projection,就完成了球面圖和平面圖的對應。看起來兩者的確是同構。

    不過我還是沒有仔細看懂graph embedding到底是什麼回事,也不想特地弄懂,就放過我吧,哈哈。

  4. 「平面流形」和「球面流形拿掉一點」是微分同胚。但是「平面圖」和「球面圖」應該不是同構的吧?我以為「微分拓樸」和「圖論」應該是兩回事。

    平面流形是以「拓樸」與「連續」這兩個數學概念為前提。平面圖是以「拓樸」與「邊不相交」兩個數學概念為前提。他們前提不一樣喔!你的說法應該是張飛打岳飛吧。

    至於Robertson–Seymour theorem我沒有學過。我剛剛看了維基百科,這個定理乍看之下是在講minor:無向偏序圖所沒有包含的minor,將形成一個完整的封閉集合(當父圖不是minor,則所有子圖也都不是minor)。這個跟平面圖、球面圖沒有什麼關係吧?

  5. 關於平面圖的部分
    “那有沒有球面圖呢?那有沒有立體不打結圖呢?應該有吧。"
    事實上 一個去掉一點的球面和一個平面是diffeomorphic的
    因此球面圖exactly就是平面圖 這也是為什麼沒有人研究球面圖的原因

    設M是一個二維曲面 那有沒有M圖? 當然有
    而且還可以證明 存在一個圖的有限集合S 使得
    (G不是M圖 iff G有一個graph minor在S裡面)
    這是Robertson–Seymour theorem的直接結果
    以M = R^2或S^2來說 我們可以挑S = \{K_5, K_{3, 3}\}

  6. 我也看得不是很懂。於是我調出了備份檔案,看起來應該是在2013-2014年之間,某一天那段程式碼忽然從flow變成了bottleneck。我還真想不透為什麼會憑空出現一個bottleneck,也許是那個時候我被鬼上身了吧。

  7. 匿名 說道:

    Edmonds-Karp Algorithm 章節中,在"找出一個最大流+計算最大流的流量"這邊
    第一個範例code有int bottleneck[10]; 卻都沒用到;code中又出現flow[] 這個 array,看得不是很懂,這兩個其實是一樣的嗎 ?

  8. 程式碼有錯,需要轉型成char,已經修正了,謝謝!
    C語言風格的轉型是

    cout << (char)(s[i] - 'A' + 'a');
    

    C++風格的轉型是

    cout << char(s[i] - 'A' + 'a');
    cout << static_cast<char>(s[i] - 'A' + 'a');
    
  9. Sophie 說道:

    void print_lowercase()
    {
    char s[15] = “Hello World!";

    for (int i=0; s[i]; i++)
    if (s[i] >= ‘A’ && s[i] <= 'Z')
    cout << s[i] – 'A' + 'a';
    else
    cout << s[i];
    }

    我拿去編譯H和W最後印出結果是數字
    out: 104ello 119orld!
    看code是沒有錯誤,所以只能用cast運算子嗎

  10. 數學家發明的數學名詞graph,是指點跟線組成的東西,用來紀錄一堆事物的倆倆關聯。
    http://www.csie.ntnu.edu.tw/~u91029/Graph.html

    計算機科學家發明的計算機科學名詞image,是指電腦圖片。而image file是指圖片檔案。常見的圖片檔案格式有bmp和jpg。
    http://www.csie.ntnu.edu.tw/~u91029/Image.html

    英國人、美國人發明的名詞image,是指影像、圖像。可以用視覺看到的具體畫面。
    http://www.dictionary.com/browse/image
    https://en.wikipedia.org/wiki/Image

    這三個東西,彼此之間都不一樣。

    至於為什麼他們中文都叫做圖,啊就某個古代中國人把這兩個不同的英文單字,故意翻譯成同一個中文字。是誰翻譯的已經不可考了。

    至於graph演算法可以套用到image file上嗎?或者換句話說,image file可以使用graph演算法嗎?事實上可以。
    更貼切的說法是image file可以使用各式各樣的數學知識,並不限於graph。這是科學家的工作,他們整天都在想這些事。

    演算法要怎麼套用到實際的圖檔,內容很多很雜,這不是在留言板上面用三言兩語可以講清楚的。如果你想學,大學的資工系所已經有課程了,課程名稱是image processing。網路課程也不少。網路書店也有同樣名稱的教科書,至少有十幾本吧。看你要上學或自學或找家教都行。

    目前來說,這些課程和教科書,都假定你已經有先備知識:程式設計、線性代數、演算法、……等等。如果你沒有基礎,那麼這些課程和教科書並不適合你。

    此時你可能要花錢攏絡、下跪懇求相關專家製作一份不需要先備知識的教材──然而在台灣不太可能發生這種事。另一種方式是趕快去投胎,看看能不能變成萬中選一的奇才,可以無師自通。

  11. Gan 說道:

    不好意思想請問一下,您在"Graph"那邊講的"圖",都是點跟線組成圖,那跟我們實際看到的圖檔(jpg、bmp)有什麼關聯嗎?演算法要怎麼套用到實際的圖檔呢?謝謝您。

  12. 剛剛發現Google translate翻譯失敗。估計是因為charset:網頁定義UTF-8、服務器送出Big5,而Google translate應付不了這種情況。
    https://translate.google.com/translate?hl=zh-TW&sl=auto&tl=zh-CN&u=http://www.csie.ntnu.edu.tw/~u91029/about.html

    百度翻译可以運作,不必翻牆。然而用上JavaScript的地方都壞了。
    http://fanyi.baidu.com/transpage?query=http://www.csie.ntnu.edu.tw/~u91029/about.html&from=cht&to=zh&source=url&render=1

    我也不知道怎麼解決,只好請大家將就點吧。

  13. 我沒有web server管理權限。

    google translate可以簡轉繁,然而要翻牆。但翻牆是從事科研的基本技能吧,不學可不行。

  14. 曾經有人提議過類似的意見,不過沒有實現。我目前沒有翻譯成簡體中文的計劃。再者台灣沒有從支付寶、微信提領現金的管道。

    意想不到倒不至於。中國對算法的需求遠大於台灣。算法補習班諸如九章六月計蒜客;算法公司諸如大疆曠視百度;研究單位諸如微軟谷歌以及各高校,最近又多了個達摩院;黨中央今年也發布了人工智能的政策。所以說,網站若做得好,收到中國人捐贈是情理之中。

    至於台灣目前公開聲稱研究算法、人工智能的單位,都是詐騙集團,別人做啥就跟著喊啥。至於網站為何需要寫個募款訊息,這就不必多說,你想想就明白啦。

  15. xiekai 說道:

    可以把网站做成简体中文版,然后加上支付宝或者微信二维码让读者捐赠,你会收到意想不到的效果的

  16. RonChen 說道:

    以前有介紹位元運算的部分,現在找不到了,希望能再放上來,謝謝~~

Leave Message

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s