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

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

項目背景

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

項目介紹

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

個性化研究課題參考 Suggested Research Fields

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

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

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

適合人群

大學(xué)生

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

Instructor Introduction
導(dǎo)師介紹

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

導(dǎo)師現(xiàn)任倫敦大學(xué)學(xué)院終身正教授，同時是英國最大學(xué)術(shù)科研組織英國皇家學(xué)會院士。導(dǎo)師研究方向聚焦編程原理、邏輯、語義和計算模型。導(dǎo)師曾任荷蘭奈梅亨大學(xué)計算與信息科學(xué)研究所擔(dān)任終身教授。在此期間，導(dǎo)師是軟件工程組CWI基金會的訪問者和Minho大學(xué)高保證軟件實驗室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 英國大學(xué)官方排名中榮膺全英第一，并享有英國最多的科研經(jīng)費；擁有英國國家醫(yī)學(xué)研究所、馬拉德空間科學(xué)實驗室和蓋茨比計算神經(jīng)科學(xué)中心等前沿機構(gòu)，倫敦大學(xué)學(xué)院合作伙伴聯(lián)盟為全球最大的健康科學(xué)中心；旗下皇家自由醫(yī)院連年獲評全英最佳醫(yī)院，巴特萊特建筑學(xué)院和倫敦大學(xué)教育學(xué)院在各自領(lǐng)域獨步全球，醫(yī)學(xué)、計算機、法律、經(jīng)濟(jì)、考古等諸多學(xué)科排名全英第一 ，尤以計算機科學(xué)領(lǐng)域研究見長，與LSE并稱為英國經(jīng)濟(jì)學(xué)的雙子星，其人文學(xué)院頒發(fā)的奧威爾獎則是政治寫作界的最高榮譽。UCL共誕生有35位諾貝爾獎得主、3位菲爾茲獎得主及各領(lǐng)域菁英

項目大綱

自動機與正則語言 Automata and Regular Languages

余歸推納:語言對等的基本技巧 Coinduction: basic techniques for language equivalence

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

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

項目回顧與成果展示 Program review and presentation

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

時間安排與收獲

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

學(xué)術(shù)報告

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

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

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

成績單