[알고리즘] Week 4: 마르코프 체인과 랜덤화 알고리즘

Day 1: 마르코프 체인 (Markov Chain)

• 강의 내용:
  • 마르코프 체인의 개념
    • 마르코프 체인이란 무엇인가?
    • 마르코프 체인의 특성 및 응용 사례
  • 마르코프 체인의 기본 원리
    • 상태 공간 (State Space)
    • 전이 행렬 (Transition Matrix)
  • 마르코프 체인의 시간 복잡도 분석
    • 마르코프 체인의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 간단한 마르코프 체인 구현 및 예제

import numpy as np

# 예제: 마르코프 체인 구현
def markov_chain(trans_matrix, state, steps):
    current_state = state
    states = [current_state]
    for _ in range(steps):
        current_state = np.random.choice(len(trans_matrix), p=trans_matrix[current_state])
        states.append(current_state)
    return states

# 전이 행렬 정의 (Transition Matrix)
trans_matrix = [
    [0.9, 0.075, 0.025],
    [0.15, 0.8, 0.05],
    [0.25, 0.25, 0.5]
]

# 초기 상태 및 단계 수 설정
initial_state = 0
steps = 10

# 마르코프 체인 실행
states = markov_chain(trans_matrix, initial_state, steps)
print("마르코프 체인 상태 변화:", states)

 

Day 2: 마르코프 체인 심화

• 강의 내용:
  • 마르코프 체인의 응용
    • 페이지랭크 알고리즘 (PageRank Algorithm)
    • 숨은 마르코프 모델 (Hidden Markov Model, HMM)
  • 마르코프 체인의 고급 기법
    • 불변 분포 (Stationary Distribution)
    • 마르코프 체인의 수렴 성질
  • 마르코프 체인의 시간 복잡도 분석
    • 고급 기법의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 페이지랭크 알고리즘 구현 및 예제

import numpy as np

# 예제: 페이지랭크 알고리즘 구현
def pagerank(M, num_iterations=100, d=0.85):
    N = M.shape[1]
    v = np.random.rand(N, 1)
    v = v / np.linalg.norm(v, 1)
    M_hat = (d * M + (1 - d) / N)
    for _ in range(num_iterations):
        v = M_hat @ v
    return v

# 링크 행렬 정의 (Link Matrix)
M = np.array([
    [0, 0, 1, 0, 0, 0],
    [1/2, 0, 0, 0, 0, 1],
    [1/2, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 1, 0]
])

# 페이지랭크 계산
pagerank_scores = pagerank(M)
print("페이지랭크 점수:")
print(pagerank_scores)

 

Day 3: 랜덤화 알고리즘 (Randomized Algorithms)

• 강의 내용:
  • 랜덤화 알고리즘의 개념
    • 랜덤화 알고리즘이란 무엇인가?
    • 랜덤화 알고리즘의 특성 및 응용 사례
  • 랜덤화 알고리즘의 기본 원리
    • 무작위화 (Randomization)
    • 기대 시간 (Expected Time) 및 확률적 분석
  • 랜덤화 알고리즘의 시간 복잡도 분석
    • 랜덤화 알고리즘의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 간단한 랜덤화 알고리즘 예제 (랜덤 선택 알고리즘)

import random

# 예제: 랜덤 선택 알고리즘 (Randomized Selection Algorithm)
def randomized_select(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    lows = [el for el in arr if el < pivot]
    highs = [el for el in arr if el > pivot]
    pivots = [el for el in arr if el == pivot]
    if k < len(lows):
        return randomized_select(lows, k)
    elif k < len(lows) + len(pivots):
        return pivots[0]
    else:
        return randomized_select(highs, k - len(lows) - len(pivots))

# 예제 실행
arr = [3, 6, 2, 1, 9, 8, 5, 7, 4]
k = 4
print(f"{k+1}번째 작은 수:", randomized_select(arr, k))  # Output: 5

 

Day 4: 랜덤화 알고리즘 심화

• 강의 내용:
  • 랜덤화 알고리즘의 응용
    • 몬테카를로 알고리즘 (Monte Carlo Algorithm)
    • 라스베가스 알고리즘 (Las Vegas Algorithm)
  • 랜덤화 알고리즘의 고급 기법
    • 샘플링 (Sampling)
    • 부트스트랩 (Bootstrap) 및 재표본 추출 (Resampling)
  • 랜덤화 알고리즘의 시간 복잡도 분석
    • 고급 기법의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 몬테카를로 알고리즘 구현 및 예제

import random

# 예제: 몬테카를로 알고리즘을 사용한 원주율 추정 (Estimating Pi)
def monte_carlo_pi(num_samples):
    inside_circle = 0
    for _ in range(num_samples):
        x, y = random.uniform(-1, 1), random.uniform(-1, 1)
        if x**2 + y**2 <= 1:
            inside_circle += 1
    return (inside_circle / num_samples) * 4

# 예제 실행
num_samples = 10000
estimated_pi = monte_carlo_pi(num_samples)
print("추정된 원주율 값:", estimated_pi)

 

Day 5: 확률 및 통계 알고리즘 종합 연습

• 강의 내용:
  • 종합 연습 문제 풀이
    • 마르코프 체인 및 랜덤화 알고리즘 문제 해결
  • 확률 및 통계 알고리즘의 응용
    • 다양한 실생활 문제에서의 응용 사례
• 실습:
  • 종합 연습 문제 해결 및 결과 분석

### 종합 연습 문제 예시
1. 주어진 전이 행렬을 사용하여 마르코프 체인의 상태 변화를 시뮬레이션하세요.
2. 주어진 웹 그래프에서 페이지랭크 점수를 계산하세요.
3. 주어진 배열에서 k번째 작은 수를 랜덤 선택 알고리즘을 사용하여 찾으세요.
4. 몬테카를로 알고리즘을 사용하여 원주율을 추정하세요.

 

Day 6: 프로젝트 준비

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 주제 및 요구사항 확정
    • 프로젝트 설계 및 계획 수립
  • 프로젝트 구현 준비
    • 데이터 구조 및 알고리즘 설계
    • 프로젝트 팀 구성 및 역할 분담
• 실습:
  • 프로젝트 주제 및 요구사항 분석
  • 프로젝트 설계 및 계획 수립

### 프로젝트 주제 예시
1. 확률 기반 네트워크 분석 도구 개발
2. 실시간 랜덤화 알고리즘 최적화 시스템

### 프로젝트 요구사항 예시
1. 확률 기반 네트워크 분석 도구:
   - 네트워크 데이터셋 입력 및 저장
   - 마르코프 체인 및 페이지랭크 알고리즘을 통한 분석
   - 분석 결과 출력 및 성능 분석

2. 실시간 랜덤화 알고리즘 최적화 시스템:
   - 랜덤화 알고리즘 데이터 입력 및 저장
   - 몬테카를로 알고리즘 및 랜덤 선택 알고리즘 구현
   - 결과 출력 및 성능 분석

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 확률 및 랜덤화 알고리즘 구현 (마르코프 체인, 페이지랭크, 몬테카를로 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 확률 및 통계 알고리즘, 특히 마르코프 체인과 랜덤화 알고리즘의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!