🍺 매일매일 맥잔잔 🍺

1-1

• oriC: DNA에서 복제의 시작점
• k-mer: mer은 polymer할 때 mer
• most frequent k-mer: 길이 k의 text중 가장 frequent한 text
• kmer 찾는것이 실제로 hidden message를 찾는것에 의미가 있는가? (15p)
• polymerase: polymer를 만드는 애
• dnaA: replication initiater
• dnaA box

• 19p: 초록색과 빨간색은 complementary한 관계에 있다
• 염기서열의 첫부분은 5’ end 끝부분은 3’ end라고 함
• 5’ end가 항상 왼쪽으로 오게 쓴다
• genome(또는 생물 종류)에 따라 hidden message가 다를 수 있다

• oriC가 주어질 때는 hidden message를 찾을 수 있지만 전체 genome에서 oriC를 찾으려면?
• oriC크기의 window를 잡아서 해당 window내의 frequent word를 찾아서 window끼리 비교한다

1-2

Probabilities of Patterns in a String

• Pr(4, 2, “11”, 2) > Pr(4, 2, “01”, 2) 인 이유는 11은 overlap이 가능하기때문이다 (111이면 11이 두번 있는셈)
• 6쪽의 공식은 overestimate임. 왜냐하면 예로 0101011이라는 string은 0101xxx, xx0101x 등 중복되어 counting 될 수 있기 때문이다
  

Finding Frequent Words

• brute force
• less time: frequency array
• patternToNumber, NumberToPattern -> O(k)
• findingFrequentWordsBySorting -> O(1)
• total -> O(text * k)
• 4의 k승만큼의 메모리를 사용
• sorting을 추가한다면? findingFrequentWordsBySorting -> 단어길이만큼의 메모리를 사용
• k가 길경우에는 sorting을 사용하고 짧을경우에는 sorting없이 그냥 하는것이 나음

Finding Clumps

• index를 integer로 바꾸는것 -> text * k

1-3

• dna 복제는 2개 방향으로 밖에 진행될 수 없다(bidirectional)
• 갈라지는동안 okazaki fragment가 부분적으로 복제된다
• 그리고 마지막에 합쳐짐
• 방향(forward, backward)에 따라 mutation rate가 다름
• single-stranded DNA has a much higher mutation rate than double-stranded DNA
• cytosine rapidly mutates into thymine through deamination & deamination rates rise 100-fold when DNA is single stranded
• skew diagram
• skew(k): |G| - |C| for the first k nucleotides of genome(누적함수)
• skew 함수가 감소하다가 증가하는 부분이 oriC라고 추측할 수 있다

1-4

• Hamming Distance Problem
• hamming distance: number of mismatches between string p and q
• d-neighborhood: hamming distance가 d보다 작거나 같은 k-mer들
• skew diagram에서 감소-증가 바뀌는 부분이 반드시 oriC라고 할 수 없다. reversal때문에 genome이 부분적으로 바뀔 수 있기 때문

//Assignment 1

Rosalind - bioinformatics problems - overlap graphs

• fasta format: 헤더와 스트링이 있는 포맷

• Searching for Tyrocidine B1
• Translation은 genome의 어느 부분에서든 시작해도 된다
• Cyclic
• DNA->RNA
• Transcription 과정
• RNA Polymerase에 의해 진행됨
• RNA->Protein
• Translation 과정
• Ribosome에 의해 진행됨
• 하지만 ribosome이 억제됐을 때 합성되는 단백질도 있음. NRP synthetase에 의해 합성되는 tyrocidine
• Mass Spectrometer로 분자의 질량을 계산 -> 어떤 단백질인지 알아냄
• 1 Dalton = mass of proton/neutron
• mass of molecule = sum of protons/neutrons
• 단, 20개 아미노산 중 정수로 따질 경우 같은 질량을 가진 애들이 2쌍 있음 -> 18가지의 질량을 구분할 수 있음
• Mass Spectrometer
• 1. Theoretical spectrum을 구함
• 길이 n의 주어진 peptide를 순서에 따라 쪼개서 가능한 모든 subpeptide(1~n-1)의 mass를 구함
• 2. spectrum에 해당하는 peptide를 찾는다(Cyclopeptide Sequencing Problem)

—

• A Brute Force Algorithm for Cyclopeptide Sequencing
• 주어진 mass를 가지는 모든 가능한 peptide sequence를 생성하여 비교함
• 결론적으로 불가능하다. 왜냐하면 가능한 sequence의 수가 exponentially 증가하기 때문에
• 해결책: branch-and-bound
• Cyclopeptide Sequencing with Branch-and-Bound
• 주어진 spectrum중 57~186에 해당하는 mass를 골라 가능한 1-mer들을 구한다 -> 해당 1-mer들로 만들 수 있는 가능한 2-mer를 만든다 -> 2-mer들 중 spectrum과 일치하는 것들만 남긴 후 3-mer를 만든다 -> 반복
• 어떤 dataset에 대해서는 exponential 할 수 있지만 보통의 상황에서는 굉장히 빠름(증명되지는 않음)
• Adapting Sequencing for Spectra with Errors
• 실제 spectrum에는 error가 있을 수 있음. 있어야 할 mass가 없거나 없어야 할 mass가 있을 수 있음
• false masses: present in experimental spectrum, absent from theoretical spectrum
• missing masses: present in theoretical spectrum, absent from experimental spectrum
• 해결책: theoretical, experimental spectrum에 공통적으로 해당하는 mass만 추림 + LeaderboardCyclopeptideSequencing
• LeaderboardCyclopeptideSequencing
• 주어진 spectrum에서 정확한 1-mer들을 추려낼 수 없기 때문에(에러 가능성) 18개의 아미노산 mass 모두에 대해 따짐
• low-scoring peptide를 쳐냄(단, keep top N with ties)
• candidate이 없을 때까지 extend, cut 반복
• heuristic한 방법이기 때문에 precise하지 않고 correct solution을 miss할 가능성이 있음(진작에 쳐내진 branch 중 정확한 솔루션이 존재할 가능성)
• 실제 실험 결과 10%의 error가 있을 경우 제대로 찾았지만, 25%의 error가 있던 경우에는 정확한 답을 찾지 못함
• From 20 to More than 100 Amino Acids
• 실제 아미노산 중에서는 mass가 일정하지 않은 non-standard amino acid가 존재한다(Ornithine)
• 따라서 18가지의 mass말고 그냥 57-186에 해당하는 정수로 따지면 리더보드 알고리즘으로 10%의 에러가 있을 경우에도 제대로 답을 찾지 못함
• The Spectral Convolution Saves the Day
• 주어진 spectrum에서 어떤 mass pair의 차는 1-mer의 mass에 해당할 수 있음. 물론 아닐 수도 있음 => Spectral Convolution!
• 모든 mass pair의 차를 구해서 테이블에 나타냄
• 테이블을 보면 여러번 나오는 mass가 있을 것. 실제 spectrum에 해당하는 1-mer일 가능성이 높다
• ConvolutionCyclopeptideSequencing
• 주어진 sequence에 대해 spectral convolution을 진행 -> M most frequent mass에 대해 LeaderboardCyclopeptideSequencing을 진행
• 실험 결과 M=10일 경우 10%의 error, 25%의 error 두 경우에 대해 모두 제대로 나옴
• The Truth About Spectra
• 실제 mass spectrometer에서는 25%보다도 더 많은 에러 가능성이 있다…실제 스펙트럼은 100개인데 1000개가 나올수도 있음
• Beltway and Turnpike Problems
• 두 문제 모두 polynomial한 알고리즘이 밝혀지지 않음
• turnpike의 경우에는 pseudo-polynomial한 알고리즘은 증명된 바 있음
• 점의 개수에 대해 polynomial한게 아니라 segment의 길이에 대해 polynomial함

• From Sequence Comparison to Biological Insights
• sequence alignment의 중요성
• 길이가 다른 여러개의 sequence를 앞/뒤나 중간에 띄워놓아서 sequence간의 공통 부분을 찾아내는 것
• Cystic Fibrosis
• The Alignment Game and the Longest Common Subsequence
• dynamic programming을 이용하여 해결해야 함. genome의 크기가 크기 때문에
• 두개의 스트링을 비교하며 맞을 경우 match, 안 맞을경우 mismatch, 빈 공간을 넣을 경우 insertion 처리
• 하나의 스트링 입장에서 insertion은 다른 스트링에서의 deletion
• Longest Common Subsequence Problem이 됨.
• Input: 두개의 스트링
• Output: A longest common subsequence of these strings(unique 하지 않음)
• The Manhattan Tourist Problem
• Longest Path in a Directed Graph Problem(irregular grid)
• The Change Problem
• Input: integer money & array of positive integers(돈의 단위)
• Output: minimum number of coins with denominations(단위) that changes money
• Greedy 알고리즘을 사용하면 최적의 해가 되는 경우가 있음(우리나라 단위 시스템의 경우)
• 안되는 경우 Recursive한 방법을 쓰면 됨. 하지만 이 경우에는 동일한 항목에 대한 계산을 여러번 하게 된다는 문제점이 있음
• 해결책: 다이나믹 프로그래밍 - 한번 계산한 항목을 저장
• biology에서는 평균적으로 alignment가 잘 맞는것 보다 local하게 alignment가 완벽하게 맞는것이 더 중요할 때가 많다
• homeobox genes
• gap penalty
• multiple sequence alignment
• 비교해야 하는 sequence의 개수가 증가할수록 시간이 exponential하게 늘어나기 때문에 exact한 답을 구하기는 거의 불가능하고 approximation 할 수밖에 없음 - suboptimal solution
• profile을 이용
• asymptotic: 점근선의

• Which Yeast Genes Are Responsible for Wine Making
• diauxic shift: yeast가 자신의 metabolism을 바꾸는것(glucose를 먹고 살다가 주변에 없으면 ethanol을 먹고삼)
• diauxic shift가 발생하기 이전, 당시, 이후에 yeast의 gene expression을 관찰 -> 비슷한 behavior의 gene들을 clustering함
• clustering
• k-center clustering problem
• noise에 민감함
• 해결방법: maximal distance 기준으로 center를 정하던 것을 squared error distortion 기준으로 수정 => k-means clustering problem
• 하지만 k-means의 문제점 -> NP-Hard for k>1임 따라서 approximation을 하여 suboptimal solution을 구함
• lloyd algorithm
• k-means clustering 알고리즘
• 항상 converge함
• hard/soft clustering
• soft clustering: clustering with responsibility
• stiffness parameter를 통해 hard clustering-soft clustering의 정도를 조절할 수 있음
• From Coin Flipping to k-means Clustering
• clustering은 em(expectation-maximization) 알고리즘의 일종
• Hierarchical clustering
• k가 주어질 필요 없음

02 Motif finding

• greedy approach
• randomized approach
• gibbs sampling
• expectation-maximization

03 Graph for string reconstruction: Assembly

• overlap graph
• de Bruijin graph
• hidden Markov model for gene finding

04 Structural variations

• insertion/deletion
• translocation

—

• metagenomics
• string match
• genotype(유전형) vs phenotype(표현형)
• DNA sequencing
• sequencer를 이용하여 할 수 있다
• 실제 dna에서 ACGT string을 얻어내는 과정
• Assembly
• 100~200개 되는 base pair를 이어 붙이는 과정
• 현재 기술으로는 sequencer가 모든 dna를 처음부터 끝까지 읽지 못하기 때문에 조각조각 읽어 붙이는것임
• Motif finding
• Text mining for biomedical literature
• 실제 literature를 train하여 어떤 term과 어떤 term이 관련 되어 있는지 알아냄.

<How do we find motifs?>

• motif: 반복되는 string
• k-mer = k-word = k-gram
• (k, d)-motif: k-mer that appears in each sequence with at most d mismatches
• consensus: 각 인덱스에서 가장 빈도수가 높은 애들의 string
• consensus의 conservation 정도를 측정하기 위해 entropy를 사용한다
• entropy가 높을수록 conservation 감소
• EM(expectation maximization)
• k-means와 방식이 비슷함: 실제 데이터를 반영한 모델을 만듬 -> 모델과 데이터를 비교 -> 업데이트 -> 반복
• 20쪽: 그대로 implement하면 두가지 문제가 발생
• 0이 하나라도 있으면 0이 됨 => pseudocount 개념 도입
• 확률에 로그를 취해줘야함
• randomised motif search
• global max를 보장할 수 없기 때문에 여러번 시행함(local max를 여러번 구해서 비교)

<Expectation Maximization>

• 어떤 데이터가 어디에 속하는지(classification)하기 위해서는 모델을 만들어야 한다
• 모델을 만드는 가장 간단한 방법 -> normal distribution
• class 정보가 주어지지 않을 경우: EM을 사용하여 hidden variable/parameter를 estimate
• naive bayesian classifier
• 한 개체가 하나의 cluster를 정하는 데에만 사용되는 것을 hard clustering이라고 함 => 결과가 extreme해질 가능성이 존재
• 하나의 개체에 대해 어떤 cluster가 될 “확률”을 계산하면 됨 = soft clustering
• 20쪽 k-means clustering은 hard clustering의 예이다
• soft clustering: EM for Gaussian mixture

<Gibbs Sampling>

• randomized motif search와 다른점
• randomized motif search may replace all k-mers in a single iteration
• gibbs sampling replaces a “single” k-mer at each iteration -> sampling with more caution
• relative entropy
• background probability 개념을 이용
• minimize the entropy of a motif matrix
• maximize the relative entropy
• “은/는”, “~이다” 와 같이 많이 등장하지만 중요한 의미를 갖지 않는 string을 처리하기 위함

<Assembly Problem>

• overlap graph를 만들면 쉽게 해결할 수 있음
• a의 prefix와 b의 suffix가 같으면 edge로 연결
• 모든 node를 딱 한번씩만 방문하는 path를 찾는 문제가 됨(Hamiltonian path problem)
• k-mer 자체를 node에 대응시키지 않고 edge에 대응시킴 => de Bruijn graph
• node는 edge의 prefix(TAA일 경우 앞의 노드는 TA, 뒤의 노드는 AA)
• 노드의 중복을 허락하지 않음(중복이 나올 경우 합침)
• Eulerian path problem이 됨(모든 edge를 한번씩 거침)
• Eulerian graph: eulerian cycle이 존재하는 graph
• Eulerian cycle: balanced & strongly connected
• 실제로는 k를 보통 50으로 잡아서 해결한다
• 너무 짧을 경우: 중복 edge가 많이 발생
• 너무 길 경우: 한 node의 크기가 너무 커짐 -> 메모리 이슈
• edge 여러개일 경우 해결법
• node간 edge가 여러개일 경우에 어떤 edge를 선택할까 하는 문제가 발생하게 됨. 그런 경우에는 k+1 mer 그래프를 그림. unique path가 생길 때까지 k를 늘려간다
• paired composition
• 방향을 양쪽으로 해서 읽으면 뒷부분에 대한 정보가 추가적으로 생김 => 어떤 edge로 이동할 지 priority를 정해줄 수 있음
• maximal non-branching path
• 노드간 edge가 여러개인 경우 그냥 그래프를 따로 나눈다. => 결과로 나온 여러가지 그래프를 실험적으로 맞춰봄

<Hidden Markov Model(HMM)>

• Markov chain
• trainsition probability를 고려한 모델
• inhomogenous Markov chain
• different distributions at different positions in the sequence
• ex) DNA sequence에서 맨 처음 위치에는 A가 올 확률이 높고 두번째 위치에는 낮고… 등등 이러한 정보를 반영
• MLE(Maximum Likelihood Estimators)
• CpG island
• ~ island: ~가 많이 있는 부분을 비유적으로 의미함
• dna 서열에서는 보통 gene이 등장하기 전에 CpG island가 많이 있음
• Hidden Markov Model
• state, state 내의 symbol, transition probability, emission probability를 정의한다. 어떻게? 데이터를 학습시켜야함!
• 어떤 종류의 problem을 해결할 수 있을까
• how likely is a given sequence?(forward algorithm)
• 길이가 같은 sequence들의 모든 조합 중 특정 sequence가 나올 확률(결론적으로 state를 고려함)
• what is the most probable path for generating a given sequence?(viterbi algorithm)
• 어떤 sequence가 주어졌을 때 그 sequence의 state 변화를 예상
• how can we learn the hmm parameters given a set of sequences?(forward-backward(baum-welch) algorithm)
• viterbi algorithm은 꽤 fair하게 state변화를 감지 할 수 있지만 정확하게는 감지할 수 없을수도 있다. 따라서 이런 경우에는 state 모델을 잘 설계하는것이 효율/성능을 높일 수 있다.

<How Do We Locate Disease-Causing Mutations?>

• Combinatorial Pattern Matching
• genotype-phenotype(표현형)간 관련성을 연구하는 것이 중요
• read mapping: reference genome에서 어떤 부분이 read와 대응되는지 찾는 것
• Trie: 그래프 자료구조의 일종
• store pairs of keys and data
• represent a collection of strings whose edge has a character
• suffix tree: trie를 compression한 것
• burrows-wheeler transform
• genome을 run-length encoding이 가능한 형태로 만드는 transform
• run-length encoding: aaaabbbccc -> 4a3b3c

• assignment 0:  virtualbox랑 ubuntu(14.04) 다운받기

OS Basics

• Von Neumann architecture = CPU + Memory + Storage
• CPU = Register + PC + ALU 

“Three Easy Pieces” -  Virtualization, Concurrency, Durability

• Virtualization: The OS takes the physical resources and transforms into virtual form of itself(OS is often referred as virtual machine)
• Concurrency: multi-thread
• Durability: surviving failure(persistence)

When a program runs:

Fetch -> Decode -> Execute

• c에서 volatile을 쓰면 해당 변수에 접근할 때 마다 캐시 대신 메모리에 접근한다
• SSD: solid-state drives

• data abstraction 
• procedural abstraction
• lazily: on demand = not executed unless necessary
• memory load를 on demand로 한다
• 48쪽 memory 그림 사실은 거꾸로임 code(text)맨 아래, 그 위에 data, heap, 맨 위에 stack. stack은 밑으로 쌓이고 heap은 위로 쌓인다
• 49쪽 64bit architecture. 
• bss segment: guard page. 
• kernal space에는 접근할 수 없다
• process는 3개의 state를 가지고 있다 - running/ready/blocked
• 53쪽 실제 register context used by the xv6 kernel
• 54쪽 proc에서 중요한 것: mem, proc_state, parent, context, tf
• 57쪽에서 return value빼고 parent에서 child로 모두 복사됨. child의 return value(address)는 0임! -> parent와 child 구분법
• %>/.program의 parent: bash

OS는 physical CPU를 time sharing을 이용해서 공유해야 한다. 이 때 고려해야할 것 두가지는:

1. performance
2. control

68쪽의 경우 run이라는 행위가 언제 끝날지 모르기 때문에 문제이다. (ex)infinite loop

+ 다른 프로그램에서 io를 access할 수 없음

kstack - kernel의 stack. 8kb

1. esp는 stack, eip는 code(text)를 가리키고 있다.
2. write()를 실행하면
3. eip는 kernel space, esp는 kernel stack을 가리킨다.

• 자원을 필요로 하는 프로세스에 자원을 배정해주는 것
• 스케줄링의 성능을 판단하는 기준:  turnaround time, fairness
• FIFO(FCFS)
• Convoy effect때문에 문제가 생김: 맨 처음 도착한 것이 엄청나게 오래걸릴경우
• SJF(Shortest Job First)
• 짧은 job들이 긴 job 실행 중에 도착할 경우 문제가 생김
• STCF(Shortest Time-to-Completion First)
• A가 실행되던 중 더 짧은 것이 도착하면 짧은것을 먼저 실행하고 A의 나머지는 그 다음에 실행함
• 스케줄링 성능 판단의 새로운 기준! response time
• 처음 schedule된 시간 - 도착한 시간
• 앞에 job이 있을 때 현재의 job이 길다고 맨 나중에 실행해버리면 답답할것이다. 적은 amount의 response라도 해야함
• 이전의 스케쥴링들은 response time이 안좋음
• RR(Round Robin)
• 하나의 job을 time slice로 잘라서 실행
• response time 훌륭
• 어떤 system이냐에 따라 적절한 size의 time slice가 필요
• 너무 작을 경우 response time은 좋지만 context switching 할 때 오버헤드 발생
• 너무 클 경우 반대의 장단점.
• real-time system의 경우 슬라이스를 작게하는것이 좋다 ex)미사일
• Incorporating I/O
• I/O가 개입될 경우 CPU 활용도를 최대한으로!
• Multi-Level Feedback Queue(MLFQ)
• priority마다 queue를 만듦. 내부에서는 rr실행
• 예) 어떤 job이 CPU를 오래 점령하고 있으면 priority를 낮춤
• CPU를 오래 사용하지 않는 interactive job은 priority를 높은곳에 둠
• 만약 interactive job이 엄청 많다면 long running job은 실행되지 못할것이다 -> starvation
• 90%정도 완료될 경우 yield하면 됨
• rule 5: 주기적으로 boost 진행(모든 프로세스를 맨 위의 queue로 이동)
• Proportional Share
• job이 필요로 하는 resource를 수치로 나타낸 후 퍼센트를 부여한다(CPU 점유 시간의 비율)
• Stride Scheduling(보폭 스케줄링)
• (A large number)/(the number of tickets of the process)
• 보폭은 스케줄링 대상을 의미한다

//과제2 String Scheduling + MLFQ 

• OS가 각 프로세스에게 가상의 memory space를 제공 -> 각각의 프로세스마다 CPU를 가지고 있다고 볼 수 있음
• 이전에는 메모리에 한번에 하나의 프로세스만 할당될 수 있었음. 효율성 .. 참담
• 그래서 Multiprogramming과 time sharing이라는 것이 나옴.
• 메모리에 여러개의 프로세스를 조금씩 할당하는 것
• 하지만 protection issue를 초래할 수 있음..
• 자기가 아닌 프로세스에 접근 가능할 수 있어서 다른 프로세스를 손상시킬 수 있다
• protection issue를 어떻게 resolve 하느냐
• 프로세스마다 address space를 만듬
• 실행되고 있는 프로세스에 관한 모든 정보를 포함하고 있는 애(program code, heap, stack 등)
• 힙은 아래를 향해 쌓이고 스택은 위를 향해 쌓이는 이유
• 둘 다 dynamic하게 쌓이거나 없어지기 때문에 딱딱 나누어 같은 방향으로 쌓이게 하면 비효율적일 수 있다
• Memory API
• malloc()
• system call이 아닌 library function이다
• free()
• new()
• delete()
• 포인터는 스택에 저장됨
• string을 allocate할 때는 \0자리까지(1byte) 해서 malloc해야함. 안그러면 string의 끝이 어딘지 알수 없으니까
• Memory Leak
• “valgrind”: 메모리 leak되는 곳을 찾아주는 프로그램
• unused code를 free해주지 않으면 메모리에 계속 쌓여서 메모리가 다 차면 프로세스가 죽어버림
• malloc은 brk라는 system call을 사용한다
• 그래서 직접 brk/sbrk를 사용하면 안됨! malloc이나 free 자신이 스스로 하기 때문에 따로 하면 충돌할 수 있다
• brk는 프로그램의 break를 확장할 때 쓰인다
• break: address space내의 heap의 끝 주소
• good memory allocation -> jemalloc.so 또는 tcmalloc.so  (so: shared object)
• LD_PRELOAD = “/usr/(local/)lib/libjemalloc.so._
• 이렇게 하면 lib.c가 아닌 저기에 define 되어있는 function들을 대신 사용함
• main호출 전에 실행하고 싶은 것이 있을경우 library에 정의하고 LD_PRELOAD에 메인함수 전의 directory에 해당 library를 정의해놓으면 된다
• LD_PRELOAD는 굉장히 고급스킬임
• Address Translation
• 프로세스가 가진 address space안의 local address(0~16kb)는 실제 physical memory안의 address(0~64kb내의 어떤 16kb만큼의 space)와 다르기 때문에, 두개의 address를 서로 바꿀 수 있어야함
• OS는 이 작업에 최대한 관여를 안하는 것이 좋음. 하드웨어로 처리하는 것이 가장 빠르기 때문에
• Assumptions
• 1) user의 address space는 memory에 연속적으로 위치해 있다
• 2) address space의 크기는 memory의 크기보다 작다
• 3) 모든 address space의 크기는 같다
• Hardware-based Address Translation(Dynamic Relocation)
• 하드웨어가 virtual address를 physical address로 번역한다
• 소프트웨어(운영체제)만을 이용하여 번역하면 아주 오래걸리기 때문에 하드웨어의 도움이 필요하다
• 34쪽에서 5번 번역해야함. 아주 비효율적.
• base and bounds register를 이용!
• address space에서 bounds register라는 것을 가지고 있게 한다
• bounds register: 내 address space의 크기 (or +base)
• physical memory에서 base register라는 것을 가지고 있게 한다
• base register: 해당 address space가 시작하는 위치 
• base부터 bound만큼의 address space가 있다는 것을 알 수 있다. (Virtual Address + base = Physical Address)
• 이렇게 하면 translation 자체에는 OS가 관여할 필요가 없게됨. base만 CPU가 알아서 더하면 되니까
• 단, OS가 꼭 관여해야 하는 부분이 있음
• process가 시작할 때: physical memory에서 address space를 위한 공간을 확보할 때 -> free list를 찾음(사용되지 않고 있는 physical memory의 범위)
• process가 끝났을 때: 
• context switch가 발생할 때: PCB에 base-and-bounds pair를 저장해야 함
• process당 하나의 base and bound를 쓰는 것의 단점
• 비효율적이다 왜냐하면 heap과 stack사이에 free(unused) space chunk가 생기게 됨
• Segmentation: 따라서 한 process의 code, heap, stack마다 각각의 base and bound를 생성!
• virtual address를 두 파트로 나눔: segment와 offset으로.
• segment: address space내의 code인지, heap인지, stack인지 indicate하는 부분
• 왜 segmentation fault라고 하냐: 나에게 허용된 segment의 base와 bound를 넘었기 때문에
• hardware support
• 각 segment가 어떤 방향으로 자라는지 알고있어야 함
• read/write/execute등 각 segment가 어떤 작업에 허용될 수 있는지 알아야 함
• bound를 absolute값으로 잡으면 메모리를 더 차지하게 됨

• finding a free chunk of memory that can satisfy the request and splitting it into two: when request for memory allocation is smaller than the size of free chunks
• 링크드리스트를 이용하여 관리
• 실제 메모리의 bound말고 주소공간의 heap을 증가시키고싶다. 그것이 미덕
• Coalescing
• free list의 여러 node들을 하나의 node로 합치는 것
• free list의 node들이 contiguous할 때만 coalescing할 수 있음. 만약 떨어져있으면 안 free한것들까지 포인터를 다 바꿔줘야하는데 이건 불가능에 가깝다
• free(void *ptr)
• 어떻게 free해 줄 포인터의 size를 아느냐???
• malloc으로 메모리 할당해줄 때 요구한것보다 조금 더 해서 size 정보 등을 저장해놓기 때문에 거기서 알 수 있음
• magic number: 현재 사용되고 있는 process인지?
• Segregated List
• Slab Allocator
• on demand하게(free list에서) 말고 같은 size의 cache를 미리 allocate하여 요청이 있을때 바로바로 제공 (kmem_alloc/ kmem_cache)
• Buddy Allocation
• Binary Buddy Allocation
• free space를 계속 반으로 나누어 요청된 메모리를 수용할 수 있는 최소한의 space를 제공
• coalescing할 때 나의 buddy만 check하면 됨

• essence of memory virtualization
• Segmented Architecture
• 장점: address translation이 빠르다(하나의 adder logic이면 가능)
• 단점: 
• 외부단편화(요청한 메모리 양에 비해 segment가 너무 작아서 안들어가는 경우)
• 내부단편화(제공된 메모리 양이 모두 사용되지 않아 낭비될 경우)
• Swapping 옵션 제한
• segment가 작을수록 fragmentation이 적게 일어남. 그럼에도 불구하고 엄청 작게 하지 않는 이유는 process에 대해 segment를 관리하기가 어려워지기 때문이다
• Page: multiple fixed-size segments with mapping table
• process의 address만을 나누지 말고(segmentation) physical memory space도 나누자
• page table은 process마다 생성됨 -> context switch가 일어날 때마다 base-bound pair도 저장해야하기 때문에
• 장점: flexibility + 
• free space를 squeeze 할 필요가 없음. 그냥 사용할 수 있는 페이지를 보고 제공하면 됨.
• Address Translation
• page number + offset
• Page Table은 handle 하기 어려울 만큼 커질 수 있음
• 그걸 address space에 저장??? 안돼…
• Physical memory에 저장하고 process마다 어디에 저장했는지 기억한다.
• PTBR(Page Table Base Register)(=CR3) 레지스터는 자신의 페이지 테이블의 base(처음)를 가리킨다.
• 뭘 하려면 PTBR이 가리키는 곳에 가서 어딘지 보고 그 주소의 메모리에 가서 정보를 가져옴..50 cycles…too much memory reference->MMU(Memory Management Unit)로 해결!
• MMU에는 TLB라는 것이 있어서 mapping table의 cache로 작용한다. Memory-Address간 translating 없이 아주 적은 cycle로 해결 가능
• 실제 주소 = CR3 + VP# * 4byte
• page table을 효율적으로 만들어야한다. 모든 page에 대해 64bit 안에 맵핑할 수 있도록
• code, stack, heap에 page 하나씩 세개의 페이지면 충분하다
• 페이지 테이블에 존재하는 flag:
• valid/protection/present/dirty/reference bit
• 페이징의 문제점:
• extra memory access
• memory utilization for page table
• 46, 47쪽:
• edi -> &array[0]
• edx -> i
• 4 -> &(array + i * sizeof(int))
• array는 위쪽 주소에 있다(4만) 왜냐하면 function 내부(stack)에 정의되어있기때문에
• 그래프의 의미: paging때문에 memory access를 한번 더해야한다(page table 한번+실제 값을 fetch하기 위해 한번)

• 프로그램 실행 시간은 clock cycle 속도보다 cache에 의해 결정된다
• vpn: virtual page number

• multiple execution flows within a process
• 실행 단위: thread
• 각자의 program counter와 register를 가지고 있다
• address space가 바뀌지 않기 때문에 process간의 context switching 보다 빠르다

• race condition(=data race)
• 여러개의 스레드/프로세스를 동시에 돌릴 때 같은 변수를 수정하면 그 여러개만큼 수정되지 않을 때
• atomicity를 보장하기 위해 lock을 이용하여 임계 영역을 지정해주어야 함

• performance가 증가했다가 유지되지 않고 감소하는 이유(spinlock에서)
• 1. convoy effect
• t1이 락을 가지고있으면 다른 스레드들도 cpu를 사용(burn)하고 있지만 t1락이 풀릴때까지 뭔가를 process 할 수 없다. 따라서 이 경우에 멀티쓰레드 상황은 performance를 worsen할 뿐이다
• 그래서 critical section는 적으면 적을수록 좋다
• lock holder인 t1에게 cpu시간을 많이 주어서 언락을 빨리 할 수 있게 하면 좋다
• 2. cache invalidation
• 락홀더가 캐쉬에 있는 값을 바꾸면 다른 쓰레드들에게 값을 똑같이 바꾸라고 보내는 메시지. 메시지가 있는 동안에는 process를 할 수 없음
• 하드웨어의 메시지 (메모리 버스)
• moesi, mesi protocol
• Thread API
• process의 시작은 fork. thread의 시작은 start_routine
• join: 어떤 스레드가 끝났는지 안끝났는지 알 수 있는 방법
• BSP(Bulk Synchronous Processing): 한 태스크를 여러 스레드로 돌리고, 다음 태스크로 갈 땐 이전 스레드들이 모두 끝났는지 확인해야함
• trylock(lock이 되어있으면 failure, 안되어있으면 락 - opportunistic locking), timelock(일정시간 이후 락을 풀음)
• condition variables: thread의 상태를 나타냄(wait(=sleep)/signal(=wake))
• 락 안에서 자면 안됨. 아무도 깨울수가 없음…
• 그래서 락 안에서 잘 경우 바로 락을 풀어야함

• 두가지 상태가 있다: available = unlocked, acquired = locked
• pthread는 lock에 관련한 여러 api를 제공한다
• interrupt는 현재 execution flow를 방해할 수 있는 최상의 priority를 가진다
• lock에서 interrupt를 disable한다? 안됨. 다양한 문제가 발생한다
• atomic instruction을 사용하는 애와 안사용하는 애가 shared variable을 사용하기 원하면 atomicity를 보장할 수 없음. 따라서 모든 instruction이 atomic하도록 주의해야함!!
• 만약 어떤 variable이 발생하는 곳에 락을 걸면 그 variable이 나오는 모든 코드 부분에 똑같이 락을 걸어야함
• ticket lock에서 발생할 수 있는 문제: 같은 번호의 티켓이 두개의 프로세스에 발급될 경우(티켓 발급이 atomic하지 않을 경우)
• spinlock 해결방법
• spin하려고 할 때 yield한다
• context switch 비용 발생
• 따라서 critical section이 작을 때는 spin waiting 하고 클 때는 yield하면 좋다
• sleeping
• 이것도 주의할점이 있음. 영원히 잠드는 애가 발생할 수 있다
• futex
• 영원히 잠드는것을 방지
• two-phase locks
• lock을 두 단계(phase)로 나눔

• file = named permanent storage
• data와 metadata를 포함하고 있다
• directory
• collection of files/directories
• file system은 logically continuous하고 physically spread하다. process에서의 page table처럼
• file allocation table(FAT)
• “direct” mapping table
• allocation 작업이 O(1)이기 때문에 아주 빠르다는 장점이 있다
• direct하기 때문에 search는 오래걸림(linear time)
• 따라서 general purpose에 적절하지 않음
• Inode
• fat와 달리 direct하지 않기 때문에 서치가 비교적 빠름(logarithmic time)
• mmap: system call로 하지 않고 memory operation으로 실행. a few cycle 뿐이기 때문에 시간이 아주 절약된다
• file system을 durable하게 만드는 방법
• write하는 것을 자주 저장(survive in short term)
• 데이터를 오래 저장할 수 있게 함
• 데이터를 여기저기 복제해놓아서 independence of failure를 보장

• RAID(Redundant Arrays of Inexpensive Disks)
• level이 올라갈수록 redundancy가 증가
• level 0: striping
• 라운드로빈을 이용하여 여러 디스크에 block을 나누어 저장
• performance와 capacity가 훌륭함
• 그림에서 (0,1,2,3)을 하나의 stripe set이라고 한다
• 실제 field에서 아주 기본적이고 중요한 technique
• no redundancy
• level 1: mirroring(=replication)
• redundancy가 존재하기 때문에(같은 data를 여러번 저장) 시간이 오래 걸린다
• level 4: saving space with parity
• 하나의 디스크를 추가하여 같은 stripe set에 있는 정보를 해당 디스크에 저장
• level 5: rotating parity
• parity block을 하나의 디스크가 아니라 전체 디스크에 돌아가며 저장
• 보통 0+1을 합쳐서 사용한다

The Turing test is a test, developed by Alan Turing in 1950, of a machine's ability to exhibit intelligent behaviour equivalent to, or indistinguishable from, that of a human.

• Unintelligent human behavior - 기대값이 -임에도 불구하고 복권을 사는 행위
• AI는 어떻게 보면 moving target이다 - OS가 AI로 불리던 시절도 있다.
• lisp: programming language
• 여러 technology의 collaboration 결과가 바로 deep learning이라고 할 수 있다 - 소프트웨어, 하드웨어..
• Modeling -> Algorithms의 두 단계로 real-world task를 tackle한다.
• 무엇을 풀지 정하고, 어떻게 풀지 정한다. 그 과정에선 어느 정도의 abstraction이 필요함.
• reflex-based model < state-based model < variable-based model < logic-based model 등 여러가지 모델이 있다 (low-level -> high-level 순)
• 각 모델마다 풀 수 있는/풀기 쉬운 문제의 종류가 다름
• what을 정할 때 computing이 가능할 지 안할지 고려해야 함. 따라서 how보다는 what이 대개 더 어려운 문제이다
• Learning algorithm내에서 example을 학습하고 generalization을 해야 의미가 있다. 그냥 예시만 학습(단순 암기)하면 머신러닝이 아님. 의미가없다.
• 31쪽 그림에서 node 하나하나를 각각의 state라고 한다
• 하나의 state에서 다음 state로 가는 순서가 중요한 경우에 state-based model을 사용한다. sudoku의 경우에는 그렇지 않음. 그래서 variable 측면에서 문제를 해결하는 것이 바람직함.
• 37쪽 hard constraints의 의미: 반드시 만족해야 하는 것으로 하나라도 만족하지 않으면 solve된 것이 아님.
• 반면 Bayesian network에서 soft dependencies의 의미: H1을 1분마다 차의 위치라고 하면, 여기서 위치는 반드시 만족하는 것이 아닌 단지 확률의 문제일 뿐이다
• 40쪽: 해당 문제를 variable-based 모델로 해결하려면 student를 하나하나를 variable로 표현해야하기 때문에 비효율적이다.
• 모델끼리 concept을 합쳐서 구현하는 경우도 있다

• feature를 어떻게 설계하느냐에 따라 전체 설계의 성능이 달라진다. 가장 중요한 부분
• raw data보다 feature를 더 크게 사용하는 경우는 없다 왜냐하면 raw data가 주어진 데이터의 총량이기 때문
• production system: production rules로 이루어진 시스템.
• if-then으로 이루어져있다

• 숫자판 문제에서 가능한 9!개의 상태를 하나의 노드로 생각 하면 9!개의 노드를 가진 그래프라고 생각해서 풀면 됨 - 스테이트 마다 각각 연결할 수 있기 때문 - 하지만 여기서 문제는 3*3, 4*4는 가능하지만 5*5는 불가능하다. 너무 크기 때문에
• 숫자가 움직이느냐/blank가 움직이느냐 의 차이: 32개의 액션/ 4개의 액션
• 9!개 노드가 있는 그래프를 스태틱하게 계속 가지고 있으면 비효율적임. 다이내믹하게 그때그때 필요한 부분만 빌드해서 쓰는게 중요하다 -> implicit representation
• start state는 주어질 수도 아닐수도 있다. 따라서 알고리즘 내에서 start state를 정의할 수 있어야 함
• state를 expand한다: 하나의 상태에서 다음 상태로 가능한 상태들을 계산하는 것
• 15쪽의 수도코드는 expand만 하고 지우는게 없음. 
• 20쪽의 수도코드는 좀 더 refined된 버전
• fringe: expand되지 않았지만 expand되기 위해 대기하고 있는 노드들의 집합
• goal인지 아닌지는 fringe에 들어갈 때가 아닌 dequeue 될 때(해당 노드를 expand 할 때) 판단한다
• state와 node를 혼용해서 쓰는 경우가 많다. 
• “node는 어떤 state를 나타내기 위한 것”
• search stretegy의 평가 기준
• time complexity: 만들어지는 노드의 총 수
• space complexity: 어느 한 “순간”에 메모리에 있는 최대 노드의 수. 전체 프로세스에서 만드는 총 노드의 수가 아님
• 두가지 complexity는 b,d,D의 세가지 변수로 계산할 수 있다
• b는 트리의 차수
• 23~ 26쪽 fringe의 queue (breadth-first search)
• A
• BC
• CDE
• DEFG
• 같은 레벨의 노드들(successor)간의 순서는 상관 없다
• 28쪽 
• time?: b(b^d-1) 은 트리의 d레벨의 마지막노드가 goal일 경우이다.
• 그럼 goal test를 fringe에 들어갈 때 하면 안되냐? 된다. 더 효율적임 breadth-first search에서만. 일반적인 경우에는 fringe에서 dequeue될 때 goal test를 해야 편하다 => exponential
• space?: 각 레벨에서의 노드들만 저장하고 있으면 된다. 부모 노드들(goal test가 끝난 노드들)은 잊어도 됨 => exponential
• optimal?: 가장 shallow한 노드에 대해 goal test를 먼저하기 때문에 yes.
• 29~40쪽 fringe의 stack (depth-first search)
• A
• BC
• DEC
• HIEC
• IEC
• EC
• JKC
• KC
• C
• so on
• 같은 레벨 노드 순서 역시 상관 없다
• 레벨을 계속 내려가다가 더 이상 갈 곳이 없으면 다음꺼… 반복
• 그림상에는 모든 노드가 있지만 까만색으로 색칠된 노드들은 스택에서 빠져나갔기 때문에 실제 메모리상에는 존재하지 않는다.
• 41쪽
• complete?: infinite loop에 빠질 가능성 존재
• time?: 최적의 경우 한번에 찾을수도 있지만 최악의 경우 모든 노드를 찾아봐야 할수도 => exponential
• space?: 최악의 경우 - 하나의 경로(D) * 나의 sibling(b-1) (가장 깊은 레벨의 첫번째 노드에서) => linear
• depth-first의 장점(메모리)을 살리며 단점(optimality)을 보완하는 방법: depth-limited search
• 42쪽
• limit l을 optimal depth로 정하는 것이 가장 좋다
• 하지만 optimal depth는 항상 알려진 것이 아니기 때문에 그런 경우에는 l을 작게 해보고 점점 늘려나가면 찾을 수 있다 -> iterative deepening
• limited search를 할 때 l의 범위 내에서 찾지 못하면 맨 위의 노드부터 (맨 처음부터) 다시 한다. overhead가 발생할 수도 있지만 overhead를 방지하기 위해 그 레벨의 노드를 모두 저장하면 결국 depth-first의 장점인 linear 메모리의 의미가 없어짐
• 43쪽 
• 이 그림에도 역시 스택에서 빠져나간 노드들이 그려져 있음. 실제 메모리에는 없다!
• backtracking: 하는것 처럼 보이지만, 실제 메모리는 그렇지 않음
• 44쪽
• chronological backtracking: 완전히 expand되지 않았지만 시간상 가장 최근에 만들어진(스택에 들어간) 노드로 backtrack하는 것

• 50쪽 Nids = O(b^(d+1))
• time에서 11%의 오버헤드가 발생하지만 그만큼 메모리라는 장점을 안고간다는 것에 의미를 둔다

• 51쪽 expand할 때 goal test를 해야하는 이유. link마다 cost가 있으면 더 깊은 node가 optimal goal일 수 있기 때문
• complete?: step cost가 양수나 0인 이유는 0인 루프가 있으면 infinite loop가 생길 수 있기 때문이다
• time?: C*/e 인 이유는 link 그대로 따지지 않고 step cost로 나누어서 단위 단계로 생각. (5면 1+1+1+1+1 이런식)

• 54쪽 기존 알고리즘과 다른 점은 closed에 기존 노드들을 저장. 이전 알고리즘들에선 지나간 노드들은 기억할 필요가 없었음

• heuristic function: 내가 얼마나 빨리 goal에 도달할 수 있는지 나타내는 함수. cost가 얼마나 남았는지. 지나온 길은 생각하지 않음. 
• 넓은 의미의 heuristic function은 evaluation function이라고 할 수 있다. 
• 숫자판 예시에서의 heuristic은 단지 추정값이고 정확하게 실제 “앞으로 얼마 남았는지”는 알 수 없다. 실제로 보면 7쪽에서 보면 5에서 6으로 간다. 따라서 그걸 따라가서 반드시 goal을 찾는다는 보장은 없다.
• 8쪽에서의 fringe는 min heap라고 생각하면 됨
• 9쪽 Greedy best-first search
• goal에 가장 가까운것 같은 node를 따라감
• Not complete라는 말 무시. 뒤에 보면 complete하다고 나와있음!
• 여태까지 본것중에 가장 비효율적인 알고리즘 같아 보인다. time과 cost를 보면
• A* search
• gb-f search가 왜 비효율적이냐면 여태 온거에 대해서는 다 까먹기 때문. 따라서 그것도 계산에 포함하면 꽤 효율적인 알고리즘을 찾을 수 있을것이다 그게 바로 a*: f = g + h
• h를 0으로 잡으면 UFS와 동일 => heuristic search라고 안한다
• 11쪽 마지막 조건: h*는 실제거리. 이 조건을 만족하는 그래프를 admissible heuristic이라고 한다
• 9쪽의 그래프에서 오른쪽애(h=4) 때문에 a* search를 쓸 수 없음
• 19쪽 앞의 핖티와 같은 알고리즘인데 expand부분이 좀 더 복잡
• successor가 처음 만드는 애면 값을 그대로 저장
• 이미 있으면 새로 계산해서 minimum한 것을 저장
• goal state의 h*값은 항상 0
• 21쪽 G는 9+0이고 C는 8+3=11이므로 둘을 비교함. G를 먼저 expand하려고 하던 중 goal test를 했는데 goal이니까 C는 expand 안하고 끝남
• h*는 우리가 아는 값. h는 정확히 알지 못하고 단지 추정하는 값일 뿐이다
• g는 expand하면서 구하는것이다. 처음부터 알려진게 아님
• 23쪽은 gbf서치를 이용하여 optimal path를 찾지 못한 예이다
• 24쪽은  a*를 이용하여 optimal path를 찾음
• 25쪽의 OPEN은 fringe임
• 둘째줄에서 h가 admissible(h* >= h)하다고 f* >= f라고 할 수 없음.
• 저렇게 말할 수 있는 이유는 f가 단조증가 하기 때문 
• admissible하면 단조증가한다(삼각형 공식)
• 어떤 노드든 expand할 때(fringe에서 뽑힐 때)에는 그 노드의 g가 optimal하다. 
• 28쪽 IDA*는 cutoff(limit)을 f로 한다
• A*는 좋아보이는데로 가면서 다 펼쳐본다면 RBFS는 가다가 아닌것같으면 backtrack해서 그 경로에 대한 정보를 기록함
• RBFS는 IDA*보다 시간을 조금 더 많이 쓰는 대신 메모리를 적게 쓴다
• SMA*: simple memory bounded a* 
• 내가 사용할 수 있는 메모리를 다 ㅏ사용함. 단 그 이상이 되면 RBFS처럼 backtrack함(가장 메모리를 많이 차지하는것을)

• 그럭저럭 괜찮은 알고리즘
• 3쪽에서 hill의 가장 높은 곳(evaluation 값이 큰 곳)으로 올라가는 것이 목표 
• 지금보다 낮은 곳으로는 가지 않고, 경사가 가장 높은 곳으로 감
• 따라서 내 주변에 낮은 곳만 있을 때 종료됨 -> local optimal은 찾을 수 있지만 global optimal은 못찾을 수도 있음.
• random restart: 한번 search가 끝나면 random한 위치에서 다시 search를 진행함 (존재할 수도 있는 global optimal를 찾기 위해)
• 7쪽 simulated annealing search
• hill climbing search처럼 낮은 곳은 아예 제외하는게 아니라 확률적으로 낮은 곳으로 갈 수도 있음
• T = f(t)
• T는 temperature, t는 time, f(x)는 정하는 것
• next 위치를 랜덤으로 설정하여 현재보다 높으면 가고, 낮으면 확률을 따져서 가거나 가지 않음 
• 확률 공식을 보면 온도가 낮을수록 optimal에서 멀어질 확률이 적게 설계되어있음. 그리고 e에 대해 exponential하니까 처음에는 많이 헤메고 확 떨어져서 오랫동안 조금씩 헤매게 함 (꼭 나와있는 공식대로 쓸 필요는 없음. design issue!)
• 온도를 천천히 낮추면 global optimal을 찾을 확률이 높음
• 이론상 온도를 무한히 천천히 낮추면 global optimal을 찾을 수 있다
• 너무 복잡한 문제가 있을 때 어려운 솔루션을 찾는 대신 지푸라기 잡는 심정으로 아주 단순한 위의 알고리즘을 이용할 수 있다
• propositional satisfiability: 주어진 논리식에 0 또는 1을 대입하여 결과가 1이 나올수 있게 할 수 있는지 여부 -> SAT solver를 이용해서 해결할 수 있음 

• 앞에서 배운것들과 달리 예측 불가능한 요소가 존재한다: 상대의 움직임, chance
• ply: 플레이어 하나의 차례. 2 ply = 1 move. move가 하나의 의미있는 단위임
• utility: 하나의 terminal state마다의 효용성(승리/패배 혹은 얻은 돈/잃은 돈)
• 보통 첫 플레이어를 max라고 함. utility를 max의 입장에 따라 정하기 때문
• Minimax: min과 max 모두 best play를 한다고 가정. 즉 max의 입장에서 상대인 min은 가장 불리한 play를 함
• dfs
• b: branching factor/m: maximum depth
• ab pruning
• 18쪽 doubles solvable depth의 의미: depth는 m, branching factor를 루트b로 줄어듬. 그냥 minimax와 같은 시간(b^m)으로 계산 한다면 depth를 2m만큼 search할 수 있다.
• random ordering은 같은 시간 안에 (4/3)m만큼 search할 수 있다
• heuristics: 같은 depth의 node들에 대해서 해당 레벨에서의 max/min한 해를 기억하고 있다
• DFID할 때 이전 iteration에서의 max/min값을 기억하고 있음
• 19쪽: quiescence search - eval값이 dynamic하게 변하는 상황 말고 잠잠한 상황에서 cut off를 한다. (병사 잡히고 다음에서 말을 먹을 수 있는 상황/병사를 먹고 다음에서 말을 잡히는 상황)
• 정확한 값일 필요 없음
• Expectiminimax
• 정확한 값이 필요
• TDGammon은 알파고같은 백개먼 게임 프로그램임. 두 수 앞을 내다본다
• Games of imperfect information
• 카드게임처럼 상대의 패를 모르는 경우에는 모든 가능성에 대한 확률을 구할 수 있다. 

• CSP가 아닌 constraint가 없는 일반적인 dfs에서는 pruning을 하지 않음
• CSP는 dfs의 중간 단계에서 constraint를 만족하는지 여부를 통해 pruning이 가능하다는 점이 기존의 일반적인 dfs와 비교해서 하나의 장점이 될 수 있다
• expand하지 않고 constraint를 만족하는 애들만 자식으로 삼는다
• optimization을 할 때 주로 local search를 쓴다
• 10쪽에서 root노드에 4개의 자식을 다 하지 않는 이유: symmetric하기 때문에 두개만 해보면 된다
• 밑의 예시에서는 땅이 variable, color가 value
• Minimum remaining values
• 앞에서 배운 heuristic처럼 value를 선택하는 것이 아니라 MRV를 가진 “variable”을 선택함
• 가장 남은 값이 적은 variable을 선택
• Most constraining variable
• 다른 variable에 대해 가장 많은 영향을 미치는 애를 우선적으로 선택
• 13쪽의 예에서는 다른 면과 가장 많이 맞닿아 있는 애
• Least constraining value
• 남은 variable이 최대한 다양한 value를 가질 수 있게 하는 값을 가진 애
• variable은 failure를 빨리 찾는 방향(까다롭게), value는 constraint를 만족하는 방향으로 이동
• Backtracking 효율적으로 하기 위한 것들
• Forward checking
• 남은 variable이 가질 수 있는 value들을 기록함 -> 어느 하나라도 공집합이 되면 backtrack함(가장 최근에 한 assignment를 undo)
• Constraint propagation: 공집합이 되지는 않았지만 인접한 두개가 같은 색(파랑)이 남았으므로 failure를 detect하게 함
• Arc consistency: 모든 vi에 대해 어떤 vj가 constraint를 만족한다면  vi->vj는 consistent하다고 한다
• preprocessor이나 postprocessor로 이용될 수 있음
• 따라서 assignment가 발생하면 나를 쳐다보는 unassigned된 애들이 constraint를 만족하는지 모두 살펴봐서 아니면 안되는 value를 지워서 consistent하게 만들어야한다. 
• time complexity: O(n^2 * d^3) -> 최대 n^2개의 edge가 있을 수 있음 * edge는 queue에 최대 d번 들어감 * value하나에 대해 constraint를 만족하는지 확인하는 횟수(RM-Inconsistent-Values)는 d^2
• SAT는 가장 대표적인 CSP문제이다: variable이 가질 수 있는 value는 0또는 1, constraint는 식의 결과가 1이어야 한다는 것
• 경로문제에서 어떤 경로에 대해 consistent하다는 것(path consistency)은 보장할 수 없음. pair-wise로 계산하기 때문에.
• map coloring의 경우에는 preprocessor의 의미가 없음: 맨 처음에 아무것도 색칠되지 않은 상태에서는 inconsistent한 값이 없으니까
• chronological backtracking: 가장 최근에 했던 것을 undo하는 방식
• 26쪽: local search와 비슷해 보이지만 backtracking을 하면 heuristic repair이고 현 상태만 가지고 있으면 local search임
• CSP로 풀 수 있는건 대부분 local search로 풀 수 있음

//중간고사 CSP까지

1. TF

2. A* 수도코드 잘못된 것

3. 확률 Minimax

4. NQueens forward checking + Arc consistency

5. Forward Checking + Arc Consistency

• 예전의 번역기: 어떤 언어를 하나의 언어로 바꾼후 그것을 목표 언어로 바꿈
• 현재의 번역기: 목표 언어로 바로 바꿈
• 어떤 독립적인 기능을 수행하는 단위를 agent라고 한다. 사람일수도 로봇일수도
• 3쪽
• Performance Standard는 고정하는것이 일반적.
• Problem generator: 실제 문제가 아닌 자기가 스스로 문제를 만들어보고 풀기위한 노력을 함. 여기서는 무시
• 4쪽
• representation: 어떤 알고리즘을 이용하여 학습할 것인가의 문제
• 피드백의 종류 세가지: supervised - 각각의 예제에 대해 정답이 주어짐, unsupervised - 예제에 대한 답이 없음, reinforcement - 예제에 대해 상과 벌을 줌 occasionally

• supervised learning은 대부분 inducted learning이다
• data의 pair(입력과 출력)을 보고 f에 최대한 근접하는 함수(h)을 알아내는 것이 목표
• f를 정확히 알아내려면 모든 x에 대해서 y가 일치해야 하는데 실제 상황에서 x가 유한하지 않기 때문에 모든 x에 대해서 확인할 수 없음
• training set에 없는 x에 대해서도 결과를 내는것 -> generalization
• 뭐가 중요하다고 생각하느냐(outlier가 있다고 생각하느냐 없다고 생각하느냐 등)에 따라 8쪽의 세가지 그래프 중 어떤식으로 하는게 바람직한지 달라질 수 있다. 파란색이 100% 다 맞췄다고 무조건 좋다고 할 수 없음

• linear predictor에 대해 배움 -> neural network
• 10쪽에서 0일경우에는 +1/-1 중 하나로 붙이면 된다
• 2차원: 직선, 3차원: 평면, n차원: hyperplane

Loss minimization

• optimization
• margin = (w*phi)*y
• 똑같이 positive라도 0.5와 1의 confidence는 다르다고 생각한다.
• 음수값이면 틀림, 양수값이면 맞음. 절대값이 클수록 얼마나 맞았고 얼마나 틀렸는지 알 수 있음
• 16쪽: 1[어쩌구]는 어쩌구가 맞으면 0, 틀리면 1을 리턴하는 함수
• residual: 실제값과 예측값과의 차이
• square loss: residual 제곱
• classification할때랑 regression할 때 무엇을 중심으로 error를 정할지 달라짐(margin/residual)
• 22쪽에서 squared loss를 사용하면 y가 최소가 되는 w값은 0, 2, 1000의 평균이고 absolute deviation을 사용하면 y가 최소가 되는 w값은 2(0, 2, 1000의 median)

Stochastic gradient descent

• squared loss를 사용할 경우 w가 하나일때는 미분해서 0되는값 찾으면 됨. 여러개일때는 변수 하나당 편미분해서 0되는값 찾음
• gradient: 기울기
• gradient descent: continuous space에서 하는 경우가 많음.
• initialize의 의미: 다 0으로 하라는게 아니라 랜덤값 넣으라는말
• hill climbing과 다른점은 모든 방향을 고려하는게 아니라 training data가 알려주는 방향으로 감
• step size가 크면 클수록 학습을 얼마나 과감하게 진행하느냐가 달라짐 -> learning rate라고 부르기도 함
• 27쪽 공식에서 변수는 w뿐이다(x, y는 주어지는것) 따라서 objective function을 w에대해 미분한 것이 gradient임
• gradient descent의 문제점: data가 엄청 많으면 한 iteration을 할 때 data를 한번 스캔해야하는데 엄청 오래걸린다. 따라서 모두 계산한 뒤에 iteration을 하지 않고 tuple하나하나 볼 때마다 iteration을 함(결과가 똑같지는 않음) -> stochastic gradient descent
• decreasing step size: simulated annealing에서 temperature과 비슷한 개념
• zero-one loss
• gradient가 항상 0이기 때문에 SGD를 이용할 수 없음. optimization은 loss에 비례해서 진행되니까
• 위의 문제를 해결하기 위해 hinge loss function을 이용
• hinge loss는 zero-one loss의 upper bound이므로 zero-one과 추구하는 방향은 같음
• 0<x<1 구간에서도 학습이 발생함
• loss가 클수록 loss를 줄이려는 노력을 더 많이함. zero one의 경우에는 줄이려는 노력이 같음 항상 1이니까
• logistic regression
• 모든 구간에서 미분 가능함
• 항상 upper bound는 아니지만 전체적으로 문제는 없음
• margin이 1을 넘어도 학습을 진행함
• SGD의 terminal condition
• 고정된 iteration 횟수를 넘길 경우
• weight update가 멈출 경우(미미할 경우)

• 여러가지 linear predictor를 합쳐서 하나의 predictor를 만드는 것. 단 합친 것이 nonlinear할 수 있게 하는 요소를 추가
• 2쪽에서 한단계로 학습하던 것(x -> y)을 3쪽에서는 두단계로 학습함(x -> h1 + h2 -> y)
• >=가 바로 NN을 nonlinear하게 만드는 요소(thresholding)
• NN에서만 할 수 있는 일이 있음. XOR은 단일 linear classification으로 학습할 수 없다
• sigmoid함수: zero-one함수를 모든 점에서 미분가능하게 흉내낸 것
• 8쪽: 1.5, -0.5, 0.5는 threshold value를 나타낸다. 1, -1은 weight.
• NN에서는 gradient descent를 backpropagation method라고 부른다
• d: desire (원하는 값)
• s: weighted sum
• f: sigmoid 함수
• ε: error
• error가 원하는값과 실제값의 차의 제곱이라고 하면 error를 s에 대해 미분한 것은 -2(d-f)
• 결과적으로 gradient만큼의 error를 고침
• 10쪽: layer간의 connection은 모두 complete bipartite하다
• k-layer feedforward network라고 함(feedback 되지 않음)
• 회색부분은 hidden layer이다
• j번째 레이어의 i번째 unit을 나타내려면 j를 위에 i를 밑에 쓴다
• threshold함수를 정하기 위해 dimension을 하나 추가하여 1로 둠 -> 11쪽에서 m(j-1)+1에서 플러스 1이 되는 이유. 1을 위해 unit이 따로 만들어주는건 아님
• 14: j+1번째 레이어의 unit들의 델타를 이용하여 j번째 레이어의 i번째 unit의 델타를 구함
• 뒤에서부터 앞으로 가면서 델타값을 결정 => backpropagation
• 15: 0인 이유는 같은 레이어의 unit들은 서로에게 영향을 끼치지 않기 때문
• train instance 하나에 대해서 각 unit별로 결과를 계산 -> backpropagation으로 weight를 업데이트
• generalization: 유한한 train set을 통해 나온 네트워크로 무한한 경우에 대한 추정값을 구할 수 있다
• 18: 일곱개의 점에 대해 함수를 구한다고 가정
• 무조건 에러가 적은 경우(high-degree)가 좋은가?
• 아님. noise가 존재할 수 있고, train data는 일부에 불과하기 때문. 따라서 train set으로 함수의 accuracy를 측정하는 것은 잘못된것.
• 그럼 전체를 모르는 상황에서 어떤 함수가 바람직한지 알수 있는가?
• 주어진 training set을 두개로 나눔: training set과 validation set -> cross validation
• k-fold cross validation: 적어도 몇번 이상을 해야 의미가 있다. 한번 하는건 의미 없음
• overfitting: 비슷한 에러를 낸다면 낮은 차수의 함수(2차원보다는 1차원 함수)를 이용하여야 방지할 수 있다
• underfitting: 데이터의 복잡도를 충분히 보장하지 않아 너무 낮은 차수의 함수로 나타내려고 하는것
• 21: validation set error 감소하는 부분은 언더피팅에서 정상으로 가는 부분, 증가하는 부분은 정상에서 오버피팅으로 가는 부분
• 앞의 모델(NN, decision tree, linear predictor…)은 parametric model(데이터에 알맞은 파라미터를 찾는 학습).
• nearest neighbor은 non-parametric
• regression이 아닌 classification에 사용
• 그냥 내가 가진 train set중 가장 가까운 애의 class를 리턴
• generalization을 한다기 보다는 storage의 문제

//과제

sigmoid함수가 1이상 -1이하일경우 그래디언트 값이 작기 때문에 convergence가 잘 이루어지지 않는다. 이것을 고치기. (= thresholding 함수바꾸기) 바꾸면 값이 제대로 안나올텐데 어떤 파라미터를 어떻게 바꾸면 잘될것이다 왜일까 생각해보기……………..

• binary classification을 이용하여 multi-classification을 할 수 있다
• 1인것을 classify할 때는 1인것과 1이 아닌것으로 classify하는식으로
• 5쪽에서 a의 세개 모델은 경향이 비슷, c는 세개의 경향이 모두 다르다. 경향이 다를수록 variance가 크다고 한다
• variance는 averaging하면 사라짐. bias는 averaging해도 사라지지 않음
• averaging해도 variance가 낮아지지 않으면 underfitting하고 있다고 생각할 수 있다 -> 차수를 높여서 해본다
• 모델이 덜 complex하면 bias가 있고 더 complex하면 variance가 있음 -> bias-variance간 tradeoff가 존재
• Ensemble method
• 트레이닝 데이터에 따라 디시젼 트리의 variance가 크게 달라지는것을 없애기 위해 여러가지 트리를 averaging함 (하지만 bias 감소효과는 미미)
• 트리는 트레이닝 데이터에 따라 트리가 많이 달라짐
• 하지만 다른 모델(뉴럴네트워크 등)에도 ensemble을 사용할 수 있음
• Bagging과 Boosting이 있음
• bagging은 literally sum의 의미가 아님.. 그냥 여러가지 모델의 결과를 종합하여 사용한다는 의미
• 12: I{~}의 의미 - ~가 참이면 1 거짓이면 0
• 엡실론과 알파는 반비례
• z는 normalize 하기 위한 상수
• 엡실론이 0.5보다 작을때만 이 알고리즘이 제대로 돌아감. 그래야 틀린게 많이 뽑히고 맞은게 적게 뽑힘

• genotype: 유전자 자체의 collection
• phenotype: genotype이 발현되어 나타나는것의 collection
• mutation: 유전자와 유전자가 재조합되어 발생하는 변이
• fitness: 생물이 얼마나 생존에 적합한지
• 제네틱 알고리즘: 랜덤 솔루션의 셋을 만들고 테스트 -> 비교적 안좋은 솔루션을 없애고 좋은 솔루션에 조금 변화를 주어 새로운 셋을 만들고 테스트. 베스트 솔루션이 충분히 좋을때까지 반복한다
• 19: program, fitness, crossover, mutation을 정해주어야함
• 어떻게 정하느냐의 자유도가 큼
• 8: IF(x,y,z) => x?y:z
• 9: 가장 바람직한 wall following program
• 10: 부모가 될 개체를 고르는 방법 두가지(같은 개체가 여러번 뽑힐 수도 있다)
• tournament
• proportional
• crossover rate: 몇개를 그대로 복사할 것인지 몇개를 부모에서 물려받을 것인지 비율
• crossover: 한 부모의 랜덤한 subtree를 골라 다른 부모의 랜덤한 subtree로 바꾸는것
• 고르는(바꾸는) subtree가 한개면 1-point, 여러개면 n-point
• 적절한 crossover operation은 부모의 fitness를 적절히 물려받게 해서 자식도 fitness가 좋게 나오게 하는것. 물려받아서 fitness가 다 흐트러지면 의미가 없다
• mutation: 부모의 랜덤한 subtree를 골라 “새로운” 랜덤 subtree로 바꾸는 것
• 18: 해당 세대에서 가장 fit한 개체의 fitness를 나타낸 그래프
• 장점: 어떤 문제에서도 응용 가능하다. development cost가 낮다. 결과가 interpretable하다(뉴럴네트워크와 달리)
• 단점: 느리다. optimal이 나온다는 보장이 없음

//중간2 genetic algorithm까지

• knowledge base: database로부터 얻어진 좀 더 high level의 정보(정보의 수준이 더 높음)
• inference engine은 domain independent하게 사용할 수 있다 - 데이터의 종류/얻어야 할 결과에 따라 다르게 만들 필요가 없다. 
• ex) watson(처음에는 퀴즈푸는애로 만들었지만 knowledge base를 바꿔서 암진단하는애로도 이용)
• knowledge base만 바꿔 끼우면 된다
• wumpus world
• 게임의 규칙과 fact(돌아다니면서 얻는 정보)의 조합이 knowledge base
• 추론(logic)이 inference engine (일반적인 과정)
• logic
• syntax: sentence의 validity를 구분하는 것
• semantics: sentence의 meaning을 정의하는 것
• x+2>y는 세살짜리 아이에게는 단순한 symbol 5개의 나열일 뿐임. symbol 각각의 의미를 알려주는것
• 어떤 world가 주어질 때 sentence가 참인지 거짓인지 판단하기 더 쉬움. 따라서 항상 world중심으로 문장을 해석한다
• entailment
• KB⊨α = “KB entails alpha” = “alpha follows from KB”
• KB가 참인 world에서 알파가 반드시 참이다라는 의미
• 이런 관계를 만족하는 알파를 찾는것이 목적임
• inference
• entailment를 계산하는 방법
• KB ⊢i α = i에 의해 알파가 KB에서 계산될 수 있다
• model
• = 참거짓을 판단할 수 있는 formally structured world
• 좁은의미: m에서 알파가 참일 경우 -> m을 알파의 모델이라고 한다
• entailment <-(sound) inference
• entailment ->(complete) inference
• 37: 여러가지 inference rule
• Modus Ponens: A과 B가 있을 때 A->B이면 B를 출력으로 내도 된다는 의미
• resolution은 거의 complete한 rule이다(resolution만 가지고 계산할 수 있는 rule이 아주 많음)
• literal = propositional variable or its negation
• 39: KB와 KB in CNF는 동치임
• *수정*: New KB: [¬P∨Q , ¬Q∨R , ¬Q∨S , ¬P∨R , ¬P∨S] 
• 41: 3번에서 negation을 가장 안쪽의 괄호까지 집어넣음
• KB⊨α이면 KB’는 inconsistent하다 -> KB’가 inconsistent하면 KB⊨α이다
• {P}, {P’}가 함께 있으면 inconsistency를 증명할 수 있다. 둘에 resolution을 적용하면 공집합이기 때문

• 2쪽: 세가지 KB의 양은 똑같다. 왜냐하면 그 안에서 찾을 수 있는 것들만 추가되었기 때문
• 3쪽: modus ponens로 모든 knowledge를 얻어낼 수 없기 때문에 incomplete한 것임. complete하게 하려면
• 다음장에 나오는 것처럼 rule을 resolution으로 바꾸면 됨. 
• 만약 modus ponens를 사용한다면 horn clause를 이용하여 forward chaining을 하면 됨
• horn clause = definite clauses or goal clause
• a^b^c -> d같은 모양
• forward chaining = forward checking
• CSP문제로 생각한다면 변수 -> propositional logic, 변수가 가질 수 있는 값 -> t/f, constraint -> clause
• 기말고사에 CSP와 이걸 관련시켜서 문제가 나올 수 있다
• backward chaining
• q가 참이려면 무엇이 참이어야하는가? p. p가 참이려면? m과 l. 이것을 반복
• forward backward 모두 linear 시간 안에 가능 
• a->b = !a v b
• disjunction을 사용하면 모두 negation이 붙고 하나만 positive인 형태로 나옴
• resolution은 refutation-complete하다. 그냥 complete 하지는 않음
• 38쪽처럼 풀수도 있고 39쪽처럼 구구절절 할수도 있다..39쪽은 bfs하고 있는거임. 4번까지 이용해서 11번까지 구하고, 또 11번까지 이용해서 그 다음을 구하고. 결과적으로 search를 어떻게 하느냐의 문제임
• elimination strategies
• contradiction을 하는 데 도움이 안되는 것을 지움 
• 똑같은 문장들
• 하나의 literal로만 이루어진 것들(p만 있고 not p가 없는 경우 또는 그 반대)
• 늘 참이 되는 문장(positive와 negative가 disjunction되는 경우)
• “{p,q} 이면 {p,q,r}”에서 {p,q,r}이 없어도 됨
• restriction strategies
• 문장의 pair를 고를 때
• Unit Restriction: 둘 중 하나는 literal이 하나여야 함
• unit resolution은 일반적으로 complete 하지 않다. 하지만 빠르기 때문에 사용.
• Input Restriction: 둘 중 하나는 원래의 KB에 있어야 함
• Linear Restriction: 원래의 KB에 있거나 다른 문장의 ancestor
• Set of Support Restriction: 알아서공부하여라
• tell operation, ask operation
• 어떤 알파에 대해 확인 할 때 satisfiability를 알파에 대해 한번, not 알파에 대해 한번 총 두번 확인하면 된다
• 문제 자체가 complex하기 때문에 무슨 알고리즘을 써도 linear하게 할 수 없음
• satisfiability를 확인하는 것은 결국 해당 조건을 만족하는 모델이 있느냐의 문제이기 때문에 model checking이라고도 한다

DPLL

• 54쪽: 어떤 clause가 생기면 그 clause에 관련된 모든 clause를 확인해본다
• empty clause가 나오면 backtrack해야함
• KB의 모든 clause가 assignment를 통해 없어지면 남은 변수는 아무렇게나 assign해도됨
• KB에 하나의 literal만 남으면 1로 assign한다
• 57쪽 *수정*: DPLL(F U { (c) }, assigned) || DPLL(F U { (¬ c) }, assigned); 
• 주석: pure literal/unit clause를 제거하는 부분을 추가해도 된다는 뜻
• 61: horn clause에서 forward/backward chaining 은 linear. any clause는 NP-complete하기 때문에 exponential
• 𝑆(𝑥, y) → ¬𝐶lear(y) 이런건 propositional logic이 아님