計(jì)算機(jī)科學(xué)導(dǎo)論CS10致遠(yuǎn)學(xué)院-上海交通大學(xué)

上海交通大學(xué) 致遠(yuǎn)學(xué)院 2014年秋季學(xué)期《計(jì)算機(jī)科學(xué)導(dǎo)論》課程教學(xué)說(shuō)明一.課程基本信息1．開(kāi)課學(xué)院（系）：致遠(yuǎn)學(xué)院2．課程名稱：《計(jì)算機(jī)科學(xué)導(dǎo)論》 (IntroductiontoComputerScience)3．學(xué)時(shí)/學(xué)分：48學(xué)時(shí)/3學(xué)分4．先修課程：無(wú)5．上課時(shí)間：第 1周-第16周；星期二第6節(jié)-第8節(jié)6．上課地點(diǎn)：東下院 202室7．任課教師：高曉沨（gao-xf@）、龍環(huán)（longhuan@）8．辦公室及電話：電信群樓 3號(hào)樓328室（34207407）、327室（34205060）9．助教：張雅濤（confidentao@）和陳智殷（cknight@）Officehour：每周2小時(shí)，電信群樓3-328室.課程主要內(nèi)容（中英文）第一章 計(jì)算機(jī)科學(xué)概論（ OverviewofComputerScience）主要內(nèi)容：概述計(jì)算機(jī)科學(xué)發(fā)展歷史， 了解現(xiàn)代計(jì)算機(jī)的發(fā)展和應(yīng)用領(lǐng)域， 掌握計(jì)算機(jī)的特點(diǎn)，介紹計(jì)算機(jī)科學(xué)主要學(xué)科與課程內(nèi)容。重點(diǎn)與難點(diǎn)：突出介紹計(jì)算機(jī)科學(xué)的起源與發(fā)展， 強(qiáng)調(diào)計(jì)算機(jī)科學(xué)對(duì)技術(shù)的影響， 闡述課程主要目標(biāo)。第二章 集合論，函數(shù)，關(guān)系（ Set,Function,andRelation）主要內(nèi)容：熟悉集合，函數(shù)，關(guān)系等基本概念及基本定理，并了解它們?cè)谟?jì)算機(jī)科學(xué)中的作用。重點(diǎn)與難點(diǎn)：集合悖論，關(guān)系演算，函數(shù)中的五個(gè)公理。第三章 基數(shù)/勢(shì)（Cardinality）主要內(nèi)容：學(xué)習(xí)基數(shù)及其中的基本概念，掌握與之相關(guān)的重要原理，并了解它們?cè)谟?jì)算機(jī)科學(xué)中的作用。重點(diǎn)與難點(diǎn)：自然數(shù)，等勢(shì)，有限集 /無(wú)限集，鴿巢原理等。第四章 邏輯（Logic）主要內(nèi)容：掌握命題邏輯、謂詞邏輯中的相關(guān)概念，介紹數(shù)理邏輯的發(fā)展以及其和計(jì)算機(jī)科學(xué)的關(guān)系。重點(diǎn)與難點(diǎn)：命題邏輯，謂詞邏輯，迪摩根律，邏輯運(yùn)算，邏輯等值，推理演算，公理化體系，范式。1/4第五章 代數(shù)（Algebra）主要內(nèi)容：理解群，子群，循環(huán)群，排列群的概念，以及抽象代數(shù)在計(jì)算機(jī)科學(xué)的應(yīng)用。重點(diǎn)與難點(diǎn)：理解伽羅瓦理論，李代數(shù)，有限域等概念，以及相關(guān)屬性。第六章 概率（Probabilistic）主要內(nèi)容：了解概率在計(jì)算機(jī)科學(xué)中的作用，學(xué)習(xí)貝葉斯規(guī)則，離散隨機(jī)變量，期望，概率統(tǒng)計(jì)方法等知識(shí)點(diǎn)。重點(diǎn)與難點(diǎn)：理解確定多項(xiàng)式，概率算法，霍爾問(wèn)題等。第七章 數(shù)論（NumberTheory）主要內(nèi)容：了解數(shù)論在計(jì)算機(jī)科學(xué)中的作用，掌握整除理論、不定方程、同余、同余方程、二次同余式與平方剩余、原根與指標(biāo)以及連分?jǐn)?shù)等基本概念。重點(diǎn)與難點(diǎn)： 整數(shù)的可除性的基本概念和理論，同余的概念及其基本性質(zhì)，歐拉定理、費(fèi)馬小定理及其對(duì)循環(huán)小數(shù)的應(yīng)用。第八章 安全和密碼學(xué)（ SecurityandCryptology）主要內(nèi)容：介紹密碼學(xué)的基本概念，掌握加密，解密的基本原理，以及一些基本的攻擊和防御方法。重點(diǎn)與難點(diǎn)：理解加解密，攻擊 /檢測(cè)的基本過(guò)程。第九章 圖論（GraphTheory）主要內(nèi)容：掌握?qǐng)D論的基本概念、基本理論、歐拉圖與哈密爾頓圈，以及圖論中的重要結(jié)論和一些基本的圖論算法。重點(diǎn)與難點(diǎn)：理解圖、簡(jiǎn)單圖、圖的度、圖的連通性、圖的代數(shù)表示與匹配、歐拉圖與哈密爾頓圈。第十章 樹（Tree）主要內(nèi)容：介紹樹的概念，掌握割點(diǎn)與割邊，理解生成樹、平衡樹、樹的基本定理，以及樹的應(yīng)用和遍歷。重點(diǎn)與難點(diǎn)：樹的深度與廣度遍歷、樹的六個(gè)重要定理、最小生成樹、哈夫曼樹、以及基本樹生成算法。第十一章 數(shù)據(jù)結(jié)構(gòu)（DataStructure）主要內(nèi)容：了解數(shù)據(jù)結(jié)構(gòu)及其分類、 數(shù)據(jù)結(jié)構(gòu)與算法的密切關(guān)系， 熟悉各種常用數(shù)據(jù)結(jié)構(gòu)并能嘗試用數(shù)據(jù)結(jié)構(gòu)進(jìn)行簡(jiǎn)單算法設(shè)計(jì)。學(xué)習(xí)文件組織方法與索引技術(shù)。重點(diǎn)與難點(diǎn)：線形表、堆棧、數(shù)組、排序、遞歸。第十二章 算法1（Algorithm1）主要內(nèi)容：掌握算法、算法復(fù)雜度的基本概念， 學(xué)習(xí)遞歸與分治算法、 二分搜索、Hanoi塔算法、動(dòng)態(tài)規(guī)劃2/4重點(diǎn)與難點(diǎn)：遞歸思想、算法與時(shí)間復(fù)雜度概念、動(dòng)態(tài)規(guī)劃的基本要素第十三章 算法2（Algorithm2）主要內(nèi)容：學(xué)習(xí)貪心算法、局部搜索等常用優(yōu)化算法。重點(diǎn)與難點(diǎn)：貪心算法基本要素，掌握貪心算法基本思想。局部搜索法的應(yīng)用范疇第十四章 可計(jì)算理論（ ComputabilityTheory）主要內(nèi)容：了解可計(jì)算的概念，學(xué)習(xí)抽象計(jì)算模型如圖靈機(jī)、無(wú)限注冊(cè)機(jī)、理解丘奇 -圖靈定理及哥德?tīng)柌豢赏陚涠ɡ?。重點(diǎn)與難點(diǎn)：理解可計(jì)算的抽象意義、計(jì)算模型與可計(jì)算的問(wèn)題第十五章 自動(dòng)機(jī)與計(jì)算復(fù)雜性理論（ AutomataandComputationalComplexity）主要內(nèi)容：學(xué)習(xí)確定型自動(dòng)機(jī)、非確定型自動(dòng)機(jī)、計(jì)算復(fù)雜性理論、 P與NP的概念和復(fù)雜性分類的意義。重點(diǎn)與難點(diǎn)：理解自動(dòng)機(jī)、圖靈機(jī)與計(jì)算復(fù)雜性理論的意義， 判斷問(wèn)題的復(fù)雜性、 學(xué)習(xí)歸約技術(shù)。三.課程教學(xué)進(jìn)度安排（擬定）第一部分、基礎(chǔ)篇(Part1:Fundamentals)Week教學(xué)內(nèi)容作業(yè)課程實(shí)驗(yàn)1FundamentalsLab-01Syllabus,Organization,IntroductiontoComputerScience2Set,Function,andRelationLab-02FixGradingPolicy,Set,Function,Relation,etc.Group3NationalHoliday.4CardinalityLab-03Definition,Haltingproblem,etc5LogicLab-04Epistemiclogic,Muddychildrenproblem,Propositionallogic6AlgebraLab-05Group,Ring,Field,AbelGroup,Monoid,etc.7ProbabilisticLab-06TrainingBirthdayproblem,Hashingcollision,Unionbound,etc.8NumberTheoryLab-07Divisibility,ModularArithmetic,Chineseremaindertheorem.9SecurityandCryptologyLab-08Encryption,Cryptology,Security,etc.第二部分、技術(shù)篇(Part2:Technologies)10GraphLab-09ReleaseProjectGraphrepresentation,Graphcoloring,Graphisomorphism,etc3/4TreeLab-1011Tree,BFS,DFS,SpanningTree,Kruskal,Prim,etc.DataStructureLab-1112LinearList,Stack,Queue,Array,etc.Algorithms(1)Lab-1213GreedyAlgorithm,DynamicAlgorithm,Divide-and-ConquerAlgorithms(2)Lab-1314HeuristicAlgorithm,LocalSearch,Optimization,etc.ComputationalComplexityLab-1415P,NP,Reduction,TimeComplexity,SpaceComplexity,etc.Automata,Language,andComputability,FinalReview16Lab-15TuringMachine,Church-TuringThesis,RecursiveFunction四.課程考核方式及說(shuō)明課程內(nèi)容百分比評(píng)分標(biāo)準(zhǔn)：期中考試25%90-100%A期末考試25%80-89%B課后作業(yè)30%70-79%C課堂實(shí)驗(yàn)10%60-69%D平時(shí)成績(jī)10%59%andbelowF總評(píng)100%五.教材與參考書本課程以課堂筆記為主，輔以如下參考書目：離散數(shù)學(xué)：DiscreteMathematicsandItsApplications(6thEdition),KennethH.Rosen,McGraw-HillCompanies,2007.集合論：ElementsofSetTheory,HerbertB.Enderton,ACADEMICPRESS,1977邏輯：《集論與邏輯》，沈恩紹，科學(xué)出版社， 2001算法：Algorithm,Dasgupta,C.H.Papadimitriou,andU.V.Vazirani,SpringerNY,2006.自動(dòng)機(jī)：ProblemSolvinginAutomata,Languages,andComplexity,Ding-ZhuDu,Ker-IKo,JohnWiley&Sons,Inc.,2001.可計(jì)算理論：Computability:AnIntroductio