Definition of Seon

학습목표 1. 그래프 정의하기 2. 그래프 그리는 방법 연습하기 3. 그래프 클래스 구분하기 Warm-up 문제) 과리니의 퍼즐 : 흰색/검은색 체스 나이트의 위치 바꾸기 문제) 한붓그리기 - 쾨니히스베르크 다리 한 번 씩만 건너기 해설) 오일러의 길 : 시작점과 끝점 가운데 있는 지점들을 빼고 모든 지점이 짝수여야 함 그래프 ex. 항공 그래프, 페이스북 그래프, 인용 그래프, 링크드 오픈 데이터, 생물학, 생화학 분야 등 -> 네비게이션(두 지점 사이의 최단 거리 찾는 알고리즘) -> 구글 검색(PageRank 페이지에 점수와 순위를 부여해 관련 링크만 보도록 함) -> 게임, 게놈, GSM, 컴퓨터 칩 An isolated vertex forms a component 분리된 꼭짓점이 구성요소를 형성..

코세라에서 받은 두번째 수료증! 조합론과 확률은 앞서 공부한 수학적사고보다 훨씬 어려웠다. 고등학생 때 배운 내용들을 다시 복습하기 위해 수학의 정석을 꺼냈다. 고등학생 때 배우지 않은 내용들을 새로 학습하느라 애먹었다. 이제 다음 강의는 3개 남았다. 하나하나 완료할 때마다 뿌듯한 느낌이 든다. 앞으로 남은 강의를 모두 이수하면 알고리즘의 기초는 쌓을 수 있는 걸까? 혹시 내 공부의 방향이 잘못된 것은 아닐까 두려운 마음도 있지만 언젠가 개발자가 되었을 때 컴퓨터공학과 전공생처럼 이산수학을 공부했다는 기록이 있는, 그런 지식이 있는 개발자가 되었으면 좋겠다.

학습 목표 - 선형성을 이용하여 기댓값을 계산하기 - 기댓값을 이용하여 확률을 추측하기 - 확률 실험에서의 확률 변수 구별하기 - 확률 변수의 기댓값 계산하기 확률 변수와 기댓값 확률 변수 : 무작위 실험의 수치적 특성을 연구하기 위한 수학적 모델 평균 from statistics import mean print(mean([1, 2, 3, 4, 5, 6])) print(mean([7, 7, 7])) print(mean([9.5, 10.5])) 평균은 최댓값보다 작거나 같고 최솟값보다 크거나 같다. 기댓값 기댓값의 선형성 마르코프 부등식 coursera Introduction to Discrete Mathematics for Computer Science 과정 중 Combinatorics and Proba..

학습목표 주어진 확률에 대한 확률 공간 제안하기 등확률적인 결과를 가지고 단순한 경우에 확률 계산하기 확률적 모델이 실제 상황에 적합한지 판단하기 단순 예제에서 조건부 확률 값 찾기 확률론 동전 던지기는 예측할 수가 없고 반복적으로 실험했을 때 0과 1이 같은 빈도로 나옴 갈톤보드(이항분포 실험기) : 가운데로 구슬을 넣었을 때 왼쪽 오른쪽 중 한 군데로 감 Z=(X+Y)/2 -> 가운데에 더 많은 구슬이 떨어짐 순수과학에서는 모델에 의해 실제 동전을 대상으로 하지만 수학에서는 모델의 결과이다. 확률공간 : 모든 결과 이벤트 : 몇 개의 결과(유리한) 동일하지 않은 결과 실제 보다 더 많은 시도를 해서 나온 것이 동일한 결과이다 전체 확률을 더하면 1이 되어야 한다. 두 상자에 흰 공 검은 공 각 15개..

학습목표 - 문제를 계산할 때 표준 조합 세팅 사용하기 - 카운팅 문제를 표준 조합 세팅으로 분류하기 - 표준 조합 세팅을 통한 개체 수 세기 - 여러 조합 세팅을 결합해 계산 문제 해결하기 복습 () parentheses(소괄호) 순서 있는 집합{} braces(중괄호) 순서 없는 집합튜플 : 순서 있는 선택, 중복 가능 from itertools import product for t in product('abc', repeat=2): print(*t, sep='', end=' ') 순열 permutation : 순서 있는 선택, 중복 불가능 n!/(n-k)! from itertools import permutations for t in permutations('abc', 2): print(*t, se..

Combination 조합 토너먼트 : 5개의 팀이 있을 경우 각 팀은 4번의 경기를 치룬다. 즉 5*4번의 경기를 치룬다. 겹치는 경우를 제외해준다. n(n-1)/2 게임의 종류 1. 첫번째 팀 포함 게임수 n-1 / 2. 첫 번째 팀 빼고 T(n) -> T(n)=(n-1)+T(n-1)=(n-1)+(n-2)+....+2+1+0 from itertools import combinations for c in combinations("abcdefgh", 2): print("".join(c)) 집합 S에 대하여 k-조합은 k크기의 S의 부분 집합이다. 파스칼의 삼각형 C=dict() for n in range(8) C[n, 0]=1 C[n, n]=1 for k in range(1,n: C[n, k]=C[n-1..

Basic Counting 기본적인 조합법을 사용하여 개체 수 계산하기 기본 조합 설정에서 개체 수 계산하기 카운팅 문제를 기본 조합 설정으로 분류하기 개체 집합에 표준 작업 적용하기 덧셈규칙 : 첫 번째 유형의 개체가 n개이고 두 번째 유형의 개체가 k개라면 두 가지 유형의 개체가 n+k개이다. 주의점 : 두 유형에 겹치는 부분이 없어야 함 집합론 어떤 원소도 공유하지 않을 때 disjoint 분리집합 합집합과 교집합 집합의 덧셈규칙 : 두 개의 서로소 집합의 결합의 크기는 서로소 집합의 크기의 합과 같습니다 곱셈규칙 from itertools import product for p in product(['a', 'b', 'c'], ['x', 'y']): print("".join(p)) 튜플과 소괄호 튜..

처음으로 받은 수료증! 뿌듯하다. 이 강의를 들으며 어떻게 수학과 컴퓨터를 연결해야 하나 공부할 수 있었다. 단순히 원서로만 공부할 때와 달리 대화형으로 진행되는 커리큘럼에 만족했다. 퀴즈를 풀고 그 퀴즈가 맞았는지 확인하는 과정을 통해 수학에 대한 흥미가 생겼다. 이제 다음은 조합론과 확률이다. 이산수학을 꼼꼼하게 공부해서 컴퓨터과학의 기초를 쌓아야지.

Summary. Invariants are important tools for proving impossibility, termination, and various bounds. 불변량은 불가능성, 종료 등의 문제를 해결하는데 중요한 도구이다. Invariants may take many forms: numbers, "parity", equations, inequalities. 불변량은 숫자, 패리티, 등호, 부등호 등 다양한 형태일 수 있다. To prove impossibility, one finds a quantity that never changes during a process. 불가능성을 증명하기 위해 과정 동안 바뀌지 않는 양을 찾는다. To prove that a process termin..

예, 반례 논리 명제를 참임을 증명하기 위해 하나의 예만 있으면 되는 경우 ex. 흰 사자가 존재한다. 명제가 거짓임을 증명하기 위해 하나의 반례만 있으면 되는 경우 ex. 어떤 사자도 초록색이 아니다. 오일러의 거듭제곱의 합 추측 n>2인 정수에 대하여 논리 연산자 negation 부정 conjunction 그리고(and) disjunction 또는(or) implication 만약 그렇다면(if...then) 드모르간의 법칙 정리 하나의 예는 존재명제를 증명하기에 충분하다. 하나의 반례는 한정명제를 반증하기에 충분하다. Negation, AND, OR, and Implication (If-Then) 는 기본적인 논리연산자다. AND의 부정은 OR 이다. OR의 부정은 AND다. 존재명제의 부정은 한정..