[MIT] Data Science - 1. Introduction and Optimization Problems

Introduction to Computational Thinking and Data Science
(6.0002, Fall 2016)

Introduction to Computational Thinking and Data Science

MIT6_0002F16_lec1.pdf

0.74MB

 

핵심 키워드

• 계산 모델(Computation Model)
• 최적화 모델(Optimization Model)
• 탐욕 알고리즘

 

학습 내용

계산 모델(Computation Model)

• 이제까지 일어났던 무언가를 이해하거나 매일 보는 현상들을 설명하는 모델
• 아직 일어나지 않은 미래를 예측할 수 있게 해주는 모델
• 예) 날씨 변화 모델 : 천 년동안 날씨가 어떻게 변했는지에 대한 모델과 미래에 어떻게 될 지
  예측하는 모델을 만들 수 있음

 

최적화 모델(Optimization Model)

• 제한 조건을 가지며 목적 함수를 최대화 또는 최소화하는 모델
• 냅색(배낭) 문제
  • 제한 조건 : 냅색 안에 들어갈 수 있는 양
  • 도둑이 가장 값비싼 물건을 훔쳐야 하는 최적화 문제
  • 연속 냅색 문제
    • 일부분만 가져갈 수 있는 문제(금괴가 아닌 금모래로 가져갈 수 있는 경우)
    • 탐욕 알고리즘으로도 풀 수 있고, 풀기 쉬운 편
  • 0/1 냅색 문제(Binary)
    • 금괴를 가져가거나 아예 못 가져가는 경우
    • 한번 결정하면 그 결정이 다음 결정에 영향을 미침

 

최적화 문제를 푸는 방법

• 무차별 대입(브루트 포스) 알고리즘(Brute force algorithm)
  • 모든 경우의 수를 고려해 승자를 택한 것
  • 그러나 실용적이지 않음
  • 복잡도가 지나치게 커짐
• 탐욕(그리디) 알고리즘(Greedy algorithm)
  
  • While kanpsack not full put "best" available item in kanpsack
  • 여러 경우 중 하나를 결정할 때 그 순간 best라고 생각되는 것을 선택해 나가는 방식
  • 가장 좋은 것(best)의 의미는 정의에 따라 달라짐
  • 시행하기 쉽고 계산이 효율적임
  • 탐욕 알고리즘은 좋은 해를 구할수는 있어도 항상 최적 해를 구할수는 없음

 

파이썬 람다(lambda) 표현식

• 익명(=이름이 없는)의 함수를 만들 때 사용
• (lambda 식별자 배열 : 원하는 식)
• lambda <idf, id2, … idn>: <표현식>
  
  • n개의 인자의 함수를 반환
• 이 파라미터들로 표현된 식을 계산하고 결과를 반환하는 함수를 만듬
• def를 쓰는 대신에 인라인 함수로 정의