알고리즘 (algorithms) The word algorithm is a corruption of early English algorisme, which came from Latin algorismus, which came from the name of the Persian mathematician Abu Ja'far Mohammed ibn Musa al-Khwarizmi (ca ca. 845). He was the author of the book Kitab al-jabr w'al-muqabala (Rules of Restoration and Reduction) which introduced algebra to people in the West. The word algebra itself originates from al-Jabr from the book title. PersianAbu Ja'far Mohammed ibn Musa al-Khwarizmi780845algebrathe Westalgebra
The word algorism originally referred only to the rules of performing arithmetic using Arabic numerals but evolved into algorithm by the 18th century. The word has now evolved to include all definite procedures for solving problems or performing tasks.arithmetic Arabic numerals18th century
요리 재료 조리법 오븐, 프라이팬 등등 요리
초콜렛과 물 2 스픈을 스팀통에 넣고 녹 인다. 녹으면 설탕을 넣고 버터를 조금씩 넣는다. 불에서 내려놓은후 달걀노른자 를 넣어 끈적거리고 레몬색이될때까지 5 분간 젓는다. 초콜렛을 더녹여 넣는다. 필요하면 가열한다. 럼과 바닐라를 넣는 다. 달걀 흰자위를 넣어 …….
알고리즘으로 풀어야 할문제들 54 곱하기 182=? 182 를 54 로 나눈후의 나머지는 ? 봉급표에서 회사의 사무원들의 한달 월 급의 합을 구한다. 정수 a, b 가 주어졌을때 a 2 + 3b 를 계산 하시오. 정수가 주어졌을때 소수인지 아닌지 판 별하시오.
문자열이 있을때 알파벹 순서로 다시 정 렬하시오. 서울에서 부산까지 국도를 따라서 여행 하려 한다. 여행 경로를 정한다. 유럽에 배냥여행을 갔다. 도시가 여러 개 있고 여행기간 중 킬로만 갈수 있 다. 어떤 경로를 통해야 만 되는가 ?
알고리즘의 목적 우리가 하고자 하는 것을 제대로 해야 한 다. Specification of all legal inputs Characterization of desired output as a function of input Legal input algorithm The desired output
algorithmic idea -> algorithm programming programming in high-level language compilation equivalent program in assembly language ……. machine code (binaries)
질문 : 제대로 하는가 ? 알고리즘은 제대로 되어 있는가 ? 컴퓨터로 체크할수 없는가 ? 프로그램에 버그는 없는가 ? Hardware 는 제대로 작동하는가 ? 예 : 107 세 덴마크 노인이 입학통지서를 받은경 우 예 : 뉴욕 1990 년 1 월 9 시간동안 전화불통 예 : 1996 년 6 월 아리안 5 폭발 프로그램 에러 (64 비트를 16 비트 자리에 넣는 오류 오버플로 )
Y2K 문제 Syntex error: compiler 가 많은 경우 찾아낸다. Logical error: 프로그램 자체에는 문제가 없다. 그러난 우리가 원하는 것을 하지 않는다. Debugging Intel Pentium II 현재 프로그램, 기계에러 보다는 인간의 에러 가 훨씬 많다. 그리고 기계의 에러는 그보다 더 적다. 거의 없다고 생각해도 된다. 라이스의 정리 : 알고리즘에 관한 성질을 알아 내는 알고리즘이 없다. (undecidable)
대표적인 알고리즘들 예 유클리드 알고리즘 GCD(A, B) Data Structure Storage, Pushdown stacks Trees Recursion: 예 자눈금 그리기 ALIS z head
tree Binary trees, recursion
sorting Selection sort: smallest, second smallest, so on: N 2 /2 comparison, N exchanges (on the average) Insertion sort: put in the proper place N 2 /4 comparison N 2 /8 exchange Radix sort: convert to digits Quick sort: divide and conquer 2Nlog N comparisons
Quick sort Divide and conquer, recursive a(1), a(2), …, a(r ) (1) a(r ) 큰것들은 뒤로 작은것들은 앞으 로 (2) 앞것들로 문제 국한해서 다시 quicksort (3) 뒷것들로 문제 국한해서 다시 quicksort
Search Sequential searching Binary search (divide and conquer) Hashing String searching Pattern matching Parsing
File compression Run length encoding Huffman code: frequency of each character tree
Geometric algorithms Points, lines, polygons Convex hulls Intersections Graph algorithms: maps, electrical wiring, IC chips, work schedules ….
수학 알고리즘 Random number generator Polynomial, matrix multiplications N 3 N 2.81 Gaussian eliminations Curve fitting Integration, symbolic or numerical Root finding (Newton ’ s algorithm)
알고리즘의 한계 Program verification: undecidable Y2K 2000: undecidable Rice ’ s theorem: There is no program to tell anything about a program. Matrix 2: oracles … Highly noncomputable noncomputable computable
현실적으로 어려운것 들 하노이 타워
해 : 1. 제일 작은 것을 시계방향으로 하나 움직 인다. 2. 나머지에서 유일하게 가능한것을 한다. N 개의 원판이 있는 경우 2 N – 1 번 움직여야 한 다. knot.org/recurrence/hanoi.shtml 2 32 ~ 하루의 마크로초 (10 – 6 초 ) 2 64 ~ 빅뱅이후의 마크로초 (10 – 6 초 ) N N 정말 할수 없음
NP 완비인 문제들 여행하는 세일즈맨의 문제 : 여러 도시와 도로 길이가 적혀 있는 지도가 있다. 주어진 거리 K 보다 적게 가면서 모든 도시를 돌수 있는가 ? 시간표 작성 문제 : 선생님, 교실, 각시간대 조건 : 한 교실에 같은 시간에 두선생님이 부여 안됨, 한 선생님이 같은 시간에 두 교실에 가지 않음. 전쟁 : 파일롯, 전투기, 미션
토의 사항 컴퓨터의 한계는 어떤 것들이 있는가 ? 컴퓨터의 한계를 어떻게 하면 극복되는 가 ? 어떤 방법으로 컴퓨터를 잘 활용할 수 있 는가 ? 컴퓨터은 단지 도구 인가 ?
도서 Robert Sedgewick, Algorithms in C++, Addison Wesley 1992 M. Atallah, Algorithms and theory of computations handbook, CRC Press 1999 D. Harel, Computers Limited, Oxford U. Press 2000 D. Harel, Algorithms, Addison-Wesley 1997