수학적 도구 (9) 썸네일형 리스트형 이산 푸리에 변환 (Discrete Fourier Transform) 글을 적는 현재 티스토리 에디터가 어색하게 느껴질 정도로 오랜만에 포스팅을 해 봅니다. 그동안 졸업 준비를 하느라 바빴습니다. 졸업 논문을 적고 심사 발표를 준비하는 일은 여간 힘든 일이 아니더군요. 다행히 예심은 잘 마쳤고, 본심까지 부족한 부분을 잘 보완할 일만 남았습니다. 그 사이 약간의 짬이 나서 글을 적습니다. 이번 포스팅의 주제는 이산 푸리에 변환(discrete Fourier transform, DFT)입니다. 약간 뜬금없게도 이 주제를 공부하게 된 계기는 쇼어의 알고리즘(Shor's algorithm) 때문입니다. 요새 학교에서 세미나 모임을 만들어 양자 컴퓨팅(qunatum computing)을 공부하고 있습니다. 여기서 여러 유명한 결과들을 살펴 보고 있는데, 그 중에서도 가장 유명한 .. 하벨-하키미 알고리즘 (Havel-Hakimi Algorithm) 티스토리 블로그 관리 페이지에는 유입 키워드를 확인할 수 있는 기능이 있습니다. 저는 하루에 몇 번씩 유입 키워드를 살펴보면서 어떤 검색어로 제 블로그에 유입되는지를 확인하고는 합니다. 그러다 최근 'hakimi 방식', 'hakimi의 방법' 등의 키워드로 제 블로그에 방문한 사람이 있다는 사실을 알게 되었습니다. 최근에 제가 작성한 거리의 그래프 실현 가능성에 대한 포스트로 유입된 것이었습니다. 2022.05.15 - [수학적 도구/Graph theory] - 거리의 트리 실현 가능성 (Tree Realizability of Distance) 거리의 트리 실현 가능성 (Tree Realizability of Distance) 오랜만에 포스팅을 합니다. 그동안 연구에 집중하기도 했고, 좀 색다른 주제로.. 거리의 트리 실현 가능성 (Tree Realizability of Distance) 오랜만에 포스팅을 합니다. 그동안 연구에 집중하기도 했고, 좀 색다른 주제로 포스팅을 할 생각도 있었는지라 블로그에 글을 쓰는 것이 늦어졌습니다. 색다른 주제는 바로 양자 컴퓨팅(quantum computing)입니다. 하도 화제인지라 개인적으로도 공부해 보고 싶었습니다. 처음에는 전혀 이해가 되지 않았는데 이 책 저 책 찾아보면서 공부하다 보니 이제는 좀 이해가 되는군요. 언젠가 해당 주제로 포스팅을 해 보도록 하겠습니다. 각설하고, 이번 글의 주제를 고민하게된 배경에 대해서 간략히 설명을 드리겠습니다. 요새 온라인 메트릭 매칭 문제(online metric matching problem)를 (제가 찾아본 바로는) 기존에는 없던 새로운 모델에서 해결해 보는 연구를 진행하고 있습니다. 그런데 일반적인 메.. 파이썬 PuLP 입문 제가 주로 하는 연구가 조합론적 최적화 쪽이다 보니 아무래도 선형 계획법(linear programming, LP)을 풀어야 할 때가 적잖이 있습니다. 그럴 때마다 예전에는 CPLEX나 Gurobi와 같은 프로그램을 C++로 불러서 해결을 했었습니다. 그렇지만 이를 사용하려면 여러 설정을 만져 줘야하는 번거로움이 있었습니다. 또, C++ 자체가 아무래도 오래된 언어다 보니 문자열 처리 등 개인적으로 불편한 부분도 많았죠.(이를 연구실 동료가 들으면 기겁하겠지만요. 하하.) 마지막으로 CPLEX나 Gurobi 모두, 비록 학술용 라이센스를 제공하기는 하지만, 상용 소프트웨어라는 점도 마음에 걸렸습니다. 그러던 와중에 파이썬에서 LP를 해결해 주는 오픈 소스 라이브러리가 있다는 것을 최근 알게 되었습니다. .. NP-완전 이해하기 (NP-Completeness) 지난번에 이어 이번에도 컴퓨터 과학의 최대 난제인 P vs NP에 대해서 좀더 깊게 들어가 보겠습니다. 이전 포스트에서는 P와 NP가 각각 직관적으로 어떤 의미를 갖고 있는지에 대해서 알아 보았는데요. 이를 보다 엄밀히 정의하면 다음과 같습니다. P는 다항 시간(polynomial time)에 결정론적(deterministically)으로 해결 가능한(solvable) 문제들의 집합입니다. 다시 말해, 어떤 결정 문제(decision problem) \(X\)에 대해, 주어지는 입력(input)이 참인지 거짓인지를 다항 시간에 결정론적으로 해결하는 알고리즘이 존재하면 \(X \in \mathrm{P}\)입니다. NP는 다항 시간에 비결정론적(nondeterministically)으로 해결 가능한 문제들의.. P vs NP 쉽게 이해하기 컴퓨터 과학에는 유명한 난제가 있습니다. 바로 P vs NP입니다. 컴퓨터 과학을 공부하다 보면 언젠간 한 번은 반드시 접하게 되는 흥미롭고도 신기한 문제인데요. 이번 포스트에서는 이에 대해서 함께 알아보도록 하겠습니다. 저는 P vs NP 문제를 대학생 시절 알고리즘 수업을 들을 때 처음 접하였습니다. 솔직히 말씀드리면, 당시에는 진짜 하나도 이해를 못했다고 해도 과언이 아니었습니다. P, NP 내용이 기말고사 범위였는데, 시험 볼 때는 교과서나 강의 자료의 내용을 그저 달달 외워서 베껴 적었던 기억이 나네요. 그 후 대학원 준비를 할 때 P와 NP에 대해서 좀더 알게 되었고, 진학 후에야 그것들을 제대로 이해하는 수준에 이르렀습니다. 그만큼 어렵게 배운 개념이었는데요. 막상 제대로 이해를 한 후에는 .. Maximal & Maximum 이번 시간에는 maximal과 maximum에 대해서 각각이 어떤 의미를 갖는지 정리해 보도록 하겠습니다. 두 단어는 매우 비슷하게 생겼지만 그 의미는 많이 다른데요, 어떻게 다른 것인지 예시를 통해 짚어 보도록 하죠. 본문에는 크거나 많은 것이 척도인 maximal과 maximum에 대해서만 적을 예정이나, 작거나 적은 것이 척도인 minimal과 minimum도 비슷하게 적용할 수 있습니다. 저는 현재 대학원생이며, 학부 자료구조 과목과 알고리즘 과목의 조교를 맡고 있습니다. 평소에는 과제를 채점하는 것이 주된 조교 일이지만, 시험 기간에는 시험을 감독하는 것도 제가 해야하는 일 중 하나입니다. 학기마다 시험을 치는 장소가 달라지기도 하지만 대개 저희가 배정 받는 장소는 다음 그림과 같이 아홉 석의 .. 그래프 트리에 관한 간단한 성질들 요즘 트리(tree, connected acyclic graph)에 관한 문제를 고민하고 있는데, 오늘 그에 관한 간단하지만 흥미로운 성질들을 알게 되어 정리합니다. 너무 간단해서 학부 수준의 조합론에서 분명 다루었을 내용으로 보입니다만, 저는 전공이 컴퓨터과학이니까요. 채워야할 것들이 아직도 너무 많은 것 같습니다. 차수열(degree sequence)에 관한 필요충분조건 첫 번째는 tree의 degree sequence에 관한 내용입니다. 먼저 degree sequence가 무엇이냐면, 그냥 정점의 차수를 내림차순으로 나열한 것입니다. Degree sequence는 그래프의 모양을 가늠할 수 있는 좋은 도구입니다. 다만, 하나의 degree sequence가 유일한 그래프를 결정하는 것은 아닌데요. .. [선형 계획법] 쌍대성(Duality) Linear programming은 최적화 분야에서 잘 알려지고 연구되었으며 실제로도 많이 응용되는 기법입니다. 줄여서 LP라고도 하며, 우리말로는 선형계획법으로 불립니다. 이름이 뭔가 멋들어져서 괜스레 어렵게 느껴질 수도 있겠습니다만, 사실 별것 아닙니다. 고등학교 수학 시간에 다음과 같은 문제를 풀어보신 적이 있을 겁니다. 여러분은 빵집 사장님입니다. 식빵과 크루아상, 두 종류의 빵을 팔고 있습니다. 식빵 1kg을 만들기 위해서는 밀가루 5kg, 설탕 3kg이 필요하고 크루아상 1kg을 만들기 위해서는 밀가루 2kg, 설탕 5kg이 필요하다고 합시다. 1kg 당 식빵과 크루아상의 가격은 같습니다. (저는 제빵을 잘 모릅니다. 수치는 그저 예시일 뿐입니다.) 하루에 밀가루 20kg, 설탕 15kg이 들.. 이전 1 다음
