計(jì)算機(jī)科學(xué)課題：編譯器及計(jì)算模型的自動(dòng)機(jī)研究【大學(xué)組】

計(jì)算機(jī)科學(xué)/計(jì)算機(jī)工程/離散數(shù)學(xué)

項(xiàng)目背景

自動(dòng)機(jī)的推進(jìn)是達(dá)到圖靈機(jī)的理論鋪墊，其對(duì)應(yīng)喬姆斯基的四種文法，是程序設(shè)計(jì)語(yǔ)言和開發(fā)編程語(yǔ)言中的核心。在開發(fā)時(shí)用自動(dòng)機(jī)處理問(wèn)題，可以大量簡(jiǎn)化復(fù)雜的條件判斷，如正則表達(dá)式和一類自動(dòng)機(jī)等價(jià)等。作為形式文法和相應(yīng)自動(dòng)機(jī)的最重要實(shí)現(xiàn)，編譯原理需要極強(qiáng)的自動(dòng)機(jī)理論基礎(chǔ)。項(xiàng)目也將從自動(dòng)機(jī)理論在計(jì)算模型中的應(yīng)用展開。

項(xiàng)目介紹

自動(dòng)機(jī)是計(jì)算機(jī)科學(xué)中最基本的結(jié)構(gòu)之一，其在編程語(yǔ)言語(yǔ)義、系統(tǒng)建模和驗(yàn)證中均有重要應(yīng)用。余歸推納是一種證明環(huán)形結(jié)構(gòu)的方法，項(xiàng)目的重點(diǎn)在于介紹余歸推納在推理形式語(yǔ)言及自動(dòng)機(jī)中的應(yīng)用。學(xué)生將在項(xiàng)目中自選加權(quán)或概率隨機(jī)等自動(dòng)機(jī)的變種進(jìn)行研究，在項(xiàng)目結(jié)束時(shí)提交項(xiàng)目報(bào)告，進(jìn)行成果展示。

Automata are among the most basic structures in Computer Science and have arange of applications in semantics of programming languages, modelling systems,and verification. Coinduction is a technique to prove properties about circular structures, of which automata and formal languages are an example. The main objective of this tutorial is to show how coinduction can be used effectively to reason about a large class of languages and automata. These include weighted and probabilistic variants of automata, as well as classical word and tree automata.

個(gè)性化研究課題參考 Suggested Research Fields

基于自動(dòng)機(jī)理論的自動(dòng)循跡搜索目標(biāo)算法Automatic tracking target search algorithm based on automata theory

有窮自動(dòng)機(jī)理論在自動(dòng)化控制方面的應(yīng)用The application of finite automata theory in automatic control

編譯原理中的離散數(shù)學(xué)基礎(chǔ)理論還原研究Fundamental theory of discrete mathematics in compilation

適合人群

大學(xué)生

就讀于計(jì)算機(jī)科學(xué)、計(jì)算機(jī)工程、離散數(shù)學(xué)等專業(yè)或?qū)σ陨蠈I(yè)領(lǐng)域感興趣的學(xué)生。 學(xué)生需要具備微積分及線性代數(shù)基礎(chǔ)，修讀過(guò)算法與數(shù)據(jù)結(jié)構(gòu)，有Haskell等純函數(shù)式編程語(yǔ)言基礎(chǔ)的申請(qǐng)者優(yōu)先。

Instructor Introduction
導(dǎo)師介紹

倫敦大學(xué)學(xué)院英國(guó)皇家學(xué)會(huì)院士&終身正教授

導(dǎo)師現(xiàn)任倫敦大學(xué)學(xué)院終身正教授，同時(shí)是英國(guó)最大學(xué)術(shù)科研組織英國(guó)皇家學(xué)會(huì)院士。導(dǎo)師研究方向聚焦編程原理、邏輯、語(yǔ)義和計(jì)算模型。導(dǎo)師曾任荷蘭奈梅亨大學(xué)計(jì)算與信息科學(xué)研究所擔(dān)任終身教授。在此期間，導(dǎo)師是軟件工程組CWI基金會(huì)的訪問(wèn)者和Minho大學(xué)高保證軟件實(shí)驗(yàn)室HASLab的成員。

Alexandra is a Royal Society Wolfson Fellow and Professor of Algebra, Semantics, and Computation at the Programming Principles, Logic and Verification Group, University College London. From September 2011 to August 2015, She was a (tenured) assistant professor at the Foundations group in the Institute for Computing and Information Science of the Radboud University Nijmegen (The Netherlands). During that time, She was a visitor at the CWI Foundations of software engineering group and a member of HASLab, the University of Minho's High-Assurance Software Laboratory.

任職學(xué)校

UCL是倫敦第一所大學(xué)，以其多元、尖端的學(xué)科設(shè)置著稱，在REF 2014 英國(guó)大學(xué)官方排名中榮膺全英第一，并享有英國(guó)最多的科研經(jīng)費(fèi)；擁有英國(guó)國(guó)家醫(yī)學(xué)研究所、馬拉德空間科學(xué)實(shí)驗(yàn)室和蓋茨比計(jì)算神經(jīng)科學(xué)中心等前沿機(jī)構(gòu)，倫敦大學(xué)學(xué)院合作伙伴聯(lián)盟為全球最大的健康科學(xué)中心；旗下皇家自由醫(yī)院連年獲評(píng)全英最佳醫(yī)院，巴特萊特建筑學(xué)院和倫敦大學(xué)教育學(xué)院在各自領(lǐng)域獨(dú)步全球，醫(yī)學(xué)、計(jì)算機(jī)、法律、經(jīng)濟(jì)、考古等諸多學(xué)科排名全英第一 ，尤以計(jì)算機(jī)科學(xué)領(lǐng)域研究見長(zhǎng)，與LSE并稱為英國(guó)經(jīng)濟(jì)學(xué)的雙子星，其人文學(xué)院頒發(fā)的奧威爾獎(jiǎng)則是政治寫作界的最高榮譽(yù)。UCL共誕生有35位諾貝爾獎(jiǎng)得主、3位菲爾茲獎(jiǎng)得主及各領(lǐng)域菁英

項(xiàng)目大綱

自動(dòng)機(jī)與正則語(yǔ)言 Automata and Regular Languages

余歸推納:語(yǔ)言對(duì)等的基本技巧 Coinduction: basic techniques for language equivalence

正則表達(dá)式和增強(qiáng)余歸推納 Regular expressions and enhanced coinduction

自動(dòng)機(jī)理論在程序驗(yàn)證中的應(yīng)用 Applications to program verification

項(xiàng)目回顧與成果展示 Program review and presentation

論文輔導(dǎo) Project deliverable tutoring

時(shí)間安排與收獲

7周在線小組科研學(xué)習(xí)+5周論文輔導(dǎo)學(xué)習(xí) 共125課時(shí)

學(xué)術(shù)報(bào)告

優(yōu)秀學(xué)員獲主導(dǎo)師Reference Letter

EI/CPCI/Scopus/ProQuest/Crossref/EBSCO或同等級(jí)別索引國(guó)際會(huì)議全文投遞與發(fā)表（可用于申請(qǐng)）

結(jié)業(yè)證書

成績(jī)單