###### tags: `university note`
[TOC]

# 計算機概論
Ch1 - Introductions
===

1-1. turning model
---
$Alan\ Turning\ in\ 1936$
:::info
**Define:** All computation could be performed by a special kind of a machine, called a ***Turing Machine***. He based the model on the actions that people perform when involved in computation.
:::
### Program in Turning Model
---
**A program is a set of instructions that tells the computer what to do with data.**
$program+ input\ data\rightarrow output\ data$

a universal Turing machine is capable of computing anything that is computable.(except Non-computable problem : halting problem)

1-2. von neumann model
---

$John\ von\ Neumann\ in\ 1944 - 1945$
:::info
**Define:** It defines the components of a computer, which are **memory**, **I/O**, **control unit**, **ALU** subsystems. **Also, program and data must stored in memory.**
:::
The memory of modern computers hosts both programs and their corresponding data (they are stroed as **binary patterns**).
### four subsystems
---
* Memory: where **programs** and **data** are stored during processing.
* ALU: where **calculation** and **logical operations** take place.
* CU: controls the operations of the memory, ALU, and I/O.
* I/O: **input** - accepts input data and the program. **output** - sends the result of the processing.
___
### execution of instructions
***Sequential execution***
CU fetch instruction $\rightarrow$ decode $\rightarrow$ execute

1-3. computer component
---
:::info
**hardware, data, software**
:::
### program instructions
* **Alogorithms**: solve problem step by step, then try to find the appropriate instruction.
* **Languages**: program in words that ppl used in daily life.
* **Software engineering**: the design and writing of structured programs.
* **Operating systems**: a manager to faciliate access to PC's components by a program.

1-4. history
---
### Mechanical machines(~1930)
* **17th, Pascaline(Blaise Pascal)**, a mechanical calculator for +-calc operations.
* **19th, Jacquard loom(Joseph-Marie Jacquard)**, the first one used the idea of storage and programming
* **1823, Babbage machine**, could solve polynomial equations.
* **1832, Analytical Engine**, similar to modern PC(4 components).
* **1890, a programmer machine(Herman Hollerith)**,could automatically read, tally, and sort data stored on punched cards.
___
### Birth of electronic computer(1930~1950)
not store the program in memory—all were programmed externally
* ABC(first)
* Z1
* Mark1
* Colossus
* **ENIAC**
:::danger
**1950, EDVAC**(Pennsylvania US), the first PC based on von Neumann's ideas. and same as **EDSAC**(Cambridge US)
:::
### Computer generations(1950~now)

**1st GEN(1950~1959)**
* commercial computers(used vacuum tubes as electronic switches)
___
**2nd GEN(1959~1965)**
* transistors instead of vacuum
* high-level programming languages, **FORTRAN, COBOL** made programming easier
___
**3rd GEN(1965~1975)**
* integrated circuit(I/C)
* MiniComputers and Canned programs(software packages) appeared
* software industry $\uparrow$
___
**4th GEN(1975~1985)**
* whole PC subsystems fit on a single IC board
* Altair 8800, the first desktop calculator
* start of PC networks
___
**5th GEN(1985~)**
* laptop and palmtop computers
* secondary strage media(CD-ROM, DVD...), multimedia, VR...
___
Ch2 - Number System
===

2-1. 2-2. Ways of conversion
---
\begin{align}
&b_1\to 10: \sum_{i=0}^{n}(第i位數 \times {b_1}^i) \\
&10 \to b_2: num\div b_2\text{ till result} = 0(fraction\;use\times) \\
&8/10/16 \to 2: \text{convert to 10 and calc} \\
&2 \to 8/16: 8(3dig)\;16(4dig)(\text{if not enough add 0}) \\
&8 \to 16: \text{convert to 2 and use 2 to 8/16} \\
\end{align}

### Number of digit
\begin{align}
b_1\rightarrow b_2 \\
&x\geqslant K \times (\log b_1\div\log b_2) \\
&K: \text{digits stored} \\ &b_1:base_1 \\ &b_2:base_2 \\ &x: digits
\end{align}

2-3. Nonpositional number systems
---

Ch3 - Data Storage
===

3-1. Introduction
---
**Multimedia**

Data is always bit patterns but storage in different data types

$\text{Data}\to\text{compressed}\to\text{storage}$

3-2. Storaging Numbers
---
### Unsigned representation
always nonegative:$0- \infty$, add 0 to full of the bit-limit
e.g. 43 in 8-bit: `00101011`
___
### Sign-and-magnitude representation
range: $\{x|(-2^{n}-1) - (2^{n}-1)\}$
the leftmost bit deside negative or positive
:::danger
double 0 is waste space
:::
___
### Two's complement represntation
Almost all PC's are using, divide two subranges into **nonegative and negative**

**One's Complementing**
`a != a`
**Two's Complementing**
Find the rightmost `1` and ||the rest bits from the position to the left
`(a != a)+1 //-a`
e.g. -28 in 8-bit use Two's Complement
*solve*:

origin: 00011100 //28
two's complement once: 11100100//-28

___
EX3-15:Retrieve the integer that is stored as `11100110` in memory using two’s complement format.
*solve*:

origin: 11100101
two's complenting once: 00011010//26
sign add: -26//answer

___
**Storing reals**
### Floating-point representation
3 parts: sing, shifter, fixed-point
move decimal point till the left digit only have one
e.g. $2,300,000.00\to2.3\times10^6,0.000000232\to2.32\times10^{-7}$
EX3-20: Show the number$(101001000000000000000000000000000.00)_2$ in floating-point representation
solve:$1.01001\times2^{32}$
___
**Normalization**
To make the fixed part of the representation uniform
e.g. $(999)_{10} = /9.99$

:::danger
**The bit 1 to the left of the fixed-point section are not stored**
Mantissa: a fractional part is treated like an integer stored in sign-and-magnitude representation
:::

---
### Excess System
storage exponent in usgined-numbers
e.g. **Excess-7**, we will add 7 to every number
:::danger
important: how many digits can save for every parts
:::
___
e.g. Show the Excess_127 (single precision) representation of the decimal number -161.875.
*solve*:
$-161.875 = (10100001.111)_2$
$(10100001.111)_2 = (1.0100001111)_2\times2^7$
$-\rightarrow1(S),7+127=134\rightarrow10000110(E), 01000011110000000000000(M)$
ans: 11000011001000011110000000000000
___
EX3.26 The bit pattern $(11001010000000000111000100001111)_2$ is stored in Excess_127 format. Show the value in decimal.
*solve*:
sign = -, 10010100(M)=148-127=21, 00000000111000100001111(E)=1.00000000111000100001111
$(1000000001110001000011.11)_2$=2,104,378.75
ans: -2,104,378.75
___
### Overflow and Underflow
**Storing Zero**
sign, exponent, mantissa all set to 0s.

3-3. Storing Text
---
We can represent each symbol with a bit pattern
$\text{number of symbols} = 2^{bits length}$
___
3-4. Storing Audio
---
:::danger
not countable, which cannot store these in the computer’s memory
Audio is an example of **analog data**
:::

**Sampling**
* record some of the audio signal.
* **select only a finite number of points on the analog signal**, measure their values, and record them.
___
**Quantization**
a process that rounds the value of a sample to the closest integer value.
e.g. `round(17.2)=17, round(17.7)=18`
___
**Encoding**
B: bit depth per sample
S: the number of samples per second
R: bit rate
we need to store S × B bits for each second of audio.

e.g. if we use 40,000 samples per second and 16 bits per each sample, the bit rate is
$R = 40,000(B) × 16(S) = 640,000$ bits per second
___
**Standards for sound encoding**
* MP3 (short for MPEG Layer 3) for storing, modification of the MPEG (Motion Picture Experts Group) compression method used for video.
* 44100 samples per second and 16 bits per sample. The result is a signal with a bit rate of 705,600 bits per second.
* discard information that cannot be detected by the human ear, called **lossy compression**
___
3-5. Storing Images
---
### Raster graphics(bitmap graphics)
* store an analog image(ex: photograph)
* the intensity (color) of data varies in space instead of in time.
* scanning(sampleing). The samples are called pixels (picture elements).
___
**Resolution**
how many pixels we need to record for each square or linear inch. The **scanning rate** in image processing is called **resolution**
___
**Color depth**
The number of bits used to represent a pixel, its color depth
RGB: red, green, and blue + intensity
___
**True-Color(255)**
One of the techniques used to encode a pixel is called True-Color, which **uses 24 bits to encode a pixel**
___
**Indexed color(palette color)**
scheme uses only a portion of these colors.
___
**Standards for image encoding**
JPEG (Joint Photographic Experts Group)uses the True-Color scheme
GIF (Graphic Interchange Format), uses the indexed color scheme
___
### Vector graphics
An image is decomposed into a combination of geometrical shapes such as lines, squares, or circles.
:::info
does not store the bit patterns for each pixel
2 disadvantages:
* the file size is big
* rescaling is troublesome
:::
___
3-6. Storing Video
---
Video is a representation of images (called frames) over time
if we know how to store an image inside a computer, we also know how to store video

Ch4 - Operation on Data
===

4-1. Logic Operations
---
NOT, AND, OR are three basic operators
:::danger
`x^y = (x&(!y)|((!x)&y)`
:::
___
### Logic operations at pattern level
The four logic operations can be used to modify a bit pattern.
* Complementing (NOT)
* Unsetting (AND)
* Setting (OR)
* Flipping (XOR)
e.g. use a mask to unset the five leftmost bits(10100110)
`(10100110)&(00000111)=00000111`
e.g. use a mask to set the five leftmost bits(10100110)
`(10100110)|(11111000)=11111110`
e.g. use a mask to flip the five leftmost bits(10100110)
`(10100110)^(11111000)=01011110`
___
4-2. Shift Operations
---
We can divide shift operations into two categories: **logical shift operations** and **arithmetic shift operations**.
:::info
**logical shift operations**: used to shift **bit patterns**
**arithmetic shift operations**: used to **integers**($\times2\div2$)
:::
___
### logical shift operations
e.g. Use a logical left shift operation on the bit pattern 10011000.
`10011000 << 1 = 00110000 //discard the leftmost 1 and add 0 to rightmost`
e.g. Use a circular left shift operation on the bit pattern 10011000.
`10011000 << 1 = 00110001 //move the leftmost 1 to the rightmost`
___
### Arithmetic shift operations
a signed integer in two's complement format.
`a >> 1 same as a/=2, a << 1 same as a*=2`
EX4.12 Use an arithmetic right shift operation on the bit pattern 10011001. The pattern is an integer in two’s complement format.
`10011001 >> 1 = 11001100 //-103 -> -52`
:::danger
EX4.14 Use an arithmetic left shift operation on the bit pattern 01111111. The pattern is an integer in two’s complement format.
`01111111 << 1 = 11111110 // 127 -> -2 because 127*2=254 is overflow`
:::
___
4-3. Arithmetic Operations
---
:::danger
When we do arithmetic operations on numbers in a computer, we should remember that **each number and the result should be in the range** defined by the bit allocation.
:::
Arithmetic operations involve **adding, subtracting, multiplying, and dividing**.
We can apply these operations to integers and floating-point numbers.
___
### Addition and Subtraction
We add integers column by column.
The following table shows the sum and carry (C).
When subtract, we make two's complement of B make it to **+(-B)**.
EX4.16 Show how B is added to A. $A=(00010001)_2,B=(00010110)_2$
17+22=39
___
EX4.18 Show how B is subtracted from A.$A=(00011000)_2,B=(11101111)_2$
24-(-17)=41
___
:::danger
EX4.16 Show how B is added to A.$A=(01111111)_2,B=(00000011)_2$
we expected the ans is 127 + 3 = 130, but the answer is −126.**(due to overflow)**
:::

:::spoiler
4. In two’s complement addition, if there is a final carry after the left
most column addition, _______.
a. add it to the right most column
b. add it to the left most column
c. discard it
d. increase the bit length
**Correct Answer: (c)**
5. For an 8-bit allocation, the smallest decimal number that can be represented in two’s complement form is _______.
a. −8
b. −127
c. −128
d. −256
**Correct Answer: (c)**($-2^{n-1}-2^{n-1}-1$)
10. If we are adding two numbers, one of which has an exponent value
of 7 and the other an exponent value of 9, we need to shift the decimal point of the smaller number _______.
a. one place to the left
b. one place to the right
c. two places to the left
d. two places to the right
**Correct Answer: (c)**
:::
___
Ch5 - Computer Organization
===
5-1. Introduction
---
we can divide computer into three broad catogories:
* CPU
* Memory
* I/O
___
5-2. Central Processing Unit(CPU)
---
CPU performs operations on data.
:::info
**ALU, Control Unit, Registers**
:::
___
### ALU
[Ch4](https://hackmd.io/e_LFrW9vRwCNejetfYR1ZA?view#Ch4---Operation-on-Data)
___
### Registers
Registers are fast stand-alone storage locations that hold data temporarily.
___
### CU
The control unit controls the operation of each subsystem.**(use signals to control)**
:::info
**PC(Program Counter)**:It contains the address of an instruction to be executed next.

**IR(Instruction Registers)**:
it contains the instruction most recently fetched or executed. The fetched instruction is loaded into an IR.
fetch->**store in IR**->decode->execute
(do the instructions one by one from memory)
:::
___
5-3. Main Memory
---

### Address space
The total number of **uniquely identifiable locations in memory** is called the address space.
:::danger
Memory addresses use unsigned binary integers
:::
EX5.1 A computer has 32 MB (megabytes) of memory. How many bits are needed to address any single byte in memory?
$32=2^5,MB=2^{20}bytes$
$2^5\times2^{20}=2^{25}$
we need 25 bits.
___
EX5.2 A computer has 128 MB of memory. Each word in this computer is eight bytes. How many bits are needed to address any single word in memory?
$128=2^7, MB=2^{20}bytes$
$2^7\times2^{20}\div2^3=2^{24}$
we need 24 bits.
___
### Memory Types
:::info
**RAM(Random Access Memory)**:SRAM, DRAM
**ROM(Read-Only Memory)**:PROM, EPROM, EEPROM
:::
RAM: makes up most of the main memory in a computer. **A data can be accessed randomly by located memory addresses**.
ROM: CPU can read, but can't write. It's **nonvolatile**, its contents are not lost if you turn off the computer(**e.g. boot program**)
___
### Memory Hieratchy
Fast memory is usually not cheap
___
### Cache Memory
Cache memory is fater than main memory, is placed between the CPU and main memory.
___
5-4. I/O
---
Allows a computer to **communicate with the outside devices**, and **to store programs and data when the power is off**.
:::info
**non-storage** and **storage** devices
:::
___
### Non-Storage Devices
Allow the CPU/memory to communicate with outside.(**they cannot store information**)

e.g. Mouse/Keyboard/Printer
___
### Storage Devices(I/O)
Store large amounts of information. Their contents are **nonvolatile**.
They are sometimes referred to as **auxiliary storage devices(輔助儲存體)**.
:::info
**magnetic, optical**
:::
___
#### Magnetic
It consists of one or more disks stacked on top.
Data are stored and retrieved from the surface of the disk using Read/Write head.

**Magnetic Disk(HDD傳統硬碟)**
* Surface organization
* Track
* Sector(Ths smallest area can be accessed is a sector)
* Cylinder
* Data access(RAM)
* Performance
* Seek time(the time move R/W head to desired track)
* Rotation time
* Transfer time(the time data to CPU/Memory)


**Magnetic Tape(磁帶)**
Track1~9=1bit check code+8bit data
___
#### Optical
Use laser light to store and retrieve data.

**CD-ROM**
(Pits=0s, land=1s)
8bits -> 14bits(**Hamming Code**)

**CD-R**
It's called **WORM(Write Once Read Many)**
(Dark dye=0s)

**CD-RW**
It can erase by medium-power lasers

**DVD**
___
5-5. Subsystems Interconnection
---
### CPU,Memory,I/O Connecting
The CPU and memory are normally connected by three groups of connections, each called a bus: **data bus, address bus, and control bus**
___
I/O are much slower than CPU and Memory. Therefore, we need controllers or interfaces to handle the difference.
**Each devices have specific controllers.**
### Common Controller
#### SCSI(Small Computer System Interface)
It has a parallel interface with8,16,or 32 connections
#### FireWire
It can connect up to 63 devices in a **daisy chain(each one only one connection)**
#### USB(Universal Serial Bus)
It allows up to 127 devices(USB2.0)
___
### Addressing I/O Devices
:::info
**Isolated I/O**: more instructions, but less address
**Memory-mapped I/O**: less instructions, but more address
:::
___
5-6. Program Execution
---
### Machine cycle
A simplified cycle can consist of three phases: **fetch, decode, and execute**
___
### I/O Operation
Commands are required to transfer data from I/O devices to the CPU and memory
:::info
**Programmed I/O. Interrupt driven I/O, DMA(Direct Memory Access)**
:::
#### Programmed I/O
During I/O processing, CPU check device status (**CPU won't work in the duration**)
___
#### Interrupt-driven I/O
CPU time is not wasted. When I/O is ready to transfer data, I/O interrupt CPU to transfer data. (**CPU can do something else while the I/O device is finishing a task**)
___
#### DMA input/output
**CPU called a DMA Controller to do I/O**, and CPU can do anything else.
When DMA Controller ready to transfer, it called CPU to control the buses(**CPU will idle while transfering data to memory**)
I/O$\rightarrow$DMA$\rightarrow$Memory
Memory$\rightarrow$DMA$\rightarrow$I/O
___
5-7. Different Arichitectures
---

### CISC(Complex Instruction Set Computer)
have a large set of instructions for both simple and complex tasks.
**Programmers therefore do not have to write a set of instructions to do a complex task.**
### RISC(Reduced Instruction Set Computer)
have a small set of instructions that do a minimum number of simple operations **most of the complex instructions are simulated using simple instructions**.
### Pipelining
**Faster to fetch, decode, and execute**
The idea is that if the control unit can do two or three of these phases simultaneously, the next instruction can start before the previous one is finished

### Parallel Processing
today we can have a single computer with multiple control units, multiple arithmetic logic units and multiple memory units.
___
5-8. A Simple Computer
---
Assuming we have a simple computer that can do instruction processing

### Instruction set
This computer has a set of 16 instructions(**Acutually it's defined by the size of computer**)
Each instructions consists of **opcode** and **operand**

### Processing the Instructions
**fetch**
the instruction whose address is determined by the PC is obtained from the memory and **loaded into the IR**. The **PC is then incremented to point to the next instruction**.
**decode**
instruciton in IR is decoded and required operands from the register or memory
**execute**
the instruction is executed and the results are placed in the appropriate memory location or the register.
___
**Example**
We can I/O by keyboard and monitor
* 1~4: Input data by keyboard
* 5~8: calculate and put the result in memory
* 9~10: display result on monitor and halt the process
:::danger
The input operation must always read data from an input device into **memory**: the output operation must always write data from **memory** to an output device.
:::
:::spoiler
4. A register in a CPU can hold _______.
a. only data
b. only instructions
c. only program counter values
d. data, instruction, or program counter values
**Correct Answer: (d)**
5. A control unit with five wires can define up to _______ operations.
a. 5
b. 10
c. 16
d. 32
**Correct Answer: (d)**
$2^5=32$
9. _______ is a memory type with capacitors that need to be refreshed
periodically.
a. SRAM
b. DRAM
c. ROM
d. CROM
**Correct Answer: (b)**
11. There are _______ bytes in 16 Terabytes.
a. $2^{16}$
b. $2^{40}$
c. $2^{44}$
d. $2^{56}$
**Correct Answer: (a)**
15. A _______ is a storage device to which the user can write information only once.
a. CD-ROM
b. CD-R
c. CD-RW
d. CD-RR
**Correct Answer: (b)**
20. A _______ controller is a high-speed serial interface that transfers
data in packets.
a. SCSI
b. USB
c. FireWire
d. USB and FireWire
**Correct Answer: (d)**
22. In the _______ method for synchronizing the operation of the CPU
with an I/O device, the I/O device informs the CPU when it is ready
for data transfer.
a. programmed I/O
b. interrupt-driven I/O
c. DMA
d. isolated I/O
**Correct Answer: (b)**
23. In the _______ method for synchronizing the operation of the CPU
with an I/O device, the CPU is idle until the I/O operation is finished.
a. programmed I/O
b. interrupt-driven I/O
c. DMA
d. isolated I/O
**Correct Answer: (a)**
24. In the _______ method for synchronizing the operation of the CPU
with an I/O device, a large block of data can be passed from an I/O
device to memory directly.
a. programmed I/O
b. interrupt-driven I/O
c. DMA
d. isolated I/O
**Correct Answer: (c)**
:::
___
Ch6 - Computer Networks and Internet
===
6-1. Overview
---
### Network
A network is the interconnection of devices capable of communication.
Device can be:
* host(Computers, laptops, smartphones, security system...)
* connecting devices
* router(路由器):make LAN
* switch(交換器):increas numbers of LAN port
* modem(數據機):connect to WAN
___
**Local Area Network(LAN)區域網路**
A local area network (LAN) is privately owned and connects hosts in a single office, building, or campus.
Each host in a LAN has an identifier, an address.
**Wide Area Network(WAN)公共網路**
A wide area network (WAN) is an interconnection of devices capable of communication.
**A point-to-point WAN** is a network that connects two communicating devices through a transmission medium (cable or air).
**A switched WAN** is a network with more than two ends.(used in global communication today)
___
:::info
**Difference between LAN and WAN**
* LAN is limited to size; WAN has a wider geographical span
* LAN interconnects hosts; WAN interconnects connecting devices such as switches, routers, or modems.
* LAN is normally privately owned; WAN is normally created and run by communication companies
:::
___
**Internet**
WAN and LAN are connected to one another. When two or more networks are connected, they make an internetwork, or internet.
A internet which is made of thousands of networks
* Backbones: large networks owned by communication companies
* Provider networks: Smaller networks. They use the services of the backbones for a fee.
* Customer networks: use the services provided for a fee.
**Backbones and Provide networks are called Internet Service Providers(ISPs)**
___
### Protocol layering
**A protocol defines the rules** that both the sender and receiver and all intermediate devices need to follow to be able to communicate effectively.

When communication is simple, we might only need one protocol
if it's complex, **we divide the task in different layers, we need a protocol at each layers.**
___
**Example**
Advantages:
* Separation of the services from the implementation.(分散分別處理)
* Communication does not always use only two end systems; there are intermediate systems that need only some layers, but not all layers(省錢非所有都需要即時性)
___
### Principles of Protocol Layering
1. Each later can perform 2 opposite tasks
2. Same layer shouuld get same types of objects
___
### TCP/IP Protocol Suite
TCP/IP is a protocol suite (a set of protocols organized in different layers) used in the Internet today.
It is a **hierarchical protocol** made up of interactive modules, each of which provides a specific functionality.

TCP/IP can divide into 5 layers:
___
**Addressing and Packets Name**
Communication involving two parties **needs two addresses: source and destination**
___
6-2. Application Layer
---
The fifth layer of the TCP/IP protocol is called the application layer; **it provides services to the user.**

* Protocols in this layer **only receive services from the protocols in the transport layer**.
* It's allows new application protocols to be easily added to the Internet.
* Application layer ius the only layer that provides services to users.
___
### Application-layer Paradigms
both application programs be able to request services and provide services
:::info
***the client–server paradigm(Traditional)***:
**server process** wait **client process** to make a connection through the Internet and ask for service.
**We cannot run a client program as a server program or vice versa**
World Wide Web (WWW) and its vehicle HyperText Transfer Protocol (HTTP), file transfer protocol (FTP), secure shell (SSH), email... use this paradugim.
___
***the peer-to-peer paradigm(New): also called P2P***
No need for a server process.**The responsibility is shared between peers.**
**A computer can provide and receive services at the same time.**
It's **Easily scalable and Cost-effective.**
:::
**Challenges**
Client-server:
* the concentration of the communication load is on the shoulder of the server, which means **the server should be a powerful computer**.
* **overwhelmed** if a large number of clients try to connect at the same time.
* create a powerful server for a specific service cost a lots.

P2P:
* Security – secure connections are harder to ensure.
* Applicability – not all applications can use this paradigm
___
### WWW and HTTP
**WWW**
* Distribution: Web pages(documents) are distributed over the world and related documents are linked together.
* Linking: linking of web pages was using **hypertext(hypermedia)**
* Many locations called **sites** hold one or more web page.
Each web page is a file with a name and address.
___
**Web Client(browser)**
:::info
browser consists of: **controller, cilent protocols, and interpreters**
:::
* controller: receives input from input devices and uses the client programs.
* client protocols: HTTP/FTP
* interpreter: to make the document can display on the screen. It can be **HTML, Java, Javascript**

**Web Server**
Web pages are stored at the server.
Sent corresponding doccuments to clients that requests.
___
**Uniform Resource Locator(URL)**
A web page has a unique identifier that distinguishes it from other web pages.
:::info
Three identifiers are needed: **host, port, and path**
:::
* Protocol: the first identifier.
* Host identifier: can be the **IP address** or the **unique name** given to the server.
* Port number: a 16-bit interger,is normally predefined for the **client–server application**.
* Path: The path identifies the location and the name of the file.
___
**HTTP(HyperText Transfer Protocol)**
HTTP define how the client-server program can be written to retrieve web pages from the Web.

* An HTTP client sends a request; an HTTP server returns a response.
* **The server uses the port number 80**; the client uses a temporary port number.
:::warning
WWW v.s HTTP
**HTTP is a protocol** which enables communication and data transfer online from one machine to another.
**WWW is a set of linked hypertext documents**, viewable on web browsers.
:::
___
### FTP(File Transfer Protocol)
FTP is the standard protocol provided by TCP/IP for **copying a file from one host to another.**

Separation of commands and data transfer makes FTP more efficient.
* Conrtol connections get or response a command.
* Data connections can transfer different data types.

Control connection remains connected during the entire FTP session.
Data connection is closed for each file transfer activity is finished.
___
### Email and TELNET
**Email**
Email is considered a **one-way transaction**
The server program is running all the time, waiting for a request from a client. The users run only client programs, and the **intermediate servers** apply the client/server paradigm.
___
**TELNET(TErminaL NETwork)**
A client can remote controll server by logining program.
TELENT is vulnerable to hacking because it sends all data including the password in plaintext.

**SSH(Secure Shell)加密過的telnet**
SSH is a secure application can be used in many purposes.
**e.g.: remote logging and file transfer.**
___
### DNS(Domain Name System)
The Internet has a **directory system that can map a name to an address.**

DNS now is distribute among many computers to **avoid the central computer failed**. Also the host can contact the nearest DNS.
___
**Name Space**
A name space with complete control over the **binding between the names and IP addresses.**

A name space can map each address to a unique name and is **normally organized hierarchically**.
___
**DNS in Internet**
:::info
In internet, **domain name space (tree)** is divided in threesections:
**generic domains, country domains, and the inverse domain.**
:::
**Generic Domains**
Define registered hosts according to their generic behaviour.
**Country Domains**
The country domains section uses two-character country abbreviations(TW, US, JP...)
___
### P2P Paradigm
**Centralized Networks(主從式網路)**
The directory system listing of the peers and what they offer uses the **client–server** paradigm. Storing and downloading files use the **P2P paradigm**
It make the maintenance of the directory simple.

Drawbacks:
* Accessing the directory can generate huge traffic and slow down the system.
* **The central servers are vulnerable to attack**, and if all of them fail, the whole system goes down.
___
**Decentralized Networks(分散式網路)**
Peers arrange themselves into an **overlay network**
:::info
Decentralized Network is classified as(by how the nodes connect):
**unstructured** or **structured**
:::
**Srtuctured P2P**
A structured network uses a predefined set of rules to link nodes. It's more effective and efficient.
:::info
e.g. **Distributed Hash Table (DHT)**
provides a lookup services similar to **Hash Table**.
**One popular P2P file sharing protocol that uses the DHT is BitTorrent.**
:::
**Unstructured P2P**
In an unstructured P2P network, the nodes are linked randomly. **A search in this network is not efficient(the search must be flooded through the network).**
___
6-3. Transport Layer
---
* It provides services to the application layer and receives services from the network layer.
* The transport layer acts as a liaison between a client program and a server program, a process-to-process connection

**The transport layer is the heart of the TCP/IP protocol suite**
___
### Transport-layer Services
A **network-layer protocol can deliver the message only to the destination computer** but we have to know which process.
**Process-to-process Communication**
:::info
**A process** is an application-layer entity (running program) that uses the services of the transport layer.
:::
A transport-layer protocol is responsible for **delivery of the message** to the appropriate process

**Addressing**
:::info
**First identifiers**: local host, local process, remote host, remote process
**Second identifier: port numbers**
Port numbers are integers between 0 to 65535(16bits)
:::
The **client program** defines itself with a port number, called the **ephemeral port number.(1024~49151 Registered, 49152~65535 Dynamic)**
TCP/IP has decided to use universal port numbers for servers; **well-known port numbers(0~1023)**.
___
### Transport-layer Protocols
**UDP(User Datagram Protocol)**
* UDP is a **connectionless, unreliable** transport protocol.
* **UDP packets, called user datagrams**, have a fixed-size header of 8 bytes.
* The total length needs to be less because a UDP user datagram is stored in an IP datagram with the total length of 65 535 bytes.
:::danger
**UDP takes less interaction between the sender and receiver than using TCP**
:::
___
**TCP(Transmission Control Protocol)**
* TCP is a **connection-oriented, reliable** protocol.
* TCP explicitly defines connection establishment, data transfer, and connection teardown phases to provide a connection-oriented service.
* TCP uses **sequence numbers** to define the order of the segment
* If segment is lost, receiver will wait untill the lost one is resent by sender.
TCP adds a header and **delivers the segment to network layer for transmission**
___
:::warning
**TCP v.s UDP**
[TCP 和UDP 是什麼：簡單的說明 - NordVPN](https://nordvpn.com/zh-tw/blog/tcp-udp-bijiao/)
[連接與非連接伺服架構](http://www.tsnien.idv.tw/Internet_WebBook/chap10/10-5%20%E9%80%A3%E6%8E%A5%E8%88%87%E9%9D%9E%E9%80%A3%E6%8E%A5%E4%BC%BA%E6%9C%8D%E6%9E%B6%E6%A7%8B.html)
:::
___
6-4. Network Layer
---
Network Layer is respomsible for the **host-to-host delivery of messages.**
___
### Services
**Packetizing**
Encapsulating the payload (data received from the upper layer) in a network-layer packet at the source.
Decapsulating the payload from the network-layer packet at the destination.
:::danger
A transport layer payload may be encapsulated in several network layer packets.
:::
**Routing**
Routing means selecting the best path for sending a packet from one point to another, when more than one path is available.
___
**Packet Delivery**
:::info
**Unreliable Delivery**
The delivery of packets at the network layer is unreliable. They might **lost, duplicated, corrupted...**

**Connectionless Delivery**
Each packet being treated independently.
**Packets may take different paths and arrive in a different order than sent.**
:::success
Use TCP protocol can make the patcket order correct but need more time
:::
:::
___
### Network-layer Protocols
**IPv4(Internet protocol version 4)**
* Identifier in IPv4 of TCP/IP protocols is **IP adress**
* An IPv4 address is a **32-bit address.**

Common notations to show IPv4 address can be:
**base2,16,256.**
:::info
32-bits IPv4 can divide into two parts:
**prefix(network), suffix(node)**
:::
**IPv4 Datagram**
Packets used by the IP are called datagrams.
The header is **20 to 60 bytes** in length and **contains information essential to routing and delivery.**
___
**IPv6(Internet protocol version 6 )**
To prevent address depletion, **IPv6 uses 128 bits** to define any device connected to the Internet.
:::info
128-bits IPv6 can divide into three parts:
**site, subnetwork, connection**
:::
**IPv6 Datagram**
___
6-5. Data-link Layer
---
These **networks, wired or wireless**, receive services and provide services to the network layer.
Communication at the data-link layer is **node-to-node.**
Two end hosts and the routers as nodes and the networks in between as links.
___
### LAN
**Wired LANs(Ethernet)**
* 10Mbps is the **Standard Ethernet**
* A group of bits are packaged together and are referred to as a **frame**.
:::warning
* **CRC is check code**
* the source and destination adress is **MAC Address**
* 透過CSMA/CD(Carrier Sense Multiple Access with Collision, IEEE 802.3)的設計，**訂定出了網路的封包大小最小為64bytes；最大為1518bytes**，來避免封包碰撞的現象。

[網際網路 乙太網路封包格式(MAC Frame Format)](https://bryceknowhow.blogspot.com/2013/12/mac-frame-format.html)
:::
Fast Ethernet (100Mbps)->Gigabit Ethernet(1000Mbps)->10-Gigabit Ethernet(**fibre-optic technology**)
___
**Wireless LANs**

WiFi(Wireless Ethernet)
:::info
The standard defines two kinds of services:
**BBS(Basic service set), ESS(Extended service set)**
ESS use AP that serves as a switch for connection to other LANs or WANs
:::

Bluetooth
* Bluetooth is a wireless LAN technology
* Bluetooth connects devices of different functions **in a short distance**
* Bluetooth LAN is an ad hoc network the devices find each other and make a network called a **piconet**.
___
### WAN
**Wired WANs**

Dial-up service(撥號連線)
* A dial-up network or connection **uses the services provided by the telephone networks** to transmit data frame.
* The need to communicate digital data resulted in the invention of the dial-up modem.

DSL(Digital Subscriber Line數位用戶線路)
* DSL technology is a set of technologies(ADSL, VDSL, HDSL, and SDSL).
* ADSL provides higher speedin the downstream direction than in the upstream direction(下行速度通常較上行速度快)

Cable network(有線電纜上網)
* Cable companies compete with telephone companies for customers who want **high-speed data transfer**.
* DSL uses the existing **unshielded twisted-pair cable**(UTP無遮蔽雙絞線) is **susceptible to interference**(利用電磁感應相互抵銷的原理封鎖電磁干擾). This imposes an upper limit on the data rate.
___
**Wireless WANs**
WiMax(Worldwide Interoperability Acces全球互通微波存取)
* WiMax is the wireless DSL or Cable connections
* It provides two types of services (fixed WiMax) to connect the main station to **fixed station** or **mobile stations**

Cellular telephony network(蜂巢式網路)
Mobile stations communicate with the fixed antenna in the cell that they are inside at each moment.
The phone will communicate with 1st to 3rd antenna in the pic.

Satellite networks
* It's a combination of nodes, satellites provide communication from one point on the Earth or to another.
* A **node in the network can be a satellite, an Earth station, or an end-user terminal or telephone**.
___
6-6. Physical Layer
---
Physical layer transfer received bits and **convert them to electromagnetic signals** for transmission.
___
### Data and Signals
**Analog data**
Analog data refers to **information that is continuous.**
**Digital data**
Digital data take on **discrete(分開的) values.**
___
### Transmission
**Digital-to-digital conversion**
**Analog-to-digital conversion**
**Digital-to-analog conversion**
**Analog-to-analog conversion**
___
6-7. Transmission Media
---
Transmission media **are directly controlled by the physical layer.**
A **transmission medium(傳輸介質)** can be broadly defined as anything that can carry information from a source to a destination.
___
### Guided Media
**Twisted-pair cabel(雙絞線)**
* A twisted-pair consists of two conductors(導體), each with plastic insulation(絕緣)
* One carries signals, the other use as a **grounded reference**.

e.g. DSL lines, RJ-45
___
**Coaxial Cable(同軸電纜)**
* A central core conductor of wire in an insulating sheath and encased in a conductor.
* Outer conductor can **decrease noise** and as second conductor.
* Plastic cover protect outer conductor.

一條普通（RG-59）的同軸電纜 A：電線外皮 B：網狀導電層 C：塑膠絕緣體 D：中心的銅線

e.g. Cable TV networks,
___
**Fiber-optic cable(光纖電纜)**
* Made of glass or plastic and **transmits signals in the form of light.**
* It's use the light is refracted one less desity medium.
* Fibre-optic cable **is often found in backbone networks** because its wide bandwidth(頻寬) is cost-effective.
___
___
### Unguided Media(Wireless)
Unguided media transport elecrtomagnetic waves **without using a physical conductor.**
**Radio wabes(無線電波)**
* Electromagnetic waves **frequencies between 3 kHz and 1 GHz.**
* They are used mostly for **radio communication.**
___
**Microwaves(微波)**
* Electromagnetic waves **frequencies between 1 GHz and 300 GHz**
* Microwaves are **unidirectional**. When an antenna transmits microwaves, they can be narrowly focused.
___
**Infrared(紅外線)**
* Electromagnetic waves **frequencies between 300 GHz and 400 GHz.**
* Can be used for **short-range communication.**
* Cannot penetrate walls.(hard for long-range communication)
* **Cannot be used outdoors** as the sun’s waves can interfere with the communication.
___
___
:::spoiler
4. The _______ layer of the TCP/IP protocol suite is responsible for node-to-node delivery of a **frame** between two adjacent nodes.
a. transport
b. network
c. data-link
d. session
**Correct Answer: (c)**
5. The _______ layer of the TCP/IP protocol suite is responsible for source-to-destination delivery of the entire message.
a. transport
b. network
c. data-link
d. session
**Correct Answer: (b)**
7. Which **physical topology(拓樸圖)** uses a hub or switch?
a. bus
b. ring
c. star
d. bus and ring
**Correct Answer: (c)**

### Physical Topology(區域網路的拓樸圖)
**Bus**:
* Adv:
* Inexpensive, easy to install
* Widely used in small LANs.
* Disad:
* If one common cable failed, entire system will crash.
* When network traffic is heavy, it develops collisions in the network.

**Ring**:
* Adv:
* Offers equal access to all the computers of the networks
* Good to use on high loads network
* Disad:
* Break in a single ring can risk the breaking of the entire network
* In the ring, topology signals are circulating at all times, which develops unwanted power consumption.
* It is very difficult to troubleshoot the ring network.

**Star**:
* Adv:
* Easy to troubleshoot, set up, and modify.
* Fast performance with few nodes and very low network traffic.\
* Disad:
* If the hub or concentrator fails, attached nodes are disabled.
* Cost of installation of star topology is costly.

:::
___
Ch7 - Operating System
===
7-1. Introduction
---
畫圖
### Operating system
:::info
* An interface between the hardware and programs or humans
* Can be a program or a set of programs.
* Facilitates the execution of other programs.
:::
Control the access to hardware by users.

Goals for Operation system are:
* Efficient use of hardware
* Easy use of resources.(software)
___
### Bootstrap process
It can be **two-stage-process or three-stage-process**(we discuss the first one here)

A small section of memory hold a program **bootstrap program*(ROM)**

___
7-2. Evolution
---
### Batch systems(批次處理系統)
:::info
Batch operating systems **were designed in the 1950s to control mainframe computers.**
:::
Each program to be executed called **job**
The operating systems ensured that all computer resources transferred from one job to another.
**Charcteristic:**
* 提高處理器的使用率
* 不宜處理具時效性資料
___
### Time-sharing systems(分時處理系統)
**Multiprogramming**
Hold several jobs in memory at a time, and only assign a resource to the jobs needed.
**Time-Sharing**
Each job allocated a portion time to use a resource.
___
### Personal systems(個人系統)
When PC was introduced, Operating systems such as **DOS (Disk Operating System)** were introduced.
___
### Parallel systems(平行處理系統)
* Multiple CPUs on the same machine(多核心電腦)
* Each CPU can be used to serve one program or a part of a program.
* Operating systems are more complex
___
### Distributed systems(分散式系統)
:::info
can be **Networking** and **internetworking**
:::
A job can now be shared between computers that may be thousands of miles apart.
___
### Real-time systems(即時系統)
Do a task within specific time contraint

[作業系統-NUTNCSIE10412](https://sites.google.com/site/nutncsie10412/ge-ren-jian-jie/zuo-ye-xi-tong)
___
7-3. Components
---
:::info
A modern operating system has at least four duties:
**memory manage, process manager, device manager, and file manager.**
:::
___
### User Interface(UI)
A program that accepts requests from users (processes) and interprets them

GUI(Graphical User Interface)讓使用者更能接受電腦視覺

e.g. UNIX-shell
___
### Memory Management
**Memory allocation** must be managed to prevent applications from running out of memory.
:::info
**Monoprogramming**
the whole program is in memory for excution, **programs execute one by one.**
* <font color=red >程式所需記憶體可能太大放不下</font>
* <font color =red>程式運行太久很沒效率 e.g.程式需I/O花很多時間等而不能先執行下一個</font>
___
**Multiprogramming**
more than one program is in memory at the same time, and they are **executed at same time.**
:::

### Multiprogramming

#### Partioning
Memory manger determined the size of partitions and for program. **PC will move to next program if encounter I/O or allocated time over**
* 先訂好的size可能太大或太小導致浪費或放不下
* 後面補上來的program可能會導致新的浪費但重新配置浪費時間
___
#### Paging
Program divided into pages, memory divided into frame. **No need to wait contiguous frames size for all pages in a program**(但要一個program的所有pages都在裡面才能運作)
___
#### Demand Paging
大致跟Paging相同(但不用所有pages都在frame才能運作)
___
#### Demand Segmentation
跟Demand Paging類似(pages->**Main + sub program**, Frame->**Segment**)
若Segment太大還能分割成page+frame放進去
https://ithelp.ithome.com.tw/articles/10207797
___
### Virtual Memory
**Part of the program is in memory and part is on disk**(Demand Paging+Segmentation)
e.g. 10 programs=30MB -> 10MB in memory, 20MB in disk(30MB virtual memory)
___
### Process Manager
program(**disk**)$\rightarrow$job(**operating system selected**)$\rightarrow$pocess(**memory**)

#### State Diagram
___
#### Schedulers(排程系統)
To move a job or process from one state to another.(process優先度)
___
#### Queing
**Job/Process control block** which store job/process information in the queues.(排隊等待被執行)

___
#### Processes Synchronization
:::info
**deadlock, starvation**
:::
**Deadlock**(資源分配不全)
:::danger
Deadlock occurs when the **operating system does not put resource restrictions on processes**.
:::
___
**Starvation**(資源搶奪)
A process can never get what it need due to other processes also need the resource.
:::danger
Starvation is the opposite of deadlock. It can happen **when the operating system puts too many resource restrictions on a process.**
:::
___
### Device Manager(I/O Manager)
* 監控I/O devices
* queue去管理I/O順序
* 不同I/O devices有不同管理法

___
### File Manager
* control access to files.
* files naming, creation, deletion. and modification.
* (備份與存取)
___
7-4.
---
Brifely introduce **UNIX, LINUX, WINDOWS**
___
### UNIX
:::info
**Developed in 1969 by Bell Laboratories.**
:::danger
multiusers, multiprocessing, portable operating system
:::
:::
#### Kernel
**have four management**, all other components call Kernel to perform services.
#### Shell
Get commands and **request Kernel to run programs.**
#### Utilites
**standard UNIX program** that povides a support process for users.
#### Applications
programs written by unofficial UNIX programmers.
___
### LINUX
similar to a small subset of UNIX
#### Components
:::info
Linux has three components: **kernel, system libraries(API), and system utilities(system program).**
:::
___
### WINDOWS
a single-user operating system(to replace MS-DOS)

**為提高擴充、便利、信用、兼容性**
___
:::spoiler
7. _______ is a multi-programming method in which multiple programs are entirely in memory with each program occupying a contiguous space.
a. Partitioning
b. Paging
c. Demand paging
d. Demand segmentation
Correct Answer: (a)
:::
10. In _______, the program can be divided into equally sized sections
called pages, but the pages need not be in memory at the same time
for execution.
a. partitioning
b. paging
c. demand paging
d. demand segmentation
Correct Answer: (c)
11. A process in the _______ state can go to either the ready, terminated,
or waiting states.
a. hold
b. virtual
c. running
d. hold or running
Correct Answer: (c)
15. The _______ scheduler creates a process from a job and changes a
process back to a job.
a. job
b. process
c. virtual
d. queue
Correct Answer: (a)
___
Ch 8 - Algorithms
===
8-2. Three Constructs
---
:::info
Three Constructs:
**Sequence(做啥敘述), Decision(if-else), Repetition(while, for)**
:::
___
8-3. Algorithm Representation
---
#### UML
#### Psudocode
___

Ch9. Programming language
===
9-1. Evolution
---
:::info
**Machine language -> Assembly language -> High-level language**
:::
Computer language is a set of instructions according to predefined rules(syntax)

### Machine language
每個電腦系統都有自己的機器語言(0s and 1s)
:::danger
The only language understood by a computer is machine language
:::
___
### Assembly language
指令(symbols)+Memory address(需有些許硬體理解)
___
### High-level language
Goals: 讓所有人都能寫程式(集中在解決問題上not硬體)
e.g.: BASIC, COBOL, Pascal, C, C++, JAVA
___

9-2. Translation
---
Translated **source program** into **object program(machine language)**
:::info
two meethods:
**compilation, interpretation**
:::
___
### Compilation
整個程式編譯成object programs(全部編譯完執行)
### Interpretation
一行一行編譯且執行(邊編譯邊做)
e.g.: **Java bytecode**
___
### Translation Process
#### Lexial analyzer
關鍵字 -> tokens(`while <- check關鍵字`)
#### Syntax analyzer
檢查語法 e.g. `int x; x =; error cuz = not have operand`
#### Semantic analyzer
檢查語意 e.g.`int a; char b; a/b; might error cuz int/char type`
___
9-3. Programming Paradigms
---
:::info
**procedural, object-oriented, functional, declarative**
:::
___
### Procedural Paradigms
程式處理資料(資料"被"處理 無延伸出物件引導程式處理)
e.g.: array存取
### Object-oriented Paradigms
The action to be performed on these objects are included in the object.(物件型態影響處理方法(function))
e.g.: struct,container
#### Encapsulation
#### Inheritance
#### Polymorphism
:::spoiler
7. _______ is a common language in the business -environment.
a. FORTRAN
b. C++
c. C
d. COBOL
Correct Answer: (d)
9. A _______ program can be either an application or an applet.
a. FORTRAN
b. C++
c. C
d. Java
Correct Answer: (d)
11. Prolog is an example of a(n) _______ language.
a. procedural
b. functional
c. declarative
d. object-oriented
Correct Answer: (c
:::
___

Ch10. Software Engineering
===
10-1. Software Lifecycle
---
#### Waterfall model
* 一次只做其中一部分
* 可能其中一個爛掉後面要等前面修好才能繼續做
___
#### Incremental model

___
10-4. Implementation
---
:::info
目的為維持軟體品質
#### Quality factors:
Operability(可操作性), Maintainability(可維護性), Transferability(轉移性)
:::
### 一些特別的性質
#### Timeliness
#### Usability

___

10-5. Testing
---
#### Purpose: To find errors
___
### Glass-box-testing(白箱測試)
測試程式碼有無語意或想法錯誤(?
#### Basis path testing
程式碼的每種可能都至少測試一遍
#### Control structure testing
比`Basis path testing`更廣泛測試
* Condition testing(條件測試)
* Data flow testing
* Loop testing
___
### Black-box-testing(黑箱測試)
* Exhaustive testing(TLE test)
* Random testing
* Boundary-value testing
___
10-6. Documentation
---
* User Documentation(使用者手冊)
* System Documentation(System使用手冊)
* All 4 phases must have
* Technical Documentation(system修復安裝手冊)
___
:::spoiler
2. Defining the users, requirements, and methods is part of the _______
phase.
a. analysis
b. design
c. implementation
d. testing
Correct Answer: (a)
6. _______ is the breaking up of a large project into smaller parts.
a. Coupling
b. Incrementing
c. Obsolescence
d. Modularization
Correct Answer: (d)
7. _______ is a measure of how tightly two modules are bound to each
other.
a. Modularity
b. Coupling
c. Interoperability
d. Cohesion
Correct Answer: (b)
8. _______between modules in a software system must be minimized.
a. Coupling
b. Cohesion
c. Neither coupling nor cohesion
d. Both coupling and cohesion
Correct Answer: (a)
:::
Ch11. Data Structure
===
xxxxxxxxxxxxxxxxxx

:::spoiler
3. Each element in a record is called _______.
a. a variable
b. an index
c. a field
d. a node
Correct Answer: (c)
4. All the members of a record must be _______.
a. the same type
b. related types
c. integer type
d. character type
Correct Answer: (b)
9. An empty linked list consists of _______.
a. a node
b. two nodes
c. data and a link
d. a null head pointer
Correct Answer: (d)
10. To traverse a list, you need a _______ pointer.
a. null
b. walking
c. beginning
d. insertion
Correct Answer: (b)
:::
___
Ch12. ADT
===
xxxxxxxxxxxxxxxxxx

:::spoiler
1. In an abstract data type, _______.
a. the ADT implementation is known
b. the ADT implementation is hidden
c. the ADT public operations are hidden
d. Nothing is hidden
Correct Answer: (b)
6. The pop operation _______ of the stack.
a. deletes an item from the top
b. deletes an item from the bottom
c. inserts an item at the top
d. inserts an item at the bottom
Correct Answer: (a)
___
8. In a binary tree, each node has _______ two subtrees.
a. more than
b. less than
c. at most
d. at least
Correct Answer: (c)
9. In preorder traversal of a binary tree, the ______.
a. left subtree is processed first
b. right subtree is processed first
c. root is processed first
d. the root is never processed
Correct Answer: (c)
10. In _______ traversal of a binary tree, the right subtree is processed
last.
a. preorder
b. inorder
c. postorder
d. any order
Correct Answer: (b)
11. In postorder traversal of a binary tree, the root is processed _______.
a. first
b. second
c. last
d. after the left subtree
Correct Answer: (c)
13. In _______ traversal of a binary tree, the left subtree is processed
last.
a. preorder
b. inorder
c. postorder
d. out of order
Correct Answer: (a)
14. In an inorder traversal of a binary tree, the root is processed
_______.
a. first
b. second
c. last
d. two times
Correct Answer: (b)
:::
___
Ch17. Theory of Computation
===
xxxxxxxxxxxxxxxxxx
:::spoiler
4. To clear a variable, we use the _______ statement(s).
a. increment
b. decrement
c. loop
d. decrement and loop
Correct Answer: (d)
5. To assign a number to a variable, we use the _______ statement(s).
a. increment
b. decrement
c. loop
d. decrement and loop
Correct Answer: (a)
6. To copy the value of one variable to another, we use the ____ statement(s).
a. increment
b. decrement
c. loop
d. increment, decrement, and loop
Correct Answer: (d)
___
7. A Turing machine has these components: _______.
a. tape, memory, and read/write head
b. disk, controller, and read/write head
c. tape, controller, and read/write head
d. disk, memory, and controller
Correct Answer: (c)
9. The _______ is the theoretical counterpart of the CPU.
a. disk
b. tape
c. controller
d. read/write head
Correct Answer: (c)
10. The controller has _______ states.
a. three
b. four
c. a finite number of
d. an infinite number of
Correct Answer: (c)
11. A _______ is a pictorial representation of the states and their relationships to each other.
a. transition diagram
b. flowchart
c. transition table
d. Turing machine
Correct Answer: (a)
12. A _______ shows, among other things, the movement of the read/
write head, the character read, and the character written.
a. diagram
b. flowchart
c. transition table
d. Turing machine
Correct Answer: (c)
___
14. The complexity of a problem is O (log10 n) and the computer executes 1 million instructions per second. How long does it take to run
the program if the number of operations is 10,000?
a. 1 microsecond
b. 2 microseconds
c. 3 microseconds
4
d. 4 microseconds
Correct Answer: (d)
:::