周一（2015/2/2）到贡比涅大学（Université de Technologie de Compiègne）作报告去了。

法国高等教育体制有别于欧洲及美国，分：大学校（Grandes Ecoles）和公立综合大学(Université)。“公立综合大学”属于大众化教育机构，在校生占全国大学生的80%-90%，学生没有入学考试，通过高中毕业会考，就有资格就读， 但一、二年级的淘汰率很高；“大学校”是为培养专业领域内精英人才的院校，学生要先上两年的预科，再通过严格的入学考试，方可入学。

“大学校”按领域分为：工程师学院（école d'ingénieurs）、高等商学院（école de commerce）、高等师范学院（école normale）、政治学院（Institut d'Etudes Politiques）等。而贡比涅大学比较特别，是一所集美国和法国传统教育、兼具公立综合大学和工程师学院特点的大学，因其以教学、科研、科技成果转让三位一体的办学方针而独具特色。

我的博士论文是在贡比涅大学做的，导师是Jacques Carlier。师长极具耐心，如中国师父般带我艰难而又顺利的完成了论文，步入了法国大学教学和研究之路，之后一直和师长保持着师生之谊。几年前，我开始了困难重重的计算机复杂性理论的研究，Jacques一直持旁观的态度，最近因此工作告一段落，所以就到他那作报告了。报告结束讨论时，虽说大家一时无法评论如此意外的内容，但表示：确实也觉得目前的计算机复杂性理论有问题，比如，用“多项式时间复杂度”表达算法有效性的不足，算法理论与算法设计的脱节等。而让我很高兴的是，Jacques看出了此工作努力于中西文化交流、融合的指向，因此给了许多的鼓励和提醒，。。。

昨天Jacques来信，其中说到：

－对我来说，也认为这个理论有缺陷，在理论与实践之间存在着太大的差距。此外，图灵机是一个过于简化的工具。最后，算法时间复杂度用大O符号表示，导致了100的1次方和10次方不分，诸如此类的滥用。应该建立一种系统，能以更精确的方式评估复杂度函数，即要考虑到函数的内涵意义。

－Pour moi aussi cette théorie est très imparfaite dans la mesure où il y a un trop grand écart entre la théorie et la pratique. Par ailleurs, la machine de Turing est un outil un peu trop fruste. Enfin le grand O permet tous les abus dans la mesure où 1 et 10 puissance 100 sont la même chose. Il faudrait un système qui permette d’évaluer la fonction de complexité de façon plus précise, c’est –à-dire avec des expressions de cette fonction.

把此报告的文件附上，供有兴趣的网友参考。

seminaireUTC.pdf