離散數學實驗教學大綱一、課程基本信息課程名稱（中文）離散數學課程名稱（英文）DataStructure課程類型專業基礎課學分4總學時52+16適用對象信息與計算科學專業（本科）考核方式閉卷筆試與上機考試相結合、其中平時成績占20%、實驗成績占10%、期末考試成績占70%先修課程線性代數后繼課程操作系統、數據庫原理、數學建模等二、實驗課程簡介本課程是結合理論課程《離散數學》安排的實踐課程，目的是通過本課程的實踐與操作，加深理論課程中離散數學的理解。離散數學實驗是對學生的一種全面綜合訓練，是與課堂聽講、自學和練習相輔相成的必不可少的一個教學環節。針對本實驗課程的特點，讓學生利用所學的知識開發小型項目，要求學生能獨立分析問題，設計算法，實現程序的各項功能，得到正確的可執行程序，學會調試程序，對設計過程進行系統的總結。三、實驗目的《離散數學》課程實驗的目的是訓練學生進行復雜程序設計的技能和培養良好程序設計的習慣。通過完成本實驗課的實驗，學生應學會和掌握本課程的基本和重點知識；深刻理解邏輯結構、物理結構、算法設計之間的關系；訓練并具有進行復雜程序設計的能力，養成良好程序設計的習慣。四、實驗內容與要求實驗1集合的運算學時：4學時實驗目的：掌握用線性表來表示集合，并求其交、并、差和補運算的方法。實驗內容：（1）一個集合用一個順序表來表示。集合的元素是整數。建立兩個集合A={1,2,3}和B={2,4,5}。表的元素可以有序也可以無序。（2）求交：把A中元素逐一與B中的元素進行比較，將相同的元素放在C中，C便是集合A和集合B的交（如果A和B有序，則可以用一層循環實現，大大節省計算量）。要求C也用順序表表示，即寫一個函數：intListInter(SqList*pA,SqList*pB,SqList*pC)（3）求并：把A中各個元素先保存在C中。將B中的元素逐一與C中的元素進行比較，把不相同的元素添加到C中，C便是集合A和集合B的并。要求C也用順序表表示，即寫一個函數：intListUnion(SqList*pA,SqList*pB,SqList*pC)實驗2關系的性質學時：4學時實驗目的：掌握二元關系在計算機上的表示方法，并掌握如何判定關系的性質。實驗內容：（1）用一個有序對的集合來表示一個關系，可用順序表來表示。在集合A={1,2,3}上建立一個關系R={(1,1),(1,2),(1,3),(3,1)}。（2）判斷關系R是否自反。即寫一個函數：intListRefl(SqList*pR).（3）判斷關系R是否對稱。即寫一個函數：intListSymm(SqList*pR).（4）判斷關系R是否傳遞。即寫一個函數：intListTran(SqList*pR).（5）若S={(1,2),(2,3)}，寫一個函數ListSynt(SqList*pR,SqList*pS,SqList*pT)求R與S的合成關系T。（6）若R={(1,1),(2,2),(3,3),(1,2),(2,1)}，先根據(1)(2)(3)判斷是否是等價關系。然后寫一個函數ListEqui(SqList*pR)求所有等價類，每行輸出一個等價類的所有元素。實驗3歸結原理學時：4學時實驗目的：掌握用計算機實現歸結原理，自動求解命題邏輯的方法。實驗內容：一個子句用一個結構體表示，一個結構體包含兩個順序表，一個表的元素(可用整數)用來表示子句箭頭左邊的符號集，另一個表示右邊的符號集。多個子句用結構體數組來表示。如子句和可以表示為如下代碼。建立多個子句后。寫一個函數intResolution(TCC[],intn)對n個子句進行歸結，如果含有空語句，則返回1，否則返回0。實驗4RSA加密算法學時：4學時實驗目的：掌握用計算機實現RSA加密算法的方法。實驗內容：（1）首先實現較小整數(10000以內)范圍內的RSA加密解密算法。找兩個素數：p=47，q=59。n=p*q=2773。t=(p-1)*(q-1)=2668。取e=847，滿足e<=""p="">取d=63，滿足d*e%t=1。設消息M=244。加密過程：c=M^e%n=244^847%2773=465解密過程：m=c^d%n=465^63%2773=244（2）考慮大整數（幾十到上百位）的RSA加密解密算法。此時大整數的運算不能直接用C語言中的int，因為int最大值為64億，只有10位。需要自己先定義一個大整數的加減乘和帶余除法的運算。五、主要儀器設備計算機六、實驗學時分配表序號實驗項目名稱學時實驗內容實驗性質每組人數必/選做演示驗證設計綜合1集合的運算4用線性表來表示集合√1必做2關系的性質4判定關系的性質√1必做3歸結原理4自動求解命題邏輯√1必做4RSA加密算法4實現RSA加密算法√1必做七、考核方法上機考試為開卷考試八、教材及參考書教材：孫吉貴,楊鳳杰，歐陽丹彤著.離散數學,北京:高等教育出版社,2002.