알고리즘 : 문제를 푸는 데 필요한 단계의 순서를 명확히 명시하는 구체적인 계산법
위대한 알고리즘의 조건?
일반 컴퓨터 사용자가 날마다 사용하는 알고리즘
구체적이고 실질적인 문제를 다뤄야 한다는 점
알고리즘이 하드웨어 중점을 둔 기술이나 인터넷 같은 인프라스트럭처 설계가 아닌 컴퓨터과학 이론에 우선적으로 연관돼야 한다는 점
검색엔진 인덱싱: 세상에서 가장 큰 건초 더미에서 바늘 찾기
검색엔진의 두 가지 주요 과제: 매칭과 랭킹. 매칭 기법인 메타워드 트릭, 랭킹 알고리즘과 구글의 페이지랭크 알고리즘
매칭과 랭킹
첫 번째 단계가 끝나면 수천 또는 수백만 개의 부합하는 결과가 있을 수 있다. 그리고 두 번째 단계에서 적합성에 따라 이를 분류해야 한다.
알타비스타: 최초의 웹 규모 매칭 알고리즘
오래된 평범한 인덱싱: 모든 검색엔진 이면에 있는 가장 근본적 발상.
매칭-구문 쿼리 문제 해결: 페이지 번호뿐 아니라 페이지 안의 위치도 저장해야 한다는 아이디어
랭킹-인간은 near 쿼리를 많이 쓰지 않지만 검색엔진은 랭킹을 향상시키고자 근접성에 관한 정보를 계속 이용
메타워드 트릭: 실제 HTML에선 메타워드를 태그라 부름,구조쿼리는 사용자가 거의 이용하지 않지만 검색엔진은 내부적으로 늘 이용. <titlestart><titleend>를 통해 찾고자 하는 단어가 제목에 있는지를 파악, 이를 하이퍼링크, 이미지, 설명 등 다양한 부분 검색 가능
페이지랭크: 구글을 출범시킨 기술
하이퍼링크 트릭:연결된 페이지 수를 세어 각 페이지에 있는 인커밍링크의 수에 따라 랭킹 매김, 그러나 나쁜 페이지에 이용될 수도 있음.
권위 트릭: 높은 권위가 있는 페이지에서 온 링크는 낮은 권위가 있는 페이지의 링크보다 더 높은 순위라는 결과를 낳아야 한다
하이퍼링크와 권위 트릭을 결합해 권위 점수로 구분
무작위 서퍼 트릭: 하이퍼링크가 사이클을 형성하는 경우 즉, 하이퍼링크를 클릭하다가 출발점으로 되돌아오는 경우 해결하기 위함. 구조는 똑같음. 하이퍼링크+ 권위
실제 상용 검색엔진이 페이지랭크 같은 링크 기반 랭킹 알고리즘 외에도 훨씬 더 많은 것을 이용해 순위를 결정
공개 키 암호화: 공개 엽서에 비밀을 적어 아무도 모르게 보내는 방법
공유 비밀로 암호화(key)
블록 암호라는 변형된 덧셈 트릭
고급 암호 표준(AES) : 일반적으로 16자짜리 블록을 128비트 키와 함께 이용해 10차례의 혼합 계산을 하는 방식으로 사용
공유 비밀을 공개적으로 설정하기
페인트 혼합 트릭: 일방향 행위 전제
개인키를 정한다
공개키와 개인키를 혼합하고 공개키를 공개한다
상대의 혼합된 공개키와 개인키를 자신의 개인키와 계산한다
상대도 마찬가지로 혼합된 공개키와 개인키를 자신의 개인키와 계산하면 같은 값을 가지게 됨.
오류 정정 코드: 데이터 오류를 스스로 찾아 고치는 마법
반복트릭
리던던시 트릭: 원본 메시지에 잉여 정보를 담은 메시지를 이용해서 메시지에 있는 모든 변화를 검출하고 정정.
(=메시지를 전송하려면 우선 각 심벌을 이에 대응하는 코드워드로 해석해야 한다. 그 다음에 여러분은 변형한 메시지를 신뢰할 수 없는 통신 채널을 통해 전송한다. 메시지를 수신했을 때 메시지의 각 부분을 보고 이것이 유효한 코드워드인지 확인한다. 유효하다면 이에 대응하는 심벌로 이를 되돌리기만 하면 된다. 만약 확인한 메시지가 유효한 코드워드가 아니라면 가장 근접히 부합하는 코드워드를 알아낸 다음 이를 대응하는 심벌로 변형한다. )
(=인코딩을 할 때 4자리 숫자가 각 집단은 이에 추가할 리던던시를 가져 7자리 코드워드를 생성한다. 디코딩할 때 수신자는 우선 수신한 7자리 숫자에 정확히 부합하는 코드워드를 찾는다. 정확히 부합하는 대상이 없다면 가장 근접한 값을 취한다. )
오버헤드: 메시지가 정확하게 수신되었는지 확인하기 위해 보내야 하는 잉여 정보의 양. 반복 트릭의 오버헤드는 양이 엄청나기 때문에 리던던시 트릭 선호
체크섬 트릭: 단순 체크섬= 다 합한 뒤 끝자리만 원본과 함께 적음. 이 경우 하나의 오류만 있는 경우 100%검출이지만 여러 개일 경우 보장 안 됨. -> 계단 체크섬 : 여러 오류 발생하는 경우 보완, 곱셈한 부분을 추가
핀포인트 트릭
코드워드 집합, 이차원 패리티,
전송 제어 프로토콜(TCP),패킷에 주로 이용 위성TV부터 심우주 탐사기에 이르는 애플리케이션에서 저밀도 패리티 검사 코드 이용.
패턴 인식과 인공지능 : 사람처럼 학습하고 생각하는 컴퓨터
패턴 인식은 인공지능의 하위분야, 얼굴 인식, 대상 인식, 발화 인식, 손글씨 인식 등을 포함함, 더 구체적인 예로 사진을 보고 누구인지 맞추거나 봉투에 손으로 쓴 주소를 알아내는 것 등을 들 수 있다. 여기서 패턴 인식은 변수가 많은 입력 데이터에 맞게 컴퓨터가 지적으로 행동하게 하는 과제라고 정의할 수 있음.
인접인웃 분류자, 의사결정나무, 인공 신경망
패턴인식과제: 첫 번째는 분류된 훈련 데이터를 기반으로 컴퓨터가 클래스에 관해 학습하는 ‘훈련 단계’이고 둘째는 컴퓨터가 분류되지 않은 새로운 데이터 샘플을 나누는 ‘분류 단계’
인접이웃 분류자: 분류되지 않은 데이터 샘플을 받으면 우선 훈련 데이터에서 이 샘플에 가장 근접한 이웃을 찾아 이 최근접 이웃의 클래스를 예측값으로 이용
K-인접이웃 분류: 인접 이웃 값을 검토하고 근접한 이웃 중 가장 대중적인 클래스를 선택
다양한 종류의 인접이웃: 숫자 이미지 사이의 지리적 거리가 아니라 차이를. 측정, 차이는 백분율로 측정, 1%만 차이 나는 이미지는 매우 가까운 이웃, 99%차이 나는 이미지는 거의 관계가 없음.
스무고개 트릭: 의사결정나무
충분한 양의 훈련 데이터가 주어지면 정확한 분류를 만들어 낼 의사결정나무를 학습하는 일이 가능하다
컴퓨터는 매우 많은 수의 첫 질문을 시험해 보고 최적의 정보를 도출할 질문을 찾는다. 첫 질문에 대한 답을 토대로 훈련 예시를 두 집단으로 나눈 다음 각 집단에 최적의 질문을 제시한다. 이렇게 나무의 특정 지점에 도달한 훈련 예시 집합을 토대로 최적의 질문을 결정하는 식으로 의사결정나무를 따라 내려간다. 예시 집합이 특정 지점에서 순수하다면 컴퓨터는 새로운 질문 생성을 멈추고 나머지 페이지에 대응하는 답을 산출.
선글라스 문제에 대한 신경망
신경망의 기본적 구조, 역치를 넘는지를 기준으로 판단, 신경망이 올바르게 작동하기 전에 특정 방식으로 조율되어야 한다.
조율 된다는 의미 파악하기
가중 신호 더하기
강화1: 신호는 0부터 1 사이의 값을 취할 수 있다.
강화2: 총 입력은 가중 합계로 계산한다.
연결의 비중이라는 수가 연결의 강도를 반영. 비중은 양의 숫자일 수도 있고 음의 숫자일 수도 있음.
강화3: 역치의 효과는 약화된다.
선글라스 문제에서 1 근방의 출력값은 선글라스가 있는 확률이 매우 큼을 나타내고 0 근방의 출력값은 선글라스가 없음을 거의 확실히 입증한다는 뜻.
학습에 의한 신경망 조율
인공 신경망 조율의 의미
모든 연결은 그 비중을 양(흥분성) 또는 음(억제성)이 될 수 있는 값으로 설정해야 함
모든 뉴런에서 역치가 적합한 값으로 설정되게 해야 함
모든 훈련 샘플을 여러 번 연습한 후 신경망은 성능 수준이 높아지고 학습 단계는 현재 다이얼 설정 상태에서 종료됨
신경망 학습 단계는 신경망이 훈련 샘플에 대해 제대로 수행할 때까지 모든 비중과 역치를 반복 조정하는 일을 비롯해 상당한 작업량이 필요하다.
선글라스 예에 작동하는 방법: 학습 단계가 완료되면 입력 이미지로부터 중앙 뉴런까지 수천 개의 연결 각각에 수치 비중이 할당, 모든 픽셀로부터 하나의 뉴런으로만 가는 연결에 집중하면 이 비중을 이미지로 변환해 매우 편리하게 시각화,
신경망 구조 한 줄 정리: 자극을 받으면 신경이 다른 뉴런에게 신호를 보내는 것처럼 인공지능도 이러한 구조를 차용하여 특정 역치값이 신호에 대한 비중을 고려하여 0에 가까워 지면 아니요 라는 출력을 1에 가까워지면 예라는 출력을 하게 만드는 것.
데이터 압축: 책 한 권을 종이 한 장에 담기
무손실압축
런-렝스 인코딩: 반복적인 데이터 압축, 실제로 다른 압축 알고리즘과 함께 사용
이를 보완하기 위해 반복이 인접하지 않아도 잘 작동하는 더 정교한 트릭 고안
전과 같음 트릭, 더 짧은 심벌 트릭
전과 같음 트릭 : 비슷한 부분 뒤에 몇 자리로 돌아가서 몇 번 복사할 건지 적어줌
더 짧은 심벌 트릭: 자주 쓰는 심벌을 짧은 숫자 코드로 축약, 겹치는 경우 잘 안쓰는 심벌엔 긴 숫자 코드 부여.
손실압축
압축 파일을 원본과 매우 유사하지만 똑같지는 않은 파일로 재구성할 수 있게 하는 손실 압축을 이용하는 편이 훨씬 유용할 때가 있음.
생략 트릭
압축가공물: 짝수 번째 행과 열을 생략, 단지 세부 항목의 손실이 아니라 압축 해제 후 특정 손실 압축 방법으로 인한 눈에 띄는 새로운 특징을 말함.
JPEG: 전체 이미지를 8x8픽셀 크기의 작은 정사각형으로 나눔, 각 정사각형을 개별 압축
Mp3,AAC 같은 흔한 음악 압축 포맷은 일반적으로 JPEG와 같은 고도의 접근을 이용, 그러나 오디오 압축 포맷은 인간 귀에 관한 사실도 이용, 특정 유형의 소리는 인간에게 거의 또는 전혀 영향을 주지 않고 압축 알고리즘으로 산출물의 품질을 떨어뜨리지 않으면서 이를 제거할 수 있음.
오류 정정 코드와 압축 알고리즘은 동전의 양면, 오류 정정 코드는 리던던시를 가지고 압축 알고리즘은 리던던시를 제거
데이터베이스: 일관성을 향한 여정
온라인 거래에 핵심적인 기술: 공개키 암호화 + 데이터 베이스
데이터 베이스: 효율성과 신뢰성
온라인 뱅킹은 탁월한 효율성과 완벽한 신뢰성을 요하는 애플리케이션의 전형적인 예.
데이터베이스 이면의 근본적 알고리즘 3가지
미리 쓰기 로그
커밋
관계형 데이터베이스
트랜잭션과 할 일 목록 트릭
컴퓨터에 관한 두 가지 사실: 프로그램이 충돌한다. 충돌하면 기존에 하던 모든 일을 잊는다.
일반적으로 컴퓨터는 한 번에 데이터베이스의 한 행만을 업데이트할 수 있음.
일관성이 중요하기 때문에 이러한 점에서 문제가 발생할 수 있음.
계좌이체의 경우 전체가 아닌 일부의 변화가 트랜잭션에서 수행된다면 데이터베이스는 불일치 상태로 남을 수 있음.
할 일 목록 트릭: 미리 쓰기 로그, 먼저 데이터베이스 테이블은 건드리지 않고 트랜잭션의 할 일 목록을 로그에 씀 그 다음에 로그 엔트리를 디스크 같은 영구 저장 장치에 확실히 저장한 다음 테이블 자체에 계획한 변화를 줌. 테이블의 변화가 디스크에 저장되면 로그 엔트리를 삭제할 수 있음. 할 일 목록 트릭은 데이터 오염을 사전에 차단하지만 데이터 손실을 제거하진 못함.
중복 데이터베이스를 위한 준비 후 커밋 트릭
트릭을 이해하려면 1. 데이터베이스는 복제될 수 있다. 2. 때론 데이터베이스 트랜잭션이 취소되어야 한다. 이를 트랜잭션 복귀 또는 중단이라고 부른다
중복데이터베이스
충돌 전 저장된 모든 데이터가 여전히 그대로 남아 있지 않은 경우 할 일 목록 트릭은 도움이 안 됨. 왜냐하면 충돌 시점에 진행 중이던 트랜잭션을 완료하거나 복귀시켜 특정 유형의 충돌을 회복시킬 수 있는 역할이기 때문. 이의 해결책은 두 개 이상의 데이터베이스 사본 유지. 데이터베이스의 사본 하나를 복제본이라 부르고 모든 사본의 집합을 중복 데이터베이스라 칭함. 백업과 구분. 백업은 백업 이후 변화가 발생하면 이 변화는 다른 장소에 저장되지 않음. 중복데이터베이스는 동기화됨.
트랜잭션의 복귀
트랜잭션은 데이터베이스의 일관성을 보장하기 위해 반드시 수반되어야 하는 데이터베이스에 대한 일련의 처리 동작, 트랜잭션이 완료할 수 없을 때도 있음, 예를 들면 디스크 공간 부족이나 동시 사용의 경우 잠금하고 다시 해제하는 과정을 거치는 데 이때 교착상태(데드록)라 부르는 심각한 상황 초래 가능. 교착상태에서는 하나가 취소되어 나머지 트랜잭션을 진행할 수도 있음. 트랜잭션 도중 디스크 공간이 부족할 땐 부분적으로 완료된 트랜잭션을 중단하거나 복귀하는 능력 필요, 할일 목록을 약간 변형하면 복귀를 달성할 수 있음, 이는 미리 쓰기 로그가 필요한 경우 각 작업을 원상복귀할 추가 정보를 담고 있어야 함.
요약-복귀해야 하는 경우 2가지: 할일 목록의 경우 이전으로 복귀/ 중복데이터베이스의 경우 디스크 공간부족 복귀
준비 후 커밋 트릭 : 첫 번째는 준비단계, 두 번째는 최초 제안을 모두가 수용했는지 여부에 따라 결정 또는 중단 단계
할일 목록과 준비 후 커밋 트릭을 결합하면 은행이 원자적 트랜잭션으로 중복 데이터베이스를 실행할 수 있으며 동시에 접속한 수천 명의 고객을 불일치나 데이터 손실 가능성이 전혀 없는 상태에서 응대 가능.
디지털 서명: 진짜 누가 이 소프트웨어를 작성했을까?
종이 서명에서는 여러분이 상대방에게 보낼 내용에 서명을 하지만 디지털 서명에서는 상대방이 여러분에게 내용을 보내기 전에 서명을 함. 사람들이 잘 인식하지 못하는 이유는 컴퓨터가 디지털 서명을 자동으로 확인하기 때문.
곱셈 자물쇠로 서명하기
자물쇠를 이용해 숫자 메시지를 잠가 디지털 서명을 제작. 시계 크기를 이용한 곱셈에 대응. 최종 결과인 숫자가 메시지에 대한 디지털 서명.
잠그는 과정은 디지털 서명을 생산하는 반면 여는 과정은 메시지를 생산함. 열린 메시지가 원본 메시지와 일치하면 디지털 서명은 검증되고 원본 메시지는 진짜, 열 때 키를 이용!
메시지에 서명을 할 때마다 메시지와 서명을 노출할 수 있지만 서명을 제작하는 데 이용한 자물쇠 숫자는 노출할 수 없음, 시계 값과 숫자 키는 공개해도 됨.
순서: 메시지->(자물쇠)->서명->(키)->검증된 성명
키 값이 공개적이기 때문에 누구나 비밀이어야 할 자물쇠 값을 계산할 수 있음, 그리고 다른 사람이 자물쇠 값을 알게 되면 이 사람의 디지털 서명을 위조할 수 있음.
지수 자물쇠로 서명하기
RSA 디지털 서명 체계 : 공개키 암호화 체계인 동시에 디지털 서명 체계
다른 사람이 이용하는 키와 시계 크기를 안다고 해서 이에 대응하는 자물쇠 값을 계산할 수는 없음. 앞의 곱셈 시스템에 있는 결점을 수정
계산 가능성과 결정 불가능성: 컴퓨터로 모든 문제를 해결할 수 있을까?
어떠한 소프트 웨어 검사 도구라도 모든 프로그램에 잠재해 있는 충돌을 모두 검출하는 일은 불가능하다는 것을 증명할 수 있음.
어떤 파일이나 입력을 이용해서 어떤 프로그램이라도 실행할 수 있다는 개념이 있다. 그러나 입력 파일이 이를 실행한 프로그램의 목적에 맞는 파일이 아닌 경우 결과 출력은 주로 쓰레기
컴퓨터 프로그램도 컴퓨터 디스크에 파일로 저장되므로 아무 프로그램이나 입력으로 이용해 어떤 프로그램이라도 실행할 수 있다는 사실
한 컴퓨터 프로그램은 자기 자신을 입력으로 이용해 실행할 수 있음
잠재력 있는 위대한 알고리즘 후보군
인공지능, 영지식 프로토콜, 분산 해시 테이블, 비잔틴 장애 허용,
알고리즘이 생각보다 굉장히 큰 범위라는 것에 놀람…
소프트웨어 기술이 어떤 원리에 의해 작동되며 무슨 문제로 발전 되었는지 알려주는 책.
책도 어렵지 않고 이론적인 거에 비하면 쉽게 쓰여짐 … 초보자도 가능! 조금 흥미 없으면 지루할 수도…ㅎ;;
알고리즘을 가지고 어떻게 프로그램으로 변환하는지는 정확히 알기 어려웠지만 그 구현하기 위한 아이디어들은 이해할 수 있었던 좋은 책
개인적으로 좋았던 부분은 검색엔진, 인공지능, 트랜잭션과 중복데이터베이스, 공개키&암호키
자세하고 쉬운 예시들이라 좋았고 뭔가 조금 더 IT를 이해할 수 있었음..