1 绪论

研究背景

上个世界60年代初，西方国家进入小汽车大发展时代，经济的快速发展带来人口。小汽车拥有量及道路交通流量急剧增加。城市道路系统在人口增长带来的交通需求增加和机动车增长的双重压力下，陷入维修道路赶不上交通增长的困境。在经过小汽车时代的理性思考后，城市居民和政府官员终于明白：优先发展城市交通才是缓解城市交通拥挤问题，构建城市可持续交通发展模式的有效途径。

美国从从19xx年颁布《城市公共交通法》后。相继通过了《城市公告交通扶助法》（1970），《地面交通法》（1992），并在19xx年后5年间在公告交通和 交通中投入315亿美元，为公共交通的发展提供了政策，经济上的保证。新加坡政府出台的“陆路运输政策”也大力提倡公交优先。其目的是：通过系统的城市规划，降低交通需求，建立广泛综合的路网系统，加快速捷运系统和公共汽车构成的有效可行的公共交通系统，严格控制车辆的增长。香港作为亚太地区的主要金融，贸易和通讯中心，高密度的人口和高强度的运输决定了其需要有高效率的道路交通，铁路交通和海上交通接洽。受制于香港的地理环境，香港政府制定了一系列政策，大力发展公共交通，加强道路交通运输设施的建设，强化交通的管理和控制，省出一半的道路面积给货运车辆用，并保证大容量的快速轨道交通建设与土地使用紧密结合，建立综合换乘枢纽与物业开发结合，将各种交通方式衔接在一起，方便换乘。巴西库里蒂巴市在公共交通规划管理方面，引入Metrobus公共交通系统，并通过与城市土地领用规划，避免了很多城市化进程中遇到的城市道路拥堵及拥堵带来的各种环境问题。

在我国，随着国民经济的快速发展，城市建设规模不断扩大，大城市数量不断增加，大城市人口高度集中并大幅度增长，城市交通需求也迅速扩大。20xx年，全国100万人口以上的特大城市27个，人口超过200万的超大城市13个。北京作为中国的首都，车辆的增长尤为突出，年增长率超过15%。南京市1978~19xx年机动车拥有量年递增率为12.3%，出行频率较高的小客车年增加16.5%而南京市的道路里程及道路面积年增长率仅为5.1%和7.2%，成都市机动车由19xx年的20万辆增加到20xx年的102万辆，平均每年增加10万辆，20xx年一年增加了15万辆。道路交通基础设施建设的发展则相对滞后，使得城市交通需求与供给之间的矛盾越来越突出。我国32个百万人口以上的大城市中有27个人均道路面积低于全国平均水品。上海市50%以上的道路高峰小时饱和度达到95%，全天饱和度超过70%，平均车速10km/h。北京等特大城市中心区的高峰期车辆平均速度低于20km/h，最低仅为4km/h（低于正常人不行速度）。城市道路系统及各项交通设施无法满足交通需求的增长，城市“乘车难”，“行车难”的局面在加剧，交通阻塞呈现出由点到线，有线到面的扩张趋势。交通拥挤，交通延误交通阻塞以及由此引起的噪声.废弃污染等问题严重影响着城市局面的正常生活以及社会经济的持续.健康发展。北京市机动车排放NO2.CO的分担率已高达46%和63%。20xx年，我国发生道路交通事故667,507起，造成104,372人死亡，494,174人受伤，直接经济损失高达33.7亿元。即使一些大中城市的交通基础

设施现状能够满足交通需求，但由于经济的快速发展，机动化进程加快，私家小汽车逐渐泛滥，也同样存在着交通隐患，城市的交通状况不容乐观

在综合比较分析和借鉴国外经验的基础上，许多研究城市交通问题的专家认为，通过优先发展公共交通，建立科学合理的出新结构，才能实现城市与交通的可持续发展。我国许多大中城市已陆续加入到发展公交优先的大趋势中。北京.广州.昆明.郑州.长沙.济南.大连等城市先后开辟了公交专用道路等公交优先策略。

第二篇：计算引论论文

浅谈计算模型

计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论，通俗说来，就是研究用计算机求解问题的难易程度。它有两个度量标准：一是计算所需的步数或指令条数(这叫时间复杂度)，二是计算所需的存储单元数量(这叫空间复杂度)。我们当然不可能也不必要就一个个具体问题去研究它的计算复杂性，而是依据难度去研究各种计算问题之间的联系，按复杂性把问题分成不同的类:常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(logn)、线形阶0(n)、线形对数阶0(nlogn)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(n^k)、指数阶0(2^n)。显然，时间复杂度为指数阶0(2^n)的算法效率极低，当n值稍大时就无法应用。不言而喻，对于任意给定的问题。设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标。

而可计算性（calculability）是指一个实际问题是否可以使用计算机来解决．从广义上讲如“帮我洗衣服”这样的问题是无法用计算机来解决的（至少在目前）．而计算机本身的优势在于数值计算，因此可计算性通常指这一类问题是否可以用计算机解决．事实上，很多非数值问题（比如文字识别，图象处理等）都可以通过转化成为数值问题来交给计算机处理，但是一个可以使用计算机解决的问题应该被定义为“可以在有限步骤内被解决的问题”，故哥德巴赫猜想这样的问题是不属于“可计算问题”之列的，因为计算机没有办法给出数学意义上的证明，因此也没有任何理由期待计算机能解决世界上所有的问题．分析某个问题的可计算性意义重大，它使得人们不必浪费时间在不可能解决的问题上（因而可以尽早转而使用除计算机以外更加有效的手段），集中资源在可以解决的问题集中．

语言可以看作是一个非空的字母集合，自动机则是一种控制结构，是抽象的计算机模型。形式语言和自动机密切相关。图灵机——0型语言（递归可枚举）——无限制文法；下面我再说说看书时所得的关于其他自动机的内容。

一、正则文法——正则语言——有穷自动机（DFA、NFA）

1、正则语言与正则表达式本质上相同：

  定理1.1：r是正则表达式，则一定存在某个带ε_转移的NFA接受r表示的语言L（r），因此，L（r）是正则语言。

  定理1.2：设L是正则语言，那么总存在正则表达式r，使得L＝L（r）。

     L是正则语言→L可被某个NFA接受→通过删除NFA节点的方法写出r

2、右线性文法和左线性文法都是正则文法

  也就是说，在正则文法中，任何产生式的右侧至多有一个非终结符（变量），且此非终结符一定在产生式右侧的最右端或最左端。如：

             A → xB

             A → x        （右线性文法）

        或

             A → Bx

             A → x        （左线性文法）

3、L是正则语言，当且仅当存在正则文法G，满足L＝L（G）。

4、DFA、NFA的定义

定义一个DFA M 是一个5元组

M=(Q, ∑, δ, q0, F)

其中，  Q：有限的状态集合（非空）

∑：用穷的字母表

δ：转移函数

q0∈Q：初始状态 

         FQ：终态集合

δ(q , a) = p,   

  扩充转移函数

，

就得到了NFA M。

5、定理1.3 设L为某个NFA M接受，则存在一个DFA M接受L。

——DFA和NFA的等价性

6、识别非正则语言——泵引理

  泵引理  设L是正则语言，那么一定存在一个只与L相关的正整常数m，使得对任意w∈L且|w|≥m，都可以分解成：

w = xyz

其中，                     |xy|≤m

                        |y|≥1

并且，对所有的i＝0, 1, 2……, 都有wi ＝ xyiz ∈L。

7、正则语言对并、交、补、连接、星闭包、代换（含同态、逆同态）运算都是封闭的。

8、构造正则文法、DFA以及正则语言的判断例题见作业本。

二、上下文无关文法CFG——上下文无关语言CFL

——非确定型下推自动机（NPDA或PDA）

1、定义：文法G＝（V, T, S, P）称为上下文无关文法CFG(context-free grammar)，如果P中的产生式具有形式           A → x

其中，A∈V , x∈(V∪T)*。

  L是上下文无关语言CFL，当且仅当存在一个CFG，满足L = L(G)。

对任何上下文无关语言CFL，都存在一个NPDA M使得L＝L(M)。

 NPDA（或PDA）的定义：

DPDA的定义：

2、识别非上下文无关语言CFL——泵引理

  泵引理  设L是上下文无关语言CFL，那么一定存在一个只与L相关的正整常数m，使得对任意w∈L且|w|≥m，都可以分解成：

w = uvxyz

其中，                     |vxy|≤m

                        |vy|≥1

并且，对所有的i＝0, 1, 2……, 都有wi ＝ uvixyiz ∈L。

3、上下文无关语言对并、连接、闭包运算封闭，对交、补运算不封闭。

4、设L1是一个CFL，L2是一个正则语言，则L1∩L2是一个CFL。

——CFL与正则语言的交是CFL。

三、上下文相关文法CSG——上下文无关语言CSL——线性有界自动机（LBA）

1、定义：文法G＝（V, T, S, P）称为上下文相关文法CSG(context-sensitive)，如果P中的所有产生式都有如下形式

x → y

其中，x,y∈(V∪T)*，且

                           |x| ≤ |y|

  L是上下文相关语言CSL，当且仅当存在一个CSG，满足L = L(G)或L(G)∪{ε}。

对任何不包含ε的上下文相关语言CSL，都存在一个LBA M使得L＝L(M)。

    图灵机的运行：让存储带运作起来，外界的信息开始进入图灵机；读写头读出存储带的内容，控制器控制图灵机，使之按照某种特定的规则对纸带传入的信息作出反应，完成程序所规定的动作；完成动作之后，纸带继续移动，开始下一个循环的工作。

关于N与NP问题，首先还是说一下我是怎么理解的吧！为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A到B是否有长度为1的路径？从A到B是否有长度为2的路径？。。。从A到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。
然而有些问题很难找到多项式时间的算法（或许根本不存在），这类问题，我们无法用传统的方法，也就是程序化的方法解决，称为NP问题。

参考文献：

可计算性与计算复杂性等；