計(jì)算理論基礎(chǔ)教學(xué)大綱-資料下載頁(yè)
【導(dǎo)讀】對(duì)集合，關(guān)系等基本。*三個(gè)基本證明技術(shù)：數(shù)學(xué)歸納法，鴿籠原理，對(duì)角化原理。*閉包及其算法，封閉性與閉包的關(guān)系。*字母表和語(yǔ)言：對(duì)何謂字母表，何謂字符串，以及字符串的性質(zhì)，如空串，及它的子串這些概念有清楚的認(rèn)識(shí)，注意區(qū)分L?*語(yǔ)言的有窮表示（字符串）和由于這一特點(diǎn)而帶來(lái)的表示上的先天缺。五元組，格局，一步產(chǎn)生，接受，M接受的語(yǔ)言，自動(dòng)機(jī)狀態(tài)圖。確定型有窮自動(dòng)機(jī)和非確定型之間的等價(jià)。有窮自動(dòng)機(jī)在并，連接，Kleene,補(bǔ)，交等運(yùn)算下的封閉性。*正則語(yǔ)言與非正則語(yǔ)言的區(qū)別：泵定理（重點(diǎn)）。確定型－>狀態(tài)最小的確定型；Chomsky范式，將任一上下文無(wú)關(guān)文法化為等價(jià)的Chomsky范式。在Chomsky范式基礎(chǔ)上的動(dòng)態(tài)規(guī)劃算法以及其復(fù)雜度分析。*Turing機(jī)的相關(guān)定義和它的特點(diǎn)。在Turing機(jī)計(jì)算中對(duì)輸入串的各種要求，對(duì)初始格局的要求。1．多帶Turing機(jī)以及它與標(biāo)準(zhǔn)Turing機(jī)的等價(jià)性證明。3．多帶頭Turing機(jī)。語(yǔ)言可被文法生成當(dāng)且僅當(dāng)它是遞歸可枚舉的。與Turing機(jī)有關(guān)的不可判定問(wèn)題
【正文】 3． 多帶頭 Turing機(jī)。 4． 二維帶 Turing機(jī)。 ? *隨機(jī)存 取 Turing 機(jī)的一系列相關(guān)定義和它與標(biāo)準(zhǔn) Turing 機(jī)的等價(jià)性。 ? *非確定型 Turing 機(jī)的相關(guān)定義以及它在判定，半判定，計(jì)算等功能上與標(biāo)準(zhǔn) Turing 機(jī)的等價(jià)性 。 ? 文法 ： 文法的相關(guān)定義。 語(yǔ)言可被文法生成當(dāng)且僅當(dāng)它是遞歸可枚舉的 。 文法可計(jì)算的定義 。（這樣定義的原因） ? *數(shù)值函數(shù) 1． 基本函數(shù) 2． 函數(shù)的組合與遞歸定義 3． 原始遞歸函數(shù) 4． 遞歸謂詞 5． 極小化的定義 6． ? 遞歸的定義 7． ? 遞歸和遞歸之間的關(guān)系。 第五章 不可判定性 ? ChurchTuring 論題 ? 通用 Turing 機(jī) ? 停機(jī)問(wèn)題 ? 與 Turing 機(jī)有關(guān)的不可判定問(wèn)題 NOTE: 注 *號(hào)者為必修內(nèi)容 ? 與文法有關(guān)的不可解問(wèn)題，不可解鋪磚問(wèn)題 ? 遞歸語(yǔ)言的性質(zhì)。
鄂ICP備17016276號(hào)-1