離散數學(7)

第七章 Relations: The Second Tine Around

A relation R on a set A is called reflexive(反身性) if for all x ε A (x,x) ε R

Relation R on set A is called symmetric(對稱性) if(x,y) εR → (y,x) ε R for
all x,y ε A

For a set A, a relation R on A is called transitive of, for all x,y,z ε A, (x,y),(y,z) ε R → (x,z) ε R.(So if x “is related to” y, and y “is related to” z, we want x “related to” z, withy playing the role of “intermediary”.

Given a relation R on a set A, R is called antisymmetric if for all a,b εA ,(aRb and bRa) → a=b

A relation R on a set A is called a partial order, or a partial ordering relation, if R is reflexive, antisymmetric, and transitive.

If A, B, and C are sets with R1cAxB and R2c BxC, then the composite relation R1◦R2 is a relation from A to C defined by  R1◦R2={(x,z)|x εA,
z ε C, and thereexists y ε B with (x,y) εR (y,z) εR2}

長方桌排列

有10個人 在長方桌作排列

一邊可坐3人 一邊可坐2人

共有10! /2種排列

作業系統(2)

第二章 System Structures

An operating System provides the environment within which programs are executed.

User interface. Almost all operating systems have a user interface(UI). The interface cam take several forms. One is DTrace Command-line interface(CLI), which uses text commands and a method for entering them.

Another is a batch interface, in which commands and directives to control those commands are entered into files, and those files are executed.

Most commonly, a graphical user interface(GUI) is used. Here, the interface is a window system with a pointing device and direct I/O, choose from menus, and make selections and a keyboard to enter text.

On systems with multiple command interpreters to choose from, the interpreters are known as shells.

System calls provide an interface to the services made available by an operating system.

System programs, also known as system utilities, provide a convinient environment for program development and execution.

The kernel has a set of core components and links in additional services either during boot time or during run time. Such a strategy uses dynamically loadable modules and is common in modern implementations of UNIX.

Seven types of loadable kernel modules
1. Scheduling classes
2. File systems
3. Loadable system calls
4. Executable formats
5. STREAMS modules
6. Miscellaneous
7. Device and bus drivers.

離散數學(6)

第六章 Languages: Finite State Machines

If ∑ is an alphabet and n ε Z+, we define the powers of ∑ recursively as follows:

1)∑1=∑

2)∑^n+1={xy|x ε ∑, y ε ∑^n} where xy denote the juxtaposition of x and y

For a alphabet ∑ we define ∑0={λ},where λ denotes the empty string—that is, the string consisting of no symbols taken from ∑.

If ∑ is an alphabet

a)∑ +=n=1 to 無限大U∑ n=Un ε z+∑ n

b)∑ *=n=0 to無限大 U∑ n

離散數學(5)

第五章 Relations and Functions

5.1 Cartesian Products and Relations

For sets A,B the Cartesian product, or cross product, of A and B is denoted by AxB and equals{(a,b)|a ε A,b ε B}.

For sets A,B, any subset of AxB is called a (binary) relation from A to B. Any subset of AxA is called a (binary) relation on A.

For nonempty sets A, B, a function, or mapping, from A to B, denoted

f :A → B, is a relation from A to B in which every element of A appears exactly once as the first component of an ordered pair in the relation.

For the function of f:A → B, A is called the domain(定義域) of f and B the codomain(對應域) of f. The subset of B consisting of those elements that appear as second component in the ordered pairs of f is called the range(值域) of f and is also denoted by f(A) because it is the set of images under f.

A domain f:A → B is called one-to-one, or injective, if each element of B appears at most once as the image of an element of A.

A function of f:A → B is called onto, or surjective, if f(A)=B—that is, if for all b ε B there is at least one a ε A with f(a)=b.

作業系統(1)

第一章 Introduction

An operating systen is a program that manages the computer hardware.

The hardware—the central processing unit(CPU), the memory, and the input/ouput(I/O) devices – provides the basic computers resources for the system.

The application programs—such as word processors, spreadsheets, compiler, and Web browsers—define the ways in which these resources are used to solve users' computing problems.

The operating system controls the hardware and coordinate its use among various application programs fir the various users.

A more common definition, and the one that we usually follow, is that the operating system is the one program running at all times on the computer—usually called the kernel.

Softeare may trigger an interrupt by executing a special operation called a system call.

On a single-processor system, there is one main CPU capable of excuting a general-purpose instuction set, including instructions from user processes.

Multiprocessor systems(also known as parallel systems or tightly coupled systems) are growing in importance. Such systems have two or more processors inclose communication, sharingthe computer bus and sometimes the clock, memory, and peripheral devices.

A trap (or an exception) is software-generated interrupt caused either by an error(for example, division by zero or invalid memory access) or by a specific request from a user program that an operating-system service be performed.

User mode amd kernel mode(also called supervisor mode, system mode, or privileged mode). A bit, called the mode bit, is added to the hardware of the computer to indicate the current mode : kernel(0) or user(1).

Embedded systems almost always run real-time operating system. A real-time system is used when rigid time requirements have been placed on the operation of a processor or the flow of data.


The operating system is responsible for the following activities in connection with process management

i)Scheduling processes and threads on the CPUs
ii)Creating and deleting both user and system processes
iii)Suspending and resuming processes
iv)Providing mechanisms for process synchronization
v)Proving mechanisms for process communication.

離散數學(4)

第四章 Properties of the integers: Mathematical Induction

All that is needed is for the open statement S(n) to be true for some first element n0 ε Z so that the induction process has a starting place. We need the truth of S(n0) for our basis step. The integer n0 could be 5 just as well as 1. It could even be zero or negative because the set Z+ in union with {0}{ or any finite set of negative integers is well ordered.

Principle of Mathematical Induction

[S(n0) ^ [all k>=n0[s(k) → s(k+1)]]] → all n >=no s(n)

Principle of Strong Mathematical Induction

a) If s(n0),s(n0+1), s(n0+2)...,s(n1-1),s(n1) are true

b)If whenever s(n0) s(n0+1)...s(k-1)and s(k) are true for some k ε z+, where k>=n1, then the statement s(k+1) is also true;then s(n) is true for all n>=n0

If a,b ε z and b=\0 , we say that b divides a and we write b|a, if there is an integer n such that a=bn, where this occurs we say that b is a divisor(因數), or a is a multiple(倍數) of b.

a) 1|a and a|0

b) [(a|b)^(b|a)] → a=+-b

c)[(a|b)^(b|c)] → a|c

d) a|b → a|bx for all x ε Z

e) If x=y+z for some x,y,z ε Z, and a divides two of the three integers x,y and z, then a divides the remaining integer.

f)[(a|b)^a|c)] → a|(bx+cy) for all x,y ε Z

g)For 1<=i<=n let ci ε Z. If a divides each ci, then a|(c1x1+c2x2+...+cnxn), where xi ε Z for all 1<=i<=n