본문 바로가기

컴퓨터 과학

컴퓨터과학이 여는 세계_9.1 튜링증명 리뷰, 시간복잡도의 개념_이광근 강좌 동영상 예전에 스위치만 켜면 참인 명제만 만드는 기계가 존재한다 --A 라면어떤 명제가 현실적으로 가능한 시간만에 끝난다--H 인 명제가 사실임을 증명했다. 그 증명을 짧게 요야하자면 어떤 명제M이 있을 때, A에서 말한 기계가 M에 대하여'M이 끝난다''M이 끝나지 않는다'를 밝힐 것이다. 그런데 그것을 밝히는 역할은 H에서 말한 기계가 하는 일이므로 A가 참이면 H도 참이다. 또, H가 거짓이라 A가 거짓임을 밝혔다. 그런데 강좌에서 한 학생이 질문을 한다.만약 참인 명제만을 만드는 기계가"어떤 명제 M이 끝나는지 아닌지 알 수 없다." 라는 명제를 증명하면 어떡하죠? 이것을 답하기 전에 명제의 종류를 알아야한다.먼저 기본적인 명제 'p이면 q이다' 같은 것들은 "1st order"명제라고 한다.. 더보기
컴퓨터과학이 여는 세계_8.4 비현실적으로 오래걸리는 문제_이광근 강좌 동영상 자릿수가 N개인 숫자로 이루어진 비밀번호를 어떻게 찾을까? 비밀번호가 아니다 틀리다만 알 수 있기 때문에 시스템 결함이 있지 않는 이상 10^N번 다 해봐야한다. 만약 영문자 조합이라면? 특수문자도 있다면? 심지어 어떤 조합인지도 모르고 자릿수도 모른다면? 그 복잡도는 어마어마할 것이다. 소인수분해를 할 때도 마찬가지이다. 100을 소인수 분해 한다면 2로 나눠보고 3으로 나눠보고 ... 해서 100 = 2*2*5*5 라는 것을 찾는다. 하지만 숫자가 28,392,749,719,070,274,017,094,729,749,071,974,729,477,294 같이 무지막지하다면 엄청난 시간이 걸린다. '그러면 더 쉬운 방법으로 하면 되지'라고 생각이 들지만 현재까지 일반적으로 N자리가 주어졌을때.. 더보기
컴퓨터과학이 여는 세계_8.3 알고리즘의 예와 복잡도_이광근 강좌 동영상 어떤 입력이 N개 주어졌을 때 걸리는 시간을 알고리즘의 시간 복잡도라고 한다. 책을 읽는 알고리즘을 예를 들겠다. 책은 N페이지로 한 장에 한쪽만 적혀있고, 한쪽을 읽는데 1초가 걸린다고하자. 그러면 N초가 걸린다. 또 다른 예로 안이 보이지 않는 주머니 속에 숫자가 적힌 공이 N개 있다고 하자. 그 숫자중 가장 큰 숫자를 찾을려면 N개의 공을 모두 꺼내서 확인해 봐야한다. 1부터 N까지 숫자중 하나를 추측할 때에 Yes/No로만 대답한다면, 1이니?, 2인가?, 설마3? 이런식으로 N번 물어볼 수 있다. 이 알고리즘의 시간 복잡도는 N이다. 하지만 만약 N이 100만 이면 그걸 일일이 하고 있을순 없다. 한편, 중간을 딱 잘라서 이거보다 크니? 라고 묻는 것을 반복하면 훨씬 빠르게 문제를 .. 더보기
컴퓨터과학이 여는 세계_8.2 알고리즘과 언어_이광근 강좌 동영상 소프트웨어는 튜링기계다. 튜링기계는 어떤일을 하고 그 일은 문제를 푸는 것이다. 컴퓨터는 소프트웨어(튜링기계)를 실행하면서 문제풀이를 자동적으로 진행한다. 컴퓨터로 문제를 푼다는 것이 이 뜻이다. 알고리즘이란 소프트웨어로 만드는 문제푸는 방도이다. 따라서 컴퓨터로 문제를 풀려면 알고리즘을 찾아야 한다. 그 해법이 맞는지 확인한 후 소프트웨어로 구현한다.-컴퓨터 과학이 여는 세계 中 문제를 풀기 위해선 알고리즘을 찾아야한다. 찾았다 하더라도 더 빠른 방법은 없는지 그 알고리즘이 현실적으로 가능한지 살펴야한다. 만약 알고리즘이 현실적으로 불가능하다면, 우주가 끝날 때까지 답을 찾지 못할 수 있다. 또, 어떤 알고리즘의 시간적 비용이 120년이라고 해서 같은 문제를 푸는 다른 방법을 찾았더니 똑같.. 더보기
컴퓨터과학이 여는 세계_8.1 소프트웨어를 잘 짜기위한 두개의 축_이광근 강좌 동영상 마음의 도구인 컴퓨터는 소프트웨어를 통해 사용한다. 가구를 짜거나 설계도를 짜듯이 소프트웨어도 지혜로 짠다. 소프트웨어를 짜기 위해선 두 가지 축이 필요하다. 첫 째는 알고리즘이다. 문제푸는 방법이라고도 한다. 같은 일을 할때 어떤 방법으로 일을 처리할지가 이 알고리즘에 해당하는 일이다. 두 번째는 언어이다. 아무리 좋은 알고리즘을 찾았다고 한들 생각만 하고 있으면 되지 않는다. 언어를 통해 표현해야하고 그것이 C나 Python같은 것으로 표현되어지는 것이다. SW는 한편 무시무시하기도 하다. 책이 한권에 2~30줄 300쪽이라 하면 6000줄 정도인 반면 보통 우리들이 쓰는 휴대폰의 운영체제가 몇십만 몇백만 줄이다. 그런데 기본적으로 사람이 짜기 때문에 실수가 있기 마련이고, SW가 잘못되.. 더보기
컴퓨터과학이 여는 세계_7.3 여러가지 재료로 컴퓨터 만들기_이광근 강좌 동영상 컴퓨터가 반드시 전기로 움직일 필요는 없다. 렌즈와 거울을 이용해서 빛으로 움직일 수도 있고, 도르래 같은 것을 이용해 힘으로 컴퓨터를 움직일 수도 있다. 그런데 현재 전기를 쓰는 이유는 그나마 가장 싸게 밀도있게 만들 수 있기 때문이다. 과거엔 엔지니어들이 진공관 스위치를 썼는데, 주먹만한 크기로 되어있다. 요즘은 눈에 보이지도 않게 작게 만들고 있다. 또, 지구상에 무지하게 많고 싼 재료로 만들고 있는데 바로 모래이다. 모래(Si, 규소/실리콘)에 최외각 전자가 3 또는 5인 물질을 도핑해주면 전자가 하나 남거나 모잘라서 전기가 때에 따라 잘 흐르는 물질이 된다. 그렇게 해서 만든 것이 트랜지스터이다. 초기 컴퓨터를 만들었을 때 컴퓨터의 효율이 불도저로 문을 열고 닫는 수준이라고 한다. .. 더보기
폰 노이만의 디자인 [출처 - 구글] 폰 노이만이 앨런 튜링의 논문을 봤는지 안 봤는지 알 수 없지만 폰 노이만은 1945년 'First Draft of a Report on the EDVAC'이라는 논문을 발표했다. 또, EDVAC이라는 컴퓨터를 만들었는데, 튜링의 기계와 비슷하지만 사뭇 다른 양상의 컴퓨터였다. 폰 노이만의 기계는 메모리에 프로그램이 저장되고, 메모리는 주소로 직접접근했다. 또, 중앙제어장치에 Program Counter(PC)를 (Personal Computer 이랑 다르다...) 만들어 프로그램의 흐름을 제어했다. 튜링의 기계와 폰 노이만의 기계 모두 어느 것이 더 낫다거나 한 쪽이 하는 일을 다른 쪽이 못 한다거나 하는 일을 없다. 두 기계 모두 유사한 구조를 띄고 있기 때문이다. 더보기
컴퓨터과학이 여는 세계_7.2 규칙표와 메모리에 읽고쓰는 회로 강좌 동영상 이제 메모리를 구현했으니 메모리에 읽고 쓰는 회로도 만들 차례이다. 간단하게 4비트 메모리에 읽고 쓰는 장치라고 해보자. 4비트 메모리니 쓸 주소와 읽은 주소도 4개의 숫자만 표현하게 두 개의 회로만 사용하면 된다. 그러면 이제 쓰기회로와 읽기회로를 주소가 입력되었을 때 해당 주소에 맞는 메모리에 어떻게 접근할까? 우선 읽기 회로이다. 응답회로는 앞서 구현했던 Decoder회로이다. 만약 m0를 읽고싶으면, 주소에 00을 입력해 m0와 연결된 and연산에 1을 주고 나머진 모두 0을 준다. 그렇다면 결국 출력으로 나오는 결과는 m0에 해당하는 정보일 것이다. 내 생각엔 or연산을 빼도 성립할 것 같다. 쓰기회로도 이와 비슷하다. 읽기회로와 달리 or연산이 하나 빠졌다. 데이터를 통째로 입력하.. 더보기
튜링기계를 컴퓨터 회로로 ':)'을 계속 쓰는 스마일 튜링기계가 있다고 하자.그렇다면 다음과 같이 A와 B상태가 번갈아가면서 :) 을 계속 쓸 것이다.(악필이다.. 그러려니 넘어가자) 이 튜링기계를 전기회로 바꾸고 싶은데 우선 'A'나 '>' 같은 기호를 표현해주기 위해 이진수로 표현해 보도록 한다. 그런다음 상태와 심볼, 움직임에 따른 각각의 이진수를 표로 나타낸 뒤 어떤 연관을 가지는 지 알아보자. 튜링기계가 간단하기 때문에, 이진수 표도 간단하게 나타낼 수 있다.이제 이 표를 가지고 회로도를 나타내는데 이번엔 회로도 자체보단 메모리와의 관계를 알아보도록 하자. 먼저 긴 메모리와 작은 메모리에서 S, I0, I1을 받아온다. 그 후 위에 표와 같은 연산을 마치고 S', O0, O1, D0, D1을 다시 메모리에 쓴다. 이 과.. 더보기
컴퓨터과학이 여는 세계_7.1 메모리회로 만들기_이광근 강좌 동영상 메모리회로: 어떤 값을 기억하고 있고 추후 그 값을 사용하거나 수정할 수 있는 회로 "flip-flop"회로라고도 한다. 전기는 한번 입력되면 순식간에 지나가기 때문에 시간이 지나도 그 정보가 남아있는 회로는 생각하기 힘들다. 하지만, 다음과 같이 회로를 만들면 가능하다.(컴퓨터로 지금까지 그렸는데, 시간이 너무 많이 걸려서 앞으로 손그림을 이용하기로 했다) 초승달 A, B가 or스위치고 그옆에 붙어있는 원이 not 스위치이다.R = 0, S = 1 이면 B에서 S가 1이니 무조건 1을 반환할것이고 not때문에 0이 된채로 A에 들어간다. 이때, R = 0이니 A는 0을 반환하지만 not 때문에 1이 되고 Q = 1이 된다.R = 0, S = 0 이 되어서 S가 꺼지면 A에 남아있던 1이 B.. 더보기

티스토리툴바