|
「資料結構與演算法」課程 [⏫上傳素材、指引] (Last update: 1/4/2025 11:23 AM) (講稿與程式碼將陸續更新) |
||
|
第0單元 |
🎯課程大綱：規劃、評分原則、觀念釐清、對同學的期許 ❔這門課適合我嗎？我是誤入叢林的小白兔?! ⚠為何測驗過程中不得使用ChatGPT或其他生成式AI工具來回答問題？
拿掉ChatGPT，你我剩下甚麼?! ⛽
本單元練習程式碼 |
|
|
第1單元 |
🎯演算法分析：Big-O、範例解析、何謂P、NP、NP-hard、NP-complete問題，遞迴手法與解特徵方程式的關聯、費伯納西數與黃金分割之間的巧妙關係 👉參考：NP完備問題—問題複雜性的分類 (台灣大學陳縕儂教授) |
🚀自家電腦安裝Dev-C++、Visual Studio Code、Code:Blocks (安裝教學)、Geany (擇一)自備可練習的環境 ⛽ 本單元練習程式碼 |
|
第2單元 |
🎯陣列：表示方式、上三角形和下三角形矩陣、多項式表示法、魔術方陣 🎯複習：C語言陣列 |
⛽
本單元練習程式碼 |
|
第3單元 |
🎯堆疊與佇列：堆疊的加入與刪除、佇列的加入與刪除、環狀佇列、應用 |
|
|
第4單元 |
🎯鏈結串列：單向串列、環狀串列、雙向串列、綜合應用 🎯複習：C語言指標與字串 🎯複習：C語言結構(struct) |
⛽
本單元練習程式碼 |
|
第5單元 |
🎯遞迴：常見範例、河內塔問題、八個皇后問題、何時不使用遞迴? |
📣謝謝同學提出以算數幾何不等式與“固定長度線段圍出最小面積”的觀點處理單層「最小包裝」問題，讓我反思原先所提解方的正確性，紀老師為同學大大按讚!!我這裡提供遞迴方式解題的版本，供大家參考比較 👉參考解以partition-integer.c
(運作範例)為基礎，考慮輸入一正整數所有可能的分割作為糖磚的包裝方式 ❔第五章末習題 ⛽
本單元練習程式碼 |
|
第6單元 |
🎯樹狀結構：二元樹、二元樹的表示法、二元樹的追蹤、引線二元樹、議題 |
❔第六章末習題 |
|
第7單元 |
🎯二元搜尋樹：基本內涵、二元搜尋樹的加入與刪除 |
⛽
本單元練習程式碼 |
|
第8單元 |
🎯堆積：基本內涵、min-heap、min-max heap、deap (double-ended
heap) |
❔第八章末習題 |
|
第9單元 |
🎯高度平衡二元搜尋樹 |
❔第九章末習題 |
|
第10單元 |
🎯 2-3樹與2-3-4樹 |
❔第十章末習題 |
|
第11單元 |
🎯 B-tree |
❔第十一章末習題 |
|
第12單元 |
🎯圖形結構：圖形資料結構表示法、圖形追蹤、擴展樹、最短路徑、拓樸排序、臨界路徑法 👉註：擴展樹、最短路徑的運作邏輯為貪婪法(於後面單元討論) |
⛽
本單元練習程式碼 |
|
第13單元 |
🎯排序：氣泡排序、選擇排序、插入排序、合併排序、快速排序、堆積排序、二元樹排序、謝耳排序、基數排序 |
❔第十三章末習題 |
|
第14單元 |
🎯搜尋：循序搜尋、二元搜尋、雜湊 |
❔第十四章末習題 |
|
第15單元 |
🎯Greedy Methods (計算凸面體的方法已更新為Graham scan演算法) |
|
|
第16單元 |
⛽
參考素材：最長相同子字串 |
|
|
第17單元 |
🎯Divide and
Conquer |
|
|
第18單元 |
🎯Prune and
Search |
|
|
參考資源 ✓ 臺灣師範大學演算法網站👍 ✓ 聯合大學資訊管理學系陳士杰教授的資料結構課程、演算法課程👍 ✓ 常見程式演算筆記
👍 ✓ NP、NP-complete與NP-hard之間的差異👍 ✓ 有任何一個NP-hard最佳化問題也是NP-complete？ ✓ 有用的論壇：stack overflow、W3Schools Tutorials、GeeksforGeeks 👍 ✓ 為什麼成為一名工程師這麼難？ (By Jewel) ✓ 搞笑談軟工：軟體開發與XX的關係 (By Teddy Chen) ✓ 科技如何綁架你的心智
(與課程無關，但藉此文讓同學反思是否已過度使用智慧型手機而不自知) |
||
![j0356582[2]](ds.files/image001.gif){kind=small}
Leave your message, thanks