알고리즘 = 문제를 해결하는 단계적 절차 또는 방법


◆알고리즘의 특성


-정확성 : 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다.

-수행성 : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능하여야 한다.

-유한성 : 알고리즘은 일정한 시간 내에 종료되어야 한다.

-효율성 : 알고리즘은 효율적일수록 그 가치가 높아진다.



알고리즘의 표현 방법 


말로 표현 :

ex)첫 카드의 숫자를 읽고...

다음 카드의 


의사 코드 : 프로그래밍 언어와 유사

ex)



여러가지 알고리즘

#해결방식에 의한 알고리즘 분류
-분할 정복 알고리즘
-그리디 알고리즘
-동적 계획 알고리즘
-근사 알고리즘
-백트래킹 기법
-분기 한정 기법
-기타 등등



문제를 해결하는 방식은 문제의 속성과 밀접한 관계가 있으므로, 문제에 따라 알고리즘을 사용해야함


#문제에 기반한 알고리즘

-정렬 알고리즘

-그래프 알고리즘

-기하 알고리즘

-기타 등등


알고리즘의 효율성 표현


#시간복잡도와 공간복잡도 → 주로 시간복잡도가 사용됨.


시간을 측정하기 위해 컴퓨터를 사용할 수가 없음(측정하는 컴퓨터의 모든 조건이 같아야 하므로 평가가 어려움)

때문에 → 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현.


#복잡도를 표현하는 세가지 방법

-최악의 경우 

-평균의 경우

-최선의 경우


#복잡도의 점근적 표기


위에서 말했듯이 연산 횟수를 입력 크기에 대한 함수로 표현하는데 이를 단순하게 표현하기 위해 점근적 표기법을 사용한다.


점근적 표기의 세가지

-빅오 표기법

-빅 오메가 표기법

-빅 세타 표기법


※ 점근적 표기법은 따로 책을 보시면서 공부하는게 도움이 될듯 싶습니다.


운영체제 : 컴퓨터 하드웨어와 컴퓨터 사용자 간의 매개체 역할로 컴퓨터 하드웨어를 효율적으로 관리하는 자원 할당자.


운영체제의 유형

·일괄 처리 시스템

- 컴퓨터 프로그램의 흐름에 따라 순차적으로 자료를 처리하는 방식

- 유휴 상태의 시간을 없애기 위해 여러개의 작업을 단일 작업으로 만듬

- 작업의 준비 및 실행 순서를 자동화함으로써 시스템의 성능을 높임.

- 작업을 실행하면 끝날때까지 아무것도 할 수 없음.


·다중 프로그래밍 시스템

- 일괄 처리에서 CPU를 비효율적으로 사용하는 것을 착안하여 그 이용도를 높이기 위한 방안

- 프로그램들 사이에 스케줄링을 통하여 CPU사용 늘림 -> 실제 CPU에서 한 개의 프로그램만 실행 

- 주기억장치 내에 여러 프로그램이 존재함 -> 메모리 관리의 어려움


·시분할 시스템

- 여러 사용자들이 컴퓨터 자원에 대한 짧은 시간 단위의 공유

- 사용자는 대화식 단말장치를 이용하여 시분할 시스템과 인터페이스를 수행


·분산 처리 시스템

- 여러 개의 분산된 데이터 저장소와 처리기들을 고속의 버스나 전화선과 같은 다양한 통신라인(네트워크)을 통해 서로 통신하면서 동시에 일을 처리

- 프로세서들이 기억장치와 클럭을 공유하지 않으며 각 프로세서들은 자신의 지역 기억장치 보유 -> 자원의 독립성

- 느슨한 결합 시스템이라고도 함

- 두 가지 기법

네트워크 운영체제

- 노드 간 기종의 차이가 심하고 대규모 네트워크 시스템에 사용

- 각 노드들은 독자적인 운영체제를 지님.

분산 운영체제

-각 노드들은 하나의 운영체제로 운영


·다중 처리 시스템

- 컴퓨터 시스템 한 대에 여러 개의 CPU를 이용하여 병렬로 처리하는 방식

- 여러 개의 프로세서가 하나의 공유기억장치를 사용하며, 일반적으로 하나의 운영 체제가 모든 프로세서들을 제어 관리.


·멀티미디어 시스템

- 다양한 미디어를 이용하여 멀티미디어 콘텐츠를 제작하기 위해 필요한 하드웨어와 소프트웨어로 구성

- 멀티미디어 콘텐츠를 제작하기 위한 저작도구가 필요


·임베디드 시스템

- 마이크로프로세서 또는 마이크로컨트롤러를 내장하여 시스템 제작자가 의도한 몇 가지 혹은 특수한 기능만을 수행하도록 제작된 시스템

- 장점 : 임베디드 시스템과 그 한정된 자원들의 능력에 맞게 최적화


+ Recent posts