이산수학 () 알고리즘 (Algorithms) 0 년봄학기 강원대학교컴퓨터과학전공문양세
Algorithms The foundation of computer programming. ( 컴퓨터프로그래밍의기초 / 기반이다.) Most generally, an algorithm just means a definite procedure for performing some sort of task. ( 알고리즘은주어진일을수행하기위한정의된절차를의미한다.) A computer program is simply a description of an algorithm in a language precise enough for a computer to understand. ( 컴퓨터프로그램이란정의된알고리즘을컴퓨터가이해할수있는언어로정확하게기술한것에불과하다.) We say that a program implements (or is an implementation of ) its algorithm. ( 프로그램은알고리즘을 구현한것이다 라고이야기한다.) Page
Programming Languages Some common programming languages: Newer: Java, C, C++, Visual Basic, JavaScript, Perl, Tcl, Pascal Older: Fortran, Cobol, Lisp, Basic Assembly languages, for low-level coding. In this class we will use an informal, Pascal-like pseudocode language. You should know at least real language! Page
Algorithm Example (in English) Task: Given a sequence {a i }=a,,a n, a i N, say what its largest element is. ( 주어진 sequence 에서가장큰수는?) Algorithm in English Set the value of a temporary variable v to a s value. Look at the next element a i in the sequence. If a i >v, then re-assign v to the number a i. Repeat previous steps until there are no more elements in the sequence, & return v. Page
Executing an Algorithm When you start up a piece of software, we say the program or its algorithm are being run or executed by the computer. ( 소프트웨어를시작할때, 우리는프로그램혹은알고리즘을실행한다 ( 혹은돌린다 ) 라고이야기한다.) Given a description of an algorithm, you can also execute it by hand(?), by working through all of its steps on paper. ( 알고리즘이있으면, 종이에손으로써가면서이를수행할수도있다.) Before ~WWII, computer meant a person whose job was to run algorithms! ( 차대전이전에, 컴퓨터는알고리즘을수행하는사람을의미했다!) Page
Execute the Max Algorithm Let {a i }=7,,,,8. Find its maximum by hand. Set v = a = 7. Look at next element: a =. Is a >v? Yes, so change v to. Look at next element: a =. Is >? No, leave v alone. Is >? Yes, v= Page 6
Algorithm Characteristics ( 알고리즘의특성 ) (/) Some important features of algorithms: Input( 입력 ): Information or data that comes in. Output( 출력 ): Information or data that goes out. Definiteness( 명확성 ): Precisely defined. ( 각단계는명확하게정의되어야한다.) Correctness( 정확성 ): Outputs correctly relate to inputs. ( 입력값의각집합에대해서정확한출력값을만들어야한다.) Finiteness( 유한성 ): Won t take forever to describe or run. Page 7
Algorithm Characteristics ( 알고리즘의특성 ) (/) Some important features of algorithms ( 계속 ): Effectiveness( 효율성 ): Individual steps are all do-able. ( 각단계는유한한양의시간에수행되어야한다.) Generality( 일반성 ): Works for many possible inputs. ( 특정한입력이아닌모든가능한입력에대해서동작하여야한다.) Page 8
Pseudocode Language procedure name(argument: type) variable := expression informal statement begin statements end {comment} if condition then statement [else statement] for variable := initial value to final value statement while condition statement procname(arguments) Not defined in book: return expression Page 9
procedure procname(arg: type) Declares that the following text defines a procedure named procname that takes inputs (arguments) named arg which are data objects of the type type. Example: procedure maximum(l: list of integers) [statements defining maximum ] Page 0
variable := expression An assignment statement evaluates the expression, then reassigns the variable to the value that results. Example: v := x+7 (If x is, changes v to.) In pseudocode, the expression might be informal: x := the largest integer in the list L Page
Informal Statement Sometimes we may write an informal statement, if the meaning is still clear and precise: swap x and y. Keep in mind that real programming languages never allow this. ( 궁극적으로는알고리즘을쓰고이를구현해야한다.) When we ask for an algorithm to do so-and-so, writing Do so-and-so isn t enough! ( x 를찾는알고리즘을기술하라 했는데, find x 라하는것은충분치않다!) Break down algorithm into detailed steps. Page
begin statements end Groups a sequence of statements together: begin statement statement statement n end Allows sequence to be used like a single statement. Might be used: After a procedure declaration. In an if statement after then or else. In the body of a for or while loop. Page
{ comment } Not executed (does nothing). Natural-language text explaining some aspect of the procedure to human readers. (Reader 의이해도모 ) Also called a remark in some real programming languages. Example: {Note that v is the largest integer seen so far.} Page
If condition then statement Evaluate the propositional expression condition. If the resulting truth value is true, then execute the statement; otherwise, just skip on ahead to the next statement. ( 조건이 true 일때만문장을수행한다.) Variant: if cond then stmt else stmt Like before, but iff truth value is false, executes stmt. Page
while condition statement (/) Evaluate the propositional expression condition. If the resulting value is true, then execute statement. Continue repeating the above two actions over and over until finally the condition evaluates to false; then go on to the next statement. ( 조건이 true 인한문장을반복하여수행한다.) Page 6
while comment statement (/) Also equivalent to infinite nested ifs, like so: (if 를무한히써서구현할수도있다. 설마 ~) if condition begin statement if condition begin statement (continue infinite nested if s) end end Page 7
for var := initial to final stmt Initial is an integer expression. Final is another integer expression. Repeatedly execute stmt, first with variable var := initial, then with var := initial+, then with var := initial+, etc., then finally with var := final. What happens if stmt changes the value that initial or final evaluates to? For can be exactly defined in terms of while, like so: begin var := initial while var final begin stmt var := var + end end Page 8
procedure(argument) A procedure call statement invokes the named procedure, giving it as its input the value of the argument expression. Various real programming languages refer to procedures as functions (since the procedure call notation works similarly to function application f(x)), or as subroutines, subprograms, or methods. Page 9
Max Procedure in Pseudocode Rewrite finding maximum number in pseudocode. procedure max(a, a,, a n : integers) v := a {largest element so far} for i := to n {go thru rest of elems} if a i > v then v := a i {found bigger?} {at this point v s value is the same as the largest integer in the list} return v Page 0
Inventing an Algorithm Requires a lot of creativity and intuition. Like writing proofs. We can t give you an algorithm for inventing algorithms. Just look at lots of examples [ 많은예를보세요 ] And practice (preferably, on a computer) [ 연습을많이하세요 ] And look at more examples [ 좀더많은예를보세요 ] And practice some more etc., etc. [ 좀더많은연습을하세요 ] Page
Searching Algorithm ( 탐색알고리즘 ) Problem of searching an ordered list. ( 정렬된리스트에서주어진값을찾아내는검색을수행하는문제 ) Given a list L of n elements that are sorted into a definite order (e.g., numeric, alphabetical), And given a particular element x, Determine whether x appears in the list, and if so, return its index (position) in the list. Problem occurs often in many contexts. ( 여러분이 Programming 을하는한수십번이상마주치는문제임!) Let s find an efficient algorithm! Page
Linear Search ( 선형탐색 ) 리스트의첫번째원소부터차례대로검색하는방법 예 : Find in {, 6, 9,,, 8,, } procedure linear search (x: integer, a, a,, a n : distinct integers) i := while (i n x a i ) i := i + if i n then location := i else location := 0 return location {index or 0 if not found} Linear search 는 ordered list( 정렬된상태 ) 뿐아니라 unordered list( 정렬되지않은상태 ) 에서도바르게동작한다. Page
Binary Search ( 이진탐색 ) (/) Basic idea: On each step, look at the middle element of the remaining list to eliminate half of it. ( 리스트의중간에위치한값과비교하여, 작은값들을가지는리스트혹은큰값 들을가지는리스트중에서한쪽부분에대해서만검사를진행한다.) 예 : Find 8 in {, 6, 9,,, 8,, } <x <x <x >x Page
Binary Search ( 이진탐색 ) (/) procedure binary search (x:integer, a, a,, a n : distinct integers) i := {left endpoint of search interval} j := n {right endpoint of search interval} while i<j begin {while interval has > item} m := (i+j)/ {midpoint} if x>a m then i := m+ else j := m end if x = a i then location := i else location := 0 return location Binary search 는 ordered list( 정렬된상태 ) 에서만바르게동작할뿐 unordered list( 정렬되지않은상태 ) 에서는바르게동작하지않는다. Page
Sorting Algorithm ( 정렬알고리즘 ) Sorting is a common operation in many applications. (Programming 을하는한 Search 다음으로많이마주치는문제임!) E.g. spreadsheets and databases It is also widely used as a subroutine in other dataprocessing algorithms. Two sorting algorithms shown in textbook: Bubble sort Insertion sort However, these are not very efficient, and you should not use them on large data sets! There are more than different sorting algorithms! ( The Art of Computer Programming by Donald Knuth.) Page 6
Page 7 Bubble Sort Example Sort L = {,,,, } nd pass st pass rd pass th pass
Bubble Sort Algorithm procedure bubble sort(a, a,, a n : real numbers with n ) for i := to n - for j := to n - i if a j > a j+ then interchange a j and a j+ {a, a,, a n is in increasing order.} Page 8
Insertion Sort procedure insertion sort(a, a,, a n : real numbers with n ) for j := to n i := while a j > a i {find a proper position of a j } i := i + m := a j for k := 0 to j i {insert a j into the proper position} a j-k := a j-k- a i := m {a, a,, a n is in increasing order.} Page 9
Greedy Algorithm 최적의알고리즘 (optimal algorithm) 을찾기가어렵다? 알고리즘의각단계에서최선을선택을수행하는 Greedy algorithm 을사용할수있다. Greedy algorithm 은최적일수도있다. 최적임을보이기위해서는증명이필요하고, 최적이아님을보이기위해서는반례 (counterexample) 를든다. 예제, 0,, 센트의동전이있을때, 동전의수를최소화하면서 67 센트의거스름돈을만들어라. 센트동전을선택한다. ( 센트남음 ) 센트동전을선택한다. (7 센트남음 ) 0 센트동전을선택한다. (7 센트남음 ) 센트동전을선택한다. ( 센트남음 ) 센트동전을선택한다. ( 센트남음 ) 센트동전을선택한다. ( 센트남음 ) Page 0