课程号：ME206002

课程名：算法及其复杂度分析

英文课程名：Algorithms and Complexity

开课单位：机电工程学院

授课教师：Dmitry A. Zaitsev

责任教师：李志武   刘鼎

学分/学时：1学分/16学时

教师简介：Dmitry A. Zaitsev教授分别于1986年、1991年在乌克兰顿涅斯克理工学院获得应用数学专业学士学位、计算机科学专业硕士学位，2004在乌克兰基辅控制研究所取得自动控制专业博士学位，2006在乌克兰敖德萨国立电信学院取得电信系统与网络专业博士学位，现为乌克兰国际人文大学教授。是美国计算机学会会员，IEEE会员，德国波恩Petri网及相关系统模型特设研究组会员，并被列入马奎斯世界名人录；发表国际期刊及会议论文90余篇。他的研究领域主要包括网络技术，系统和网络模型，操作系统和系统软件等。具体的研究方向包括Petri网理论及应用，通讯协议，软件工程，制造业管理及控制等。Dmitry A. Professor Zaitsev obtained his bachelor's degree in Applied Mathematics and master's degree in computer science from Donetsk Polytechnic Institute (DPI), Ukraine in 1986 and 1991, his doctor's degree in automatic control from Academic Council of Kiev Cybernetics Institute in 2004, and in telecommunication system and network from Academic Council of Odessa National Academy of Telecommunications (ONAT), Ukraine in 2006. Now he is a professor of Odessa State Environmental University, department of Information Technology. He is senior member of the ACM and IEEE, and special research group of Bonn Petri net and related system models in Germany. He has been listed in the Marquis Who's Who. He has published more than 90 international journals and conference papers. His research fields mainly include network technology, system and network model, operating system and system software, etc. Specific research directions include Petri net theory and application, communication protocol, software engineering, manufacturing management and control.

课程简介：本课程主要讲授了算法的概念及其复杂度分析，研究如何高效开发算法或者程序。本课程首先从算法及其空间和时间复杂度的概念出发，以图灵机作为计算模型讲解，并介绍了一些不确定性问题。同时包含一些离散数学的内容，如图，树的基本知识。而后分别研究递归算法，排序算法，搜索算法，以及NP问题的本质和目前国际前沿的进展。最后讲解动态规划和程序的设计范式，以此探讨如何高效开发算法和程序。This course mainly introduces the concept of algorithm and its complexity analysis, and how to develop algorithm or program efficiently. This course starts from the concept of algorithm and its space and time complexity, explaining Turing machine as the computation model, and introduces some undecidable problems. At the same time, it contains some basic knowledge of discrete mathematics, such as graph theory and tree. Then the recursive algorithm, the sorting algorithm, the search algorithm, and NP-hard problem are analyzed. In the end, the dynamic programming and paradigms of programming are mentioned.

先修课程：无