컴퓨팅적사고 7주차

이번 강의에서 다룬 주제는 알고리즘을 통한 문제 해결입니다. 알고리즘의 정립, 알고리즘 개념의 확립자 크누스, 알고리즘을 구현한 최초의 프로그래머, 알고리즘의 표현 방법, 알고리즘의 주요 특성, 알고리즘을 통한 문제 해결의 구현 과정 등을 배웠습니다.

 

알고리즘을 통한 문제 해결

알고리즘의 정립
-수학에서는 문제를 풀기 위해 정의나 정리들을 활용
-컴퓨터에서는 문제 해결을 위해 알고리즘(algorithm) 이용
-문제를 철저하게 분석한 후 알고리즘을 거쳐 프로그램 작성
-알고리즘 개념의 시초는 1830년대 영국의 바베지(Babbage)와 러브레이스(Lovelace)에 의해 처음으로 제기됨
컴퓨터과학자들과 크누스(D. Knuth)에 의해 체계적으로 정립

알고리즘 개념의 확립자 크누스
-크누스(Donald Ervin Knuth, 1938~ )는 미국의 컴퓨터과학자
-The Art of Computer Programming 7권 시리즈 저술
-알고리즘의 대가, 1974년 튜링상(Turing Award) 수상
-초기의 문서 편집용 소프트웨어인 TeX 개발

알고리즘을 구현한 최초의 프로그래머
-러브레이스(Ada Lovelace, 1815~1852)는 최초의 프로그래머
-분석 엔진을 고안한 찰스 베비지의 후원자이자 동료
-루프(loop), 서브루틴(subroutine) 개념과 IF 구문을 고안
-알고리즘을 구현하는 현대적 프로그래밍의 개념 착안

알고리즘의 표현 방법
-알고리즘은 여러 가지 방법으로 표현 가능
-순서도(flowchart)
-유사 코드(pseudo code),
-언어(language)
-프로그래밍 언어 등
-누구나 이해할 수 있도록 명확하게 기술

알고리즘의 주요 특성
-입력(input): 문제를 풀기 위한 입력
-출력(output): 문제를 해결했을 때 그 결과인 해답
-유한성(finiteness): 명령이 수행된 후에는 반드시 끝나야 함
-정확성(correctness): 주어진 문제를 정확하게 해결
-확정성(definiteness): 각 단계가 실행된 후에는 결과가 확정
-일반성(generality): 같은 유형의 문제에 모두 적용 가능
-효율성(effectiveness): 모든 명령은 명확하면서도 효율적

알고리즘 처리 순서: 1. 입력-2. 출력-3. 처리

알고리즘을 통한 문제 해결의 구현 과정
-알고리즘은 문제를 해결하기 위한 체계적이고 순서적인 절차
-논리적 표현으로 변환하면 의사 코드나 순서도로 변환 가능
-이것을 해당 프로그래밍 언어로 변환하면 컴퓨터 프로그램
-주어진 문제를 해결하는 아이디어로 알고리즘 만들기
-최종적으로 컴퓨터 프로그램을 실행하여 결과를 얻음