编程概要 图灵机 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通用计算的统一 标准）