基本素養 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

    教師上傳大綱內容
    本資訊僅提供本校師生參考。有著作權,非本校人員若欲使用本資訊,請洽本校取得授權。
    © (2008-2022) National Cheng Kung University ALL RIGHTS RESERVED.

    濱野正浩-數學與演算法.pdf