《益智游戏与算法》教学大纲

课程编号：  MS006022  

课程名称：益智游戏与算法   英文名称：Puzzle games and algorithms

学分/学时：1/16                         课程性质：选修            

适用专业：理工科专业                    开设学期：第一学期     

先修课程：无                            开课单位：数学与统计学院   

一、课程教学目标及任务

益智游戏在人工智能发展过程中起着非常重要的作用。从最初的跳棋，到深蓝攻克国际象棋，再到Alpha Go攻陷围棋。人工智能取得的里程碑式的成就都和益智游戏息息相关。本课程教学目标及任务如下：（1）介绍一些与数学密切相关的益智游戏，例如幻方，数独，魔方等。（2）介绍一些算法的基础知识，在此基础上重点介绍遗传算法。（3）在案列研究部分，重点展示如何基于遗传算法求解幻方、数独问题。

希望籍此通识课程的开设和教学，开阔学生的视野，普及人工智能的知识，激发学生的学习兴趣。

二、课程教学内容及基本要求

本课程简要介绍了几种益智游戏，同时对算法做了一些基本介绍。重点介绍了遗传算法并基于遗传算法对幻方和数独问题进行了求解。  

第一章 智力游戏简介(4学时)

1.教学内容

益智游戏简介；幻方的由来，怎样构造幻方；数独简介，数独与拉丁方，数独求解练习；魔方。

2.基本要求

了解拉丁方；学会构造简单的幻方；会求解简单的数独；

3.重点、难点

重点：数独的求解 难点：数独的求解

4.采用的教学方法及要求：课堂讲授、讨论。

5.作业及课外学习要求：完成作业和自学内容。

 第二章 算法简介(6学时)

1.教学内容

算法简介；算法的优劣；深度优先与广度优先搜索；随机数的生成；蒙特卡洛算法；启发式算法与贪婪算法；遗传算法。

2. 基本要求

    了解算法及其优劣；了解深度优先搜索与广度优先搜索；掌握各种均匀分布随机数的生成；了解蒙特卡洛算法；了解启发式算法与贪婪算法；掌握遗传算法的原理与算法流程。

 3.重点、难点

重点：蒙特卡洛算法 遗传算法 难点：遗传算法

4.采用的教学方法及要求：课堂讲授、讨论。

5.作业及课外学习要求：完成作业和自学内容。

第三章 案列研究(6学时)

1.教学内容

基于遗传算法求解幻方问题；基于遗传算法求解数独问题

2.基本要求

      了解遗传算法求解幻方问题的思路与遗传算法中的交叉算子与变异算子的设计

 3.重点、难点

重点：程序设计与实现 难点：程序设计与实现

4.采用的教学方法及要求：课堂讲授、讨论。

5.作业及课外学习要求：完成作业和自学内容。

 三、教学安排及方式

总学时 16 学时，讲授 14学时，小测验、综合练习等多种形式2学时．

四、考核及成绩评定方式

总评成绩由平时成绩和期末课程论文成绩按比例综合而成.各部分所占比例如下：

平时成绩： 60%。包括平时作业（上机实验）和课堂考勤等.平时作业主要考核对课堂学习知识点的理解和掌握程度。

小测验：40%.课堂测验，考核学生发现、分析和解决问题的能力。

过程成绩提交时间和总评成绩计算说明表

注：上表用于说明授课过程中分项成绩提交时间，教师应在规定的时间内提交对应成绩，提前或逾期无法提交，一旦提交无法修改。大纲可以根据需要自行定义提交成绩的次数、时间和名称或说明，总评成绩计算必须与考核和成绩评定方式中描述的一致。

.

五、教材及参考书目

教材：无

参考书目：

[1]吴鹤龄等编著，《幻方及其他》(第二版)，北京：科学出版社，2004.   

[2]吴鹤龄等编著，《七巧板，九连环和华容道》(第二版)，北京：科学出版社，2004.

[3]（美）罗森豪斯，塔尔曼著；肖华勇译《数独了不起：全世界最流行的填字游戏背后的数学》，北京：机械工业出版社，2013.

[4]北京广播电视台数独发展总部编著，中国数独段位考试教程，北京：龙门书局，2013.

[5]（美）科尔曼等编著，算法导论（影印版），北京：高等教育出版社，2006.

[6] 陈国良等编著，遗传算法及其应用，北京：人民邮电出版社，1999.

（执笔人：刘延风；审核人：杨有龙）

2018年7月26日