-
양자 컴퓨팅 - Surface Code
최근 양자 컴퓨팅의 error detection 및 correction에 사용되는 surface code의 기초를 잘 설명한 논문인 Surface codes: Towards practical large-scale quantum computation을 접했습니다. 이 포스트를 통해 양자 컴퓨팅에서 어떻게 error detection을 진행하고, surface code가 어떤 개념인지 설명하고자 합니다. 배경 지식 Shor’s Algorithm이나 Grover’s Algorithm 등의 양자 알고리즘이 개발되며 양자 컴퓨팅에 대한 관심이 커졌습니다. 2020년 현재 IBM Q Experience나 Amazon Braket, Microsoft QDK 등으로 양자 컴퓨팅 프로그래밍 언어를 사용할 수도 있습니다. 그러나 이런 시스템이 물리적인 양자 체계와...
-
P VS NP Question
P vs NP Question Contents 들어가며 P NP 란? 여러가지 NP문제들 PSPACE 와 NSPACE P = NP? 참고 들어가며 예전에 비해 프로그래밍이 좀 더 보편적인 분야로 자리잡으면서, 남녀노소 할 것 없이 많은 사람들이 프로그래밍을 접하고 있다. 또한 문제풀이로 알려진 Problem Solving 쪽을 많은 기업체 또는 학교에서 평가의 기준또는 test로 삼고 있다. 이러한 PS는 여러가지 분야가 있지만, 대부분이 주어진 제한적인 상황안에서 문제를 해결하게 된다. 보통 PS공부를 하기 위해서 알고리즘 공부가 필수라고 얘기한다. 그렇다면 알고리즘이란 무엇일까? 알고리즘을...
-
블루투스의 취약점들
1. Introduction 블루투스는 수많은 기기들이 근거리 통신을 위해 사용하는 프로토콜입니다. 컴퓨터와 연관이 있는 키보드, 마우스, 스피커 등의 입출력장치는 물론이고 심장박동수 측정 기기와 같은 의료기기들도 무선으로 정보를 송/수신해야할 필요가 있을 경우 블루투스를 사용합니다. 블루투스 통신에서 오가는 정보는 반드시 기밀이 유지되어야 하고 송/수신자가 아닌 외부의 공격자가 내용을 감청하거나 변조하는 일이 없어야 합니다. 그렇기 때문에 블루투스의 통신 규약을 보면 내용은 암호화가 되고 다양한 공격들에 대한 대비책을 미리 마련해두고 있습니다. 그러나 현존하는 모든 시스템이 그러하듯 블루투스 프로토콜도 다양한 취약점이...
-
Error-bounded Piecewise Linear Representation
안녕하세요? 오늘은 주어진 데이터를 여러 개의 선형 방정식으로 근사하되, 모든 점들마다 최대 오차가 $\delta$ 이하로 bound되도록 하는 Error-bounded Piecewise Linear Representation를 구하는 방법에 대해 알아보겠습니다. 이 글의 내용은 2014년 발표된 논문인 Maximum error-bounded Piecewise Linear Representation for online stream approximation을 참고하였습니다. PLR이란? Piecewise Linear Representation(PLR)은 주어진 데이터를 구간마다 여러 개의 선형 방정식으로 근사하는 방법입니다. PLR을 사용하면 얻을 수 있는 이점은 데이터의 절약입니다. 위 Fig 1는 총 11개의 데이터를 포함하고 있지만, 해당 데이터를 3개의 선으로 근사한다면...
-
동적 계획법 모델화하기
서론 세상에는 수없이 많은 알고리즘 문제가 있습니다. 그러나 새로운 문제를 볼 때마다 항상 지금껏 보지 못한 새로운 기법을 사용해야 하는 것은 아닙니다. 문제의 특성을 파악하고, 조건들을 이용하여 자신이 아는 문제로 변환한 뒤, 이전에 다른 문제를 풀 때 사용했던 기법을 비슷하게 적용하여 풀 수 있기도 합니다. 이처럼 많은 문제는 몇 가지 정해진 전형적인 형태로 모델화 되는 경우가 많습니다. 반면에 큰 알고리즘 분류 중에 많은 사람들이 처음 접할 때 큰 벽을 느끼는 분야가 있습니다. 바로 동적 계획법(dynamic...