## 基本素養 Basic Literacy

Technological and Cultural literacy

Environmental and Social Care

Ability to communicate effectively with others and work in a team with developed international perspective

## 核心能力 Competence

Professional and interdisciplinary capacity

Innovative thinking as well as the ability to define and solve problems independently

Language and communication skills to coordinate the integration of interdisciplinary personnel

The ability to design, verify, and integrate with industrial implementations, and work together to promote industrial transformation and upgrading

Developed sense of self- improvement: International Perspective, Principle Literacy

## 課程概述 Course Description

This is an introductory course of Theory of Computation, which strives to use mathematical concepts and methods in order to understand a nature of computational phenomena. The theory practically explains creations, capabilities and limitations of computers of today, but any computers that could be built in future. The course introduces the elements of computational complexity theory with a particular interaction to the (complexity based) cryptography. The computational complexity investigates on resources (time and space) needed to make certain problems solved by computers which are modelled mathematically by Turing machines. Distinguishing hard and intractable problems without efficient algorithms, the computational complexity provides a foundation for the modern cryptography, where the aim is to design cryptosystems hard to break with limited amount of resources. The course also deals with the quantum computation, making a recent breakthrough to cryptography, whose mathematical formulation arises naturally as an extension of the classical computation using a concept of linear algebra. The extension is know as quantum gates and quantum Turing machines and enables modelling parallel computation (using quantum superposition) to speed up running time using novel algorithms.

## 課程學習目標 Course Objectives

• To acquire the basic concept of Turing Machine (TM) modelling
• To understand the major aim of cryptography
• To see mathematically how quantum computation is invented
• ## 課程進度 Progress Description

進度說明 Progress Description
1I Turing Machines I-i Formal Languages and States
2I-ii Turing Machines (deterministic)
3I-iii Computability and Undecidability
4I-iv Muititape Turing Machines
5I-v Nondeterministic Turing Machines
6I-vi DTM Simulation of NTM in Bounded Time
7II Computational Complexity II-i Polynomial Time and Nondeterministic Polynomial Time
8II-ii Complexity Classes (P, NP, EXPTIME)
9II-iii NP completeness (Hamilton Path Problem)
10 III Cryptography and Cryptographic Algorithms III-i Before CS (Information-Theoretic Security (one-time pad))
11III-ii Algebraic Preliminaries for Public-Key Cryptosystems (Discrete Log Problem and Prime Factorisation)
12III-iii ElGamal Encryption and RSA Public-Key Cryptosystem
13III-iv Polynomial Time Computation and One Way Functions
14 IV Introductory Quantum Computation IV-i Bloch Spheres, Quantum Bits, and Unitary Matrices
15IV-ii Quantum Gates
16IV-iii Quantum Turing Machines
17IV-iv Quantum Parallelism and Measurement
18IV-v An Elementary Quantum Algorithm (Deutsch Algorithm)
以上每週進度教師可依上課情況做適度調整。The schedule may be subject to change.

## 課程是否與永續發展目標相關調查 Survey of the conntent relevant to SDGs

本課程與SDGs相關項目如下：
This course is relevant to these items of SDGs as following:
• 就業與經濟成長 (Decent work and Economic growth)
• 工業、創新與基礎建設 (Industry Innovation and infrastructure)

## 有關課程其他調查 Other Surveys of Courses

1.本課程是否規劃業界教師參與教學或演講? 否
Is there any industry specialist invited in this course? How many times? No
2.本課程是否規劃含校外實習(並非參訪)? 否
Are there any internships involved in the course? How many hours? No
3.本課程是否可歸認為學術倫理課程? 否
Is this course recognized as an academic ethics course? In the course how many hours are regarding academic ethics topics? No
4.本課程是否屬進入社區實踐課程? 否
Is this course recognized as a Community engagement and Service learning course? Which community will be engaged? No