Abdul Bari의 Algorithms 강의를 듣고 공부한 내용입니다. 링크
What is Algorithms?
Algoritm is step by step procedure for solving a computational problem
Then, what is program?
Program is a procedure for solving a computational problem
OK, then what is the difference between program and algorithms?
By comparing program and algorithm, we can understand the importance and meaning of algorithm
Software development lifecycle : there are two important phases in developing
Design phase and Implementation phase
first you design, and then you write a program
Before you write a program, you write on a paper, MS Word, notepad etc. about how program should work, what's the function program have etc. this is nothing but algorithm.
So, algorithms are written in design time
Program is written in implementation time.
Algorithm
- written in Design Time
- written by someone who has domain knowledge (can also be a programmer with domain knowledge)
- Any language can be used
- HW/SW & OS independent
- Analyze - achieving the goals right, efficient in time and space
Program
- written in Implementation Time
- written by programmer
- programming language is used
- HW/SW & OS dependent
- Test - Running and checking errors
gonna use C language in this lecture
1.1 A priori analysis and A posteriori testing
※ A priori : (Latin) 선험적인; 연역적인 // A posteriori : (Latin) 경험에 의거하여, 귀납적인
A priori analysis
- analysis of algorithm by studying it into a greater detail knowing how it is working
- find out the time and space consumed by an algorithm
- time function and space function
- hardware independent
- language independent
A posteriori testing
- run and execute program, and check
- watch-time, and the amount of memory consuming in terms of bytes
- hardware specific
- language specific
- OS & environment specific
1.2 Characteristics of Algorithm
- Input - can take 0 or more input
- Output - at least 1 output
- Definiteness - should be obvious, should have single, exact meaning. cannot write any statement which can't be understood and can't be solved. Every statement should be clear and definite
- *Finiteness - must terminate at some point, must have finite set of statements, duration must be finite (on the other hand, there are some programs which runs continuously until the user stops them, for example, database server)
- *Effectiveness - whatever the statement in algorithm is, it must work in the steps of algorithm. None of statements in algorithms is unnecessary.
