코드 없는 알고리즘과 데이터 구조 (암스트롱 수베로 지음)
목차
Part 1 - 데이터 구조
Part 2 - 알고리즘
Part 3 - 알고리즘과 데이터 구조를 이해하는데 필요한 지식들
10. 무작위성
📍무작위성
- 식별할 수 있는 패턴 없이 예측 불가능하게 발생하는 성질
(동전을 던져 앞 or 뒤 가 나올 확률)
- 사람에게 선천적으로 존재 (심리.. 충동적 행동 등)
반면 컴퓨터는 사람과 달리 항상 의도된 출력을 제공하도록 프로그래밍됨
- garbage in garbage out
프로그래밍에서는 수학의 확률 이론을 기반으로 (무작위) 난수 생성
📍하드웨어 이해하기
컴퓨터가 하드웨어적으로 난수를 생성하는 방법 뿐만 아니라 알고리즘 동작의 기반이 되는 컴퓨터 하드웨어를 이해해야 한다
트랜지스터
- 컴퓨터를 이루는 전자 부품의 기본 구성요소
- 이산 트랜지스터 -> 회로도 (배터리, 모터, 스위치 등을 포함)
모스펫(MOSFET)
- 트랜지스터보다 더 효율적으로, 소비 전력을 줄임
칩에 많은 트랜지스터를 집적할수록 컴퓨터 성능이 향상됨
(무어의 법칙)
증폭기(amplifier)
- 전자 신호를 증폭 (회로 구성요소가 조합되어 약한 신호를 받아 더 강력한 신호를 생성)
- 연산 증폭기 (피드백을 사용하여 동작)
피드백
- 장치의 출력 중 일부를 다시 입력으로 사용
- 네거티브 피드백 : 출력 중 일부를 반전 단자로 피드백
단자(terminal)
- 장치의 핀
콤퍼레이터(비교기)
- 연산 증폭기를 사용
- 전기 신호 2개를 비교하여 결과에 따라 특정 신호(HIGH / LOW)를 출력
클럭(clock)
- 디지털 회로의 심장 박동으로 주어진 간격에서 HIGH ~ LOW 로 움직이는 신호 (진동 : oscillation)
- CPU의 성능의 척도
- 알고리즘의 성능이 효율적이라는 것은 최소한의 클럭 사이클 시간을 소모
- 오실레이터(발진기)는 클럭을 생성
📍논리 게이트(logic gate)
- 트랜지스터의 조합으로 생성
- 입력 상태(H/L)에 따라 특정 출력(H/L)을 제공
논리곱(AND) 게이트
- 2개의 입력 단자와 1개의 출력 단자
- 두 입력이 모두 HIGH 이면 HIGH or 1 을 출력
- 두 입력이 모두 LOW 이면 LOW or 0 을 출력
논리합(OR)
- 두 입력 중 하나만 HIGH여도 HIGH or 1 을 출력
- 두 입력이 모두 LOW 이면 LOW or 0 을 출력
논리 부정(NOT)
- 입력의 반대를 출력
버퍼(Buffer)
- 입력을 단순히 출력으로 전달
- 논리 레벨(HIGH / LOW)의 감쇄 현상을 방지하거나 전달 속도를 지연시키는 역할
배타적 논리합(XOR)
- 두 입력이 다를 때 HIGH or 1을 출력
📍조합 및 순차 논리
- 논리 게이트를 조합하여 조합 논리 또는 순차 논리를 구성
조합 논리(combinational logic) 회로
- 입력의 현재 상태가 바로 출력에 반영
순차 논리(sequential logic) 회로
- 입력의 현재 상태 뿐만 아니라 이전 상태까지 반영하여 출력을 생성하도록 메모리와 피드백이 구현된 회로
- 펄스 현상으로 클럭이나 신호의 진폭이 잠깐 크게 바뀜
- 플립플롭(flip-flop) : 컴퓨터 메모리의 구성요소로 상태 정보 저장하는데 사용 가능
D 플립플롭
- 기초적 플립플롭 형태
- 데이터(회로도에서 D로 표시)와 클럭(삼각형과 이어진 단자로 표시)을 입력으로 받아 출력(Q) 제공
- 출력(Q)은 입력으로 주어지는 클럭의 변화에 따라 달라짐
레지스터
- CPU의 기본 저장 단위
- 플립플롭은 메모리의 기본 단위 중 하나로, 단일 레지스터로 간주할 수 있음
시프트 레지스터
- 다수의 플립플롭으로 구성된 회로로, 여러 비트 데이터를 저장
- 시스템에 비트를 직렬 또는 병렬 방식으로 입력 가능
직렬 입력 직렬 출력 (SISO, serial in serial out) 시프트 레지스터
- 데이터를 직렬로 입력받아 직렬로 출력
직렬 입력 병렬 출력 (SIPO, serial in parallel out) 시프트 레지스터
- 데이터를 차례대로 입력받은 후 한 번에 모두 병렬로 출력
이외에도 PISO, PIPO 시프트 레지스터 존재
- 시프트 레지스터를 다른 회로와 결합하면 다른 비트 조작 수행 가능
📍혼성 신호 회로, 유도 저항, 노이즈
- 아날로그 회로 : 연산 증폭기
- 디지털 회로 : 논리 게이트, 플립플롭, 시프트 레지스터
콤퍼레이터
- 연속적 아날로그 신호를 받아 이산적 디지털 신호로 변환
- 아날로그-디지털 변환(ADC, analog-to-digital conversion)
- (반대) 디지털-아날로그 변환(DAC)
예) 마이크를 통해 음성을 녹음하고 스피커로 재생
연속적인 아날로그 신호 (목소리) => 이산적인 디지털 신호 (녹음) => 다시 아날로그 신호로 출력 (스피커에서 재생)
- 회로를 사용하여 신호를 변환
- CPU가 이를 처리하고 저장
혼성 신호 회로(mixed-signal circuit)
- 아날로그와 디지털 구성요소를 포함한 회로
컴퓨터 하드웨어 중 회로 구성요소 2가지
- 커패시터(축전기, capacitor)
- 인덕터(유도기, inductor)
이 2가지는 주기적으로 크기와 방향을 바꾸는 교류(AC)의 흐름에 저항하는 유도 저항(reactance) 을 갖는다
노이즈
- 회로에서 전기 신호에 불필요한 간섭이 발생하는 현상
📍유사 난수
유사 난수 (pseudorandom number)
- 실제로는 무작위가 아닌 숫자
- 무작위 숫자 생성 알고리즘의 설계 방식에 한계가 있어 진짜 무작위 숫자를 생성한다고 하기 힘들다
시드값
- 난수 생성에 필요한, 프로그래머가 정하는 숫자
- 똑같은 시드값을 사용하면 생성되는 일련의 숫자도 같다
- 이러한 문제 해결을 위해 운영체제에서 제공하는 몇 가지 매개변수를 사용하여 안전하게 시드값을 생성
- 몇 차례 거듭하면 완전한 난수에 가까운 결과를 얻을 수 있다
난수 생성기 : random number generator (RNG)
유사 난수 생성기 : pseudorandom number generator (PRNG)
- 아무리 정교한 유사 난수 생성기라도 시드값 등 이미 결정된 알고리즘이 있으므로 완전한 난수 만드는 것은 불가
사이버 보안 분야처럼 완전한 난수가 필요한 곳에서는 특수한 난수 생성기를 활용한다
- 암호화 보안 유사 난수 생성기 : CSPRNG
- 암호화 유사 난수 생성기 : CPRNG
선형 피드백 시프트 레지스터
- 유사 난수를 생성하는 괜찮은 방법
- 플립플롭과 배타적 논리합 게이트의 조합을 사용하여 비트열로 유사 난수 생성
- 무작위로 보이는 생성된 비트열이 다시 선형 함수의 입력으로 제공되고, 이 과정이 반복됨
- 비암호화용으로 훌륭한 유사 난수 생성기 구현 가능
📍참 난수 생성기
하드웨어 난수 생성기 (HRNG)
- 참 난수 생성기는 유사 난수 생성기보다 복잡한 하드웨어 성능이 필요
- 노이즈 또는 카오스 시스템에서 발생하는 무작위 현상으로 난수 생성
(카오스 시스템 : 한동안 예측이 가능하며, 이후 무작위처럼 보이는 시스템)
오실레이터 기반 HRNG
- 스트레이 유도 저항(본질적으로 노이즈)을 생성
- 이 노이즈를 감지하는 논리 회로를 통해 난수 생성
노이즈 기반 HRNG
- 플립플롭이 있는 콤퍼레이터를 사용
양자 기반 시스템 등..