A tutor on coding, Sep 9, 2011 An Introduction to Computer Programming k wo- ne At twm)4:2sas54 童伟华 E-mail:tongwh@ustc.edu.cn 中国科学技术大学数学系 http://math.ustc.edu.cn/
An Introduction to Computer Programming 童 伟 华 E-mail: tongwh@ustc.edu.cn 中国科学技术大学 数学系 http://math.ustc.edu.cn/ A tutor on coding, Sep 9, 2011
内容提纲 编程概要 编程模型 编程语言 编程环境 软件庠介绍 编程进阶 A tutor on coding, Sep 9, 2011 2
2 A tutor on coding , Sep 9, 2011 内容提纲 编程概要 编程模型 编程语言 编程环境 软件库介绍 编程进阶
编程概要 ■什么是编程? From Wikipedia Computer programming (often shortened to programming or coding) is the process of writing, testing, debugging/troubleshooting and maintaining the source code of computer programs. This source code is written in a programming language. The code may be a modification of an existing source or something completely new. The purpose of programming is to create a program that exhibits a certain desired behaviour(customization).The process of writing source code often requires expertise in many different subjects, including knowledge of the application domain, specialized algorithms and formal logic 编程:编写,测试,调试,维护 ●核心:应用领域知识十算法十数据结构 A tutor on coding, Sep 9, 2011
3 A tutor on coding , Sep 9, 2011 编程概要 什么是编程？ ⚫ From Wikipedia : Computer programming (often shortened to programming or coding) is the process of writing, testing, debugging/troubleshooting, and maintaining the source code of computer programs. This source code is written in a programming language. The code may be a modification of an existing source or something completely new. The purpose of programming is to create a program that exhibits a certain desired behaviour (customization). The process of writing source code often requires expertise in many different subjects, including knowledge of the application domain, specialized algorithms and formal logic. ⚫ 编程：编写，测试，调试，维护 ⚫ 核心：应用领域知识＋算法＋数据结构
编程概要 ■历史简述 编程的概念出现: The concept of devices that operate following a pre-defined set of instructions traces back to Greek Mythology, notably Hephaestus and his mechanical servants. The antikythera mechanism was a calculator utilizing gears of various sizes and configuration to determine its operation ●可编程机械出现:1206年,伊斯兰数学家A Jazari's programmable automata 现代计算机逻辑模型的发明:1936年,Aan Turing在伦敦数学进畏中发表题为“On Computable Numbers, with an Application to the Entscheidungsproblem”,提出通用图 灵机的概念(计算机的逻辑模型),1944年, Von neumann在美国 Los Alamos National Laboratory的 Manhattan Project中提出该体 糸结构,后被 ENIAC project使用 A tutor on coding, Sep 9, 2011 4
4 A tutor on coding , Sep 9, 2011 编程概要 历史简述 ⚫ 编程的概念出现：The concept of devices that operate following a pre -defined set of instructions traces back to Greek Mythology, notably Hephaestus and his mechanical servants. The Antikythera mechanism was a calculator utilizing gears of various sizes and configuration to determine its operation. ⚫ 可编程机械出现：1206年，伊斯兰数学家Al - Jazari's programmable Automata ⚫ 现代计算机逻辑模型的发明：1936年，Alan Turing 在伦敦数学进展中发表题为 “On Computable Numbers, with an Application to the Entscheidungsproblem ”，提出通用图 灵机的概念（计算机的逻辑模型），1944年， Von Neumann在美国Los Alamos National Laboratory 的 Manhattan Project中提出该体 系结构，后被ENIAC project 使用
编程概要 ■图灵机( uring machine) Logical Computing Machine: an infinite memory capacity obtained in the form of an infinite tape marked out into squares on each of which a ymbol could be printed At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine Any symbol on the tape may therefore eventually have an innings A tutor on coding, Sep 9, 2011 5
5 A tutor on coding , Sep 9, 2011 编程概要 图灵机(Turing machine) ⚫ Logical Computing Machine ：an infinite memory capacity obtained in the form of an infinite tape marked out into squares on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings
编程概要 图灵机 Hopcroft and Ulman(1979, p. 148) formally define a(one-tape) Turing machine as a 7-tuple M=(Q, T,b, 2,6, qo. F)where a O is a finite set of states T is a finite set of the tape alphabet/symbols bE Tis the blank symbol(the only symbol allowed to occur on the tape infinitely often at any step during the computation) ecr\blis the set of input symbols 8: Qxr-QxIX(L, RJis a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows"no shift", say N, as a third element of the latter set. go∈ Qis the initial cQis the set of final or accepting states. Anything that operates according to these specifications is a Turing machine A tutor on coding, Sep 9, 2011 6
6 A tutor on coding , Sep 9, 2011 编程概要 图灵机
编程概要 图灵机 3 tate busy beet州R O!iCe.o: compete configuratin(ala Instantaneous desapio) Sequence Instruction Instruction A B H TAPE& TABE&HEAD OOOCCCCOOOOCOCC 0000cccoooo0 o A 9 0000cCco100Co0 B01 1A1 11c0 345678901234 ABAcBA 0000 AAA 111B0 0000000c 1111A9 B000011111000000 111B11 B00OCC1 Toooocv 11B111 B 000 可BB 1 BBB 1111 10 1111 11111 A000CCO 111100c 1A11111 0000C1 11c1111 H000CC111110000C 11H1111 Progress of the computation (state-trajectory) of a 3-state busy beaver 真实的计算机:图灵机的实现〔 (the random access stored program machine) A tutor on coding, Sep 9, 2011
7 A tutor on coding , Sep 9, 2011 编程概要 图灵机 真实的计算机：图灵机的实现(the random access stored program machine)
编程概要 ■ Von Neumann结构 o is a design model for a stored-program digital computer that uses a processing unit and a single separate storage structure to hold both instructions and data. It is named after the mathematician and early computer scientist John von Neumann. Such computers implement a universal Turing machine and have a sequential architecture. MEMORY CONTROL ARITHMETIC UNIT LOGIO UNIT accumulator INPUT OUTPUT A tutor on coding, Sep 9, 2011 8
8 A tutor on coding , Sep 9, 2011 编程概要 Von Neumann结构 ⚫ is a design model for a stored-program digital computer that uses a processing unit and a single separate storage structure to hold both instructions and data. It is named after the mathematician and early computer scientist John von Neumann. Such computers implement a universal Turing machine and have a sequential architecture
编程概要 Personal computer的组成(包括BMPC, Notebook or Laptop, Tablet PC, Pocket PC<) CPU:中央处理器 ● Motherboard:主板 · Main memory:内存 ● Hard disk:硬盘 ● Video card:视频卡 辅助设备:网卡、声卡等(现在一般集成在主板上 输入设备:键盘,鼠标等 输出设备:显示器,音响等 A tutor on coding, Sep 9, 2011
9 A tutor on coding , Sep 9, 2011 编程概要 Personal computer的组成（包括IBM-PC, Notebook or Laptop, Tablet PC, Pocket PC等) ⚫ CPU：中央处理器 ⚫ Motherboard：主板 ⚫ Main memory：内存 ⚫ Hard disk：硬盘 ⚫ Video card：视频卡 ⚫ 辅助设备：网卡、声卡等（现在一般集成在主板上） ⚫ 输入设备：键盘，鼠标等 ⚫ 输出设备：显示器，音响等
编程概要 ■GPU编程 Graphics processing unit: is a specialized processor that offloads 3D graphics rendering from the microprocessor Modern GPUs are very efficient at manipulating computer graphics, and their highly parallel structure makes them more effective than general purpose CPUs for a range of complex algorithms 特点 Stream processing( SIMD or MimD,单指令多数据或多指令多数据),适 合并行计算模型 ■具有强大的浮点运算能力,尤其适合数值并行计算 具有独立的内存资源十高速的总线 编程语言:UDA(“ Compute Unified Device Architecture”),NVda公司 行业标准:penC(GP逦用计算的统一标淮 A tutor on coding, Sep 9, 2011 10
10 A tutor on coding , Sep 9, 2011 编程概要 GPU编程 ⚫ Graphics processing unit: is a specialized processor that offloads 3D graphics rendering from the microprocessor ⚫ Modern GPUs are very efficient at manipulating computer graphics, and their highly parallel structure makes them more effective than generalpurpose CPUs for a range of complex algorithms ⚫ 特点： ▪ Stream processing （SIMD or MIMD，单指令多数据 或多指令多数据），适 合并行计算模型 ▪ 具有强大的浮点运算能力，尤其适合数值并行计算 ▪ 具有独立的内存资源＋高速的总线 ▪ 编程语言：CUDA (“Compute Unified Device Architecture”), NVidia公司 ▪ 行业标准：OpenCL（GPU通用计算的统一 标准）