按照规范的设计方法，一个完整的数据库设计一般分为以下6个阶段：(51)：分析用户的需求，包括数据、功能和性能需求。

(52)：主要采用E—R模型进行设计，包括画E—R图。

(53)：通过将E—R图转换成表，实现从E—R模型到关系模型的转换。

(54)：主要是为所设计的数据库选择合适的存储结构和存取路径。

(55)：包括编程、测试和试运行。

(56)：系统的运行与数据库的日常维护。

(42)

(40)

(41)

The　Turing　machine　is　an　abstract(71)of　computer　execution　and　storage　introduced　in　1936　by　Alan　Turing　to　give　a　mathematically　precise　definition　of(72).　or　'mechanical　procedure'.　As　such　it　is　still　widely　used　in　theoretical　computer　science,　especially　in(73)theory　and　the　theory　of　computation.　The　thesis　that　states　that　Turing　machines　indeed　capture　the　informal　notion　of　effective　or　mechanical　method　in　logic　and　mathematics　is　known　as　Turing's　thesis.

Every　Turing　machine　computes　a　certain(74)partial　function　over　the　strings　over　its　alphabet.　In　that　sense　it　behaves　like　a　computer　with　a　fixed　program.　However,　as　Alan　luring　already　described,　we　can　encode　the　action　table　of　every　Turing　machine　in　a　string.　Thus　we　might　try　to　construct　a　Turing　machine　that　expects　on　its　tape　a　string　describing　an　action　table　followed　by　a　string　describing　the　input　tape,　and　then　computes　the　tape　that　the　encoded　Turing　machine　would　have　computed.　As　Turing　showed,　such　a　luring　machine　is　indeed　possible　and　since　it　is　able　to　simulate　any　other　Turing　machine　it　is　called　a(75)Turing　machine.

(39)

(35)

(36)

(37)

The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　applies　only　to　worst-case　complexity.　Being　NP-complete　does　not(68)that　a　problem　is　intractable　on　the　average　case.　Indeed,　some　NP-complete　problems　are　"(69)on　average",　though　some　may　not　be.　Levin　initiated　the　study　of　average-case　intractability,　He　showed　that　a　bounded　tiling　problem　under　a　simple　distribution　is　average-case　NP-complete.　Since　then,　several　additional　average-case　NP-complete　problems　have　been　shown　within　Levin's(70).　This　paper　is　intended　to　provide　a　comprehensive　survey　of　average-case　NP-complete　problems　that　have　been　published　so　far,　and　the　techniques　of　obtaining　these　results.

(34)