1、2022/7/25計算機應用技術研究所11離散數學Discrete Mathematics 汪榮貴 教授合肥工業大學計算機與信息學院2022/7/25計算機應用技術研究所2第七章 函數與特殊函數2022/7/25 本章學習內容 有限集的置換函數4 函數關系的應用52022/7/25計算機應用技術研究所4有限集的置換函數2022/7/25計算機應用技術研究所5 置換函數 置換函數的概念 置換函數的運算 置換的輪換分解2022/7/25 置換函數的概念2022/7/25 例 題2022/7/25 置換函數的概念2022/7/25 例 題2022/7/25 例 題【例題】等邊三角形如圖7-2所示，求

2、經過旋轉和翻轉能使之重合的所有置換函數.2022/7/25 例 題2022/7/25 例 題2022/7/25計算機應用技術研究所13 置換函數 置換函數的概念 置換函數的運算 置換的輪換分解2022/7/25計算機應用技術研究所14 置換函數的運算 置換是一種特殊的雙射函數，關于函數的求逆運算和復合運算在置換中完全適用. 因此，可直接將一般函數的逆運算和復合運算作為置換函數的逆運算和復合運算.2022/7/25計算機應用技術研究所15 例 題2022/7/25計算機應用技術研究所16 例 題2022/7/25計算機應用技術研究所17 置換函數的運算2022/7/25計算機應用技術研究所18

3、例 題2022/7/25計算機應用技術研究所19 置換函數 置換函數的概念 置換函數的運算 置換的輪換分解2022/7/25計算機應用技術研究所20 置換的輪換2022/7/25計算機應用技術研究所21 例 題2022/7/25計算機應用技術研究所22 置換的輪換2022/7/25計算機應用技術研究所23 置換的輪換2022/7/25計算機應用技術研究所24 置換的輪換2022/7/25計算機應用技術研究所25 例 題2022/7/25計算機應用技術研究所26 例 題試問按照同樣的洗牌方式，經過幾次洗牌可以將牌的順序恢復到原來的順序.2022/7/25計算機應用技術研究所27 例 題【分析】從

4、已知可以發現，不管怎么洗牌，1和12的位置始終不改變，但是其他牌的位置在每次洗牌之后都會發生變化，其變化存在如下規律：2561042,3911873由上面的規律可以知道，經過5輪的洗牌后，每張牌都將回到原來的位置。所以這是一個5階輪換，當輪換置換是n重輪換時，需要n次才可以將牌的順序恢復到原來的順序.2022/7/25 本章學習內容 有限集的置換函數4 函數關系的應用52022/7/25計算機應用技術研究所29函數關系的應用2022/7/25計算機應用技術研究所30 置換函數 哈希查找問題 網絡寬帶分配問題2022/7/25計算機應用技術研究所31 哈希查找問題【定義】哈希函數（Hash fu

5、nction）也稱為散列函數或 Hash函數，是一種將任意長度的輸入字符串變化為固定長的輸出字符串的函數。在數據結構中，通常借助哈希函數來加速對數據項的查找過程。根據應用情況的不同，通常也將哈希函數的輸出稱為哈希值或哈希碼或散列值等。2022/7/25計算機應用技術研究所32 哈希查找問題2022/7/25計算機應用技術研究所33 哈希查找問題2022/7/25計算機應用技術研究所34 哈希查找問題2022/7/25計算機應用技術研究所35 哈希查找問題2022/7/25計算機應用技術研究所36 哈希查找問題2022/7/25計算機應用技術研究所37 哈希查找問題2022/7/25計算機應用技

6、術研究所38 哈希查找問題常見的構造哈希函數的方法有以下幾種：3）平方取中法。平方取中法是一種比較常用的構造哈希函數的方法，具體是：將關鍵字求平方后，取其中間的幾位數字作為散列地址。由于關鍵字平方后的中間幾位數字和組成關鍵字的每一位數字都有關，因此產生沖突的可能性較小，最后究竟取幾位數字作為散列地址需要由散列表的長度決定。2022/7/25計算機應用技術研究所39 哈希查找問題例如，若結構的存儲地址范圍是1999，則取平方值的中間三位，如表所示。2022/7/25計算機應用技術研究所40 哈希查找問題常見的構造哈希函數的方法有以下幾種：4）折疊法。折疊法適用于關鍵字位數很多且關鍵字中每一位上數

7、字分布大致均勻的情況。具體方法是：將關鍵字分割成位數相同的幾部分（最后一部分的位數可以不同），然后取這幾部分的疊加和（舍去進位）作為哈希地址。疊加又可分為移位疊加和間界疊加。其中，移位疊加是將分組后的每位數字的最低位對齊，然后相加；間界疊加是將分組后的每組數字從一端向另一端沿分界線進行來回折疊，然后對齊相加。2022/7/25計算機應用技術研究所41 哈希查找問題2022/7/25計算機應用技術研究所42 哈希查找問題2022/7/25計算機應用技術研究所43 哈希查找問題2022/7/25計算機應用技術研究所44 哈希查找問題2022/7/25計算機應用技術研究所45 哈希查找問題2022/

8、7/25計算機應用技術研究所46 哈希查找問題常見的解決沖突的方法有下面幾種：2）再哈希法。再哈希法是當同義詞產生地址沖突時計算另一個哈希函數地址，直到沖突不再發生。這種方法不易產生“聚集”，但增加了計算的時間。2022/7/25計算機應用技術研究所47 哈希查找問題2022/7/25計算機應用技術研究所48 哈希查找問題2022/7/25計算機應用技術研究所49 網絡帶寬分配問題【問題前沿】 一般來說，用戶使用的寬帶分成兩部分：靜態寬帶和動態寬帶。靜態寬帶是運營商承諾的最小寬帶，已經預留給每個用戶；動態寬帶被所有的用戶共享，根據需求進行分配。語音視頻業務服務過程一般分成三步：建立連接、進行語音視頻傳輸、結束服務。對于已經建立連接并正在進行傳輸的服務，運營商應該保證其所需要的寬帶。而在連接階段，如果所有客戶申請的寬帶總量超過運營商所提供的寬帶時，則進行寬帶分配。用戶的優先級=他可使用的最大寬帶與已占有的寬帶之比，需求量越大，被滿足的寬帶越小，則優先級越高。2022/7/25計算機應用技術研究所50 網絡帶寬分配問題【問題描述】 假設已知每一項業務所申請的寬帶大小，在保證分配的寬帶之和不超過網絡總寬帶的條件下，如何選擇一部分業務，以使得這些業務的優先級收益（即所有業務的優先級之和）達到最大？2022/7/25計算機應用技術研究所51 網絡帶寬分配問題2