一、請定義下列問題
1. The m-Coloring Problem
2. The Hamiltonian Circuits Problem
二、Suppose that n=4, W=16, and we have the following:
| i | pi | wi | pi/wi |
|---|---|---|---|
| 1 | $40 | 2 | $20 |
| 2 | $30 | 5 | $6 |
| 3 | $50 | 10 | $5 |
| 4 | $10 | 5 | $2 |
請用backtracking方法，解決0/1 Knapsack problem
三、試比較branch-and-bound與backtracking
(more...)
正所謂，住在學校宿舍，就要發揮它的最大效益──離學校什麼設備都近！離系上也近，離圖書館也近，離社辦也近，除了暑假期間校內餐廳關閉所以還是會騎摩托車往外跑之外，其他就真的是腳踏車走遍遍了。
話說暑假到了，你會想到什麼呢？夏天！炎熱的夏天！就是要游泳啊！昨天跑到積健樓那邊去看了游泳池的公告(很奇怪，他們都不會把這些訊息寫在網頁上，網站同等虛設)，開放時間與票價如下：
| 輔仁大學游泳池暑期開放時間 95年6月19日 至 8月20日 | |
|---|---|
| 上午時間 | 05:00至11:15 |
| 本校人員專屬時段 (週一至週四) | 12:00至13:30 |
| 下午時段 | 13:30至16:15 |
| 晚間時段 | 18:00至20:45 |
| 票價 | |
|---|---|
| 本校學生 校友或教職員工眷屬 | 40 |
| 半票 學生或兒童 | 80 |
| 全票 | 110 |
| 15次券(不限本人使用) | 1350 (90/次) |
| 30次券(不限本人使用) | 2400 (80/次) |
| 60次券(不限本人使用) | 4200 (70/次) |
大致上是這樣的，我是比較傾向早泳啦，最近都是7點就自動起床，再多努力一下的話，6點起來也不是多困難的事情吧。
話說下午的時段快要開放了耶...雖然想去，可是現在肚子裡面都還是剛剛午餐的飯，明明刻意提早吃午餐了，香城的份量還是太多了嗎orz 總之，就先看著辦吧。
(more...)
2006年5月3日擺置的桌布，主角是東方紅魔鄉的惡魔之妹 フランドール・スカーレット，不正常的個性或是不懂得拿捏的破壞力等等，怎樣都是讓人頭痛的角色。
因為紅色，而且多麼具有狂氣與傲氣的姿勢與表情，很吸引人不是嗎？這張桌布放了好一段時間。
20060514 筆電桌布，ARIA的燈里。這張桌布跟上一張都有修過，把字修掉。本來只是想要降低狂氣所以換了一張清新色調的，可是太過雜亂了，看起來很痛苦。在一次不小心把桌布關掉的情況之下，有好一段時間桌布是維持全黑的狀態。
20060609 筆電桌布，我也忘了這個月亮與貓是哪來的了。反正當時的桌布是黑的，那麼多一個月亮，我想也差不到哪去吧。結果覺得還蠻不錯的，應該可以維持一個暑假。
這篇桌布介紹已經拖了一個月了耶(汗
隨便寫完~~吃飯去~~
(more...)「感謝大家參與這場遊戲，希望能帶給你們充實的時光，下次請大家務必繼續光臨，一起來玩吧。」
我看過很多桌上遊戲的主持人(Game Master)，都會以這句話做為遊戲的閉幕。因為很喜歡，所以我也用這句話，為這學期的最後一天，也是最歡樂的一場桌上遊戲畫下句點。
於是，暑假開始了。
放假固然是很開心，也是很麻煩的事情。首先第一個令人苦惱的問題就是搬家。我自認為東西已經不多了，實際上卻還是相當的多，就算是事先搬移、囤積到其他地方去，要搬的東西還是多到看了會令人退縮的境界。
仔細分析看看自己房間的東西，書是最多的──課本、厚得像電話簿一樣的電腦書、數本F誌與十幾本漫畫、跟老妹借來的日文教材。其次要說的話，就是回憶物吧，尤其是最彼的東西，怎樣都有種不想讓它離開身邊的感覺。大概因為這是我的開始...也是我的終點，所以在我可以到達這個終點之前，我不會想要去挑戰終點的。此外的話，我生活使用的雜物還不少，帶起來也很重，身上裝備就算再怎樣實用取向，這點也該檢討檢討了。
跟以往一樣，我只要有摩托車與行李箱，一個人就這樣慢慢搬吧。雖然累，不過去年也是這樣過來的，所以今年也一定可以作得到。
除了搬家之外，國科會的計畫、英文老師的結案、幫隆基整理電腦、自我充實什麼的，也是該開始作業了。啊，還有，要好好適應一下孤單的暑假了。到系上卻沒有同學可以聊天，還蠻寂寞的。
明天是社團送舊啊......這也是這學期最讓我覺得可惜的部份吧，希望送舊的時候還是能跟大家快樂地在一起。
嗯，加油！然後好好地去面對這個暑假吧！
(more...)在實體層的訊號增強器(repeater)與集線器(hub)只是將小網路連結而成大網路，但是因為碰撞機會增加，造成區域網路的效能降低。網路區隔(isolate traffic)解決了這個問題，它可以依據傳送封包的目的位置，拒絕或接收封包傳遞到另一個區域網路。並檢查封包是否正確(錯誤偵測)，如果另一個區域網路使用不同格式的封包，也可以改變這個封包的格式，轉換成目的地區域網路的格式。屬於資料鏈結層(data-link layer)的橋接器(breidge)與交換器(switch)都具備這些能力。
記住幾個原則：
用這個規則來判斷，繞送表格就不難填寫了
透明式橋接器主要分成兩個部份
繞送學習 route learning
封包重複傳送...被跳過了
路徑資訊協定是一種自治系統 (automous systems)，可以讓路由器之間自動通知到特定網路位置的最短路徑。
路徑資訊協定又分成內部路徑協定(interior routing protocol)與外部協定(exterior routing protocol)。內部路徑協定控制自治系統內的路徑，外部路徑協定則是自治系統外。老師主要是講內部路徑協定。
內部路徑協定是透過不斷地傳送訊息以確定各個路徑的資訊，其路徑距離的單位是hop，意思是跳過幾個路由器的記數。與透明式橋接器的封包學習功能一樣，路由器會給每個位置一個計時器，以刪除過久沒有傳送訊息的位置。
TCP，傳送控制協定(Transmission Control Protocol)，是一種連接導向的網路層服務。兩台電腦以TCP連結時，會先執行握手動作(handshake)，確認並建立起彼此邏輯上的連結。每一邊都會有流量控管協定(flow control protocol)、確認機制(acknowledge segment)與回報受損的封包以確保可靠的連結。TCP應用在以穩定為目的的服務上，網路上大部分常見的服務都是透過TCP在傳送，例如SMTP (Simple Mail Transfer Protocol，簡單郵件傳送協定，就是送電子郵件用的)、Telnet (網路遠端控制) 、HTTP與FTP。
UDP...
請解釋IP當中的網路位置、機器數量以及子網路遮罩，並得算出在特定子網路遮罩中的網路位置以及機器的節點數量。
HDLC的頁框中，為避免頁框資料與標示頁框起始與終點的旗號(flag)相同，也就是01111110，所以送方在送出五個1的時候，自動填入一個0；而收方則是在收到五個1的時候，自動刪去一個0，以保持平衡。
BSC協定的透明資料頁框(transparent data frame)中，為了避免資料與控制訊號相混，因此使用DLE來打開或關閉控制訊號的檢查，在STX(Start of Text)與ETX(End of Text)之前各安插一個DLE。DLE就像是Toggle Switch一樣，第一次讀到DLE的時候，會關閉ETX的檢查，因此不會與ETX相混；直到讀到下一個DLE，才再次打開對ETX的檢查。
然而，這依然會有資料與DLE相同而誤判的情況發生。所以在送出前，要把資料與DLE一樣的地方後面，再加入一個DLE。這種方法稱之為位元組填充(byte stuffing)。
乙太網路的資料欄有資料的下限與上限。因為乙太網路是使用匯流排(bus)協定的方式在運作，同一時間內只能有一台電腦傳送資料，為了避免通道佔據時間過長，所以設定上限為1500位元組；為了確保CSMA/CD (載體感應多重存取與碰撞偵測)偵測機制能夠正常運作，資料長度必須確保要在頁框最後一個位元送出前聽到碰撞的聲音，所以下限是46位元組。
因為有下限的緣故，不足於下限的話，便用填充欄(pad field)來補足長度。
集線器(hub)，又稱為多工訊號增強器(multiport repeater)，擁有許多個連接埠，可用10BaseT(10Mbps, 基頻, 雙絞線)連接到多台電腦。Hub的外部線是星狀拓樸，但是內部仍是用匯流排協定。當其中一台電腦要傳遞資料給另一台電腦時，必須要先將資料傳送給hub，再由hub複製資料，傳送到每一台電腦。
Hub的優點是可以簡化檢查的工作，可從hub看出哪一台電腦連接失效；hub也保留了匯流排拓樸容易安裝、移除裝置的特色。
switch的構造類似hub的不同，但是hub的傳送資料是傳遞給所有電腦，這也包括了不相干的電腦，因而提高網路阻塞的時間、增加碰撞的機會；swtich則是只傳送給目標的電腦，而不會造成無浪費。
在10Mbps乙太網路中，是使用Manchester自我同步碼傳送資料。如果要增加傳送的資料量，而加快Manchester碼的頻率的話，也會造成太高的噪音。
因此在100BaseTX當中，改用straight NRZI不回歸0編碼傳送。但是不回歸0編碼的問題在於，當連續太多0傳送的時候，便會失去自我同步的功能。因此100BaseTX將資料先以4B/5B的方式，將4個位元的資料改成另一種5個位元的資料，以確保同步。
雖然straight NRZI不回歸0編碼搭配4B/5B的方式會浪費25%的多餘消耗，不過速度上還是比Manchester自我同步碼來得快。
為了降低高頻所帶來的噪音，又發展出多層次線路傳輸──三層(Multilevel Line Transmission-Three Levels, MLT-3)。跟以往使用兩種訊號(0與1)不一樣，MLT-3使用三種訊號(0、1與-1)。當要傳送0的時候，訊號不變；傳送1的時候，才改變訊號到下一層。
MLT-3是-1→0→+1→0→-1完成一個循環，與Manchester碼的low→high→low比起來可以容納更多訊息，頻率最多也只需要Manchester的25%。因此MLT-3可以取代Manchester而達到更低頻率、攜帶更多訊息的優勢。
(more...)
考試範圍：
1. 匯流排拓樸 (bus topology)
優點是簡單，不論是新增或移除其中一台電腦都很容易。缺點是傳送資料時，是以廣播(broadcast)的方式把資料傳送到每台電腦，同一時間點上只允許一台電腦傳送資料，否則會發生碰撞(contention)。
2. 環狀拓樸 (ring topology)
環狀拓樸是將每台電腦串成一個圈圈，每台電腦輪流傳遞權杖(token)，拿到權杖的電腦可以把資料放在權杖中，權杖中的資料記錄著來源電腦與目的電腦，資料僅有目的電腦可以接收，傳完一圈之後，來源電腦有權限刪除該資料。環狀拓樸優點是允許多台電腦傳送資料，缺點是裝置的增加或刪除都必須重新設定，而且一台電腦的錯誤會導致網路癱瘓，難以偵錯。
3. 星狀拓樸 (star topology)
一台電腦作為其他所有電腦的邏輯通訊中心 ，任何電腦要傳送訊息，都必須透過這台電腦。
這層的用處是連結網路兩點間的傳輸，其功能包括
IBM制定，之後經過多次申請，名稱演變的樹狀圖為：
HDLC是一種位元導向的協定，支援半雙工與全雙工通訊。
位元導向：HDLC把頁框(frame)當成位元串流(bit stream)處理。
在HDLC當中設備(device)被區分為三種：
HDLC通訊模式也有三種：(斯斯聽說只有兩種)
| 位元數 | 8 | 8或16 | 8或16 | 不固定 | 16或32 | 8 |
|---|---|---|---|---|---|---|
| 旗號 Flag |
位置 Address |
控制訊號 Control |
--資料-- | 頁框檢查序列 FCS |
旗號 Flag |
‧旗號 Flag
用來標示頁框的開頭與結尾。一概是由01111110 (0兩個，中間1六個，共八個位元)組成。
位元填充 (bit stuffing)
‧位置 Address
頁框檢查序列(frame check sequence，FCS)：使用CRC檢查，CRC多項是為x16 + x12 + x5 + 1。
由開頭的一到兩個位元來定義頁框的類型：
資料頁框 Information frame
| 位元數 | 1 | 3 | 1 | 3 |
|---|---|---|---|---|
| 0 | N(S) 本頁框編號 |
P/F 要求/終點 |
N(R) 預期頁框 |
監督頁框 Supervisory frame
| 位元數 | 1 | 1 | 2 | 1 | 3 |
|---|---|---|---|---|---|
| 1 | 0 | S 狀態 |
P/F 要求/終點 |
N(R) 預期頁框 |
無編號頁框 Unnumbered frame
| 位元數 | 1 | 1 | 2 | 1 | 3 |
|---|---|---|---|---|---|
| 1 | 1 | M 協定決定 |
P/F 要求/終點 |
M 協定決定 |
(a) 建立連結
(b) 交換頁框
(c) 結束連結
特色
剩下的看有沒有時間寫囉！
(more...)
Comments