본문 바로가기

분류 전체보기

 (142)
2. Structure of Complex systems 1. Hierarchy of complex systems 우리는 Complex system의 한가지 Model을 정의할 것이다. 계층적 구조로 다음과 같고, 상위 요소는 하위 요소들로 분할가능하다. Hierarchy Example Systems Communication system, Information system, Aerospace system Subsystems Signal Network, Database, Engines Components Signal Receiver, Data display, Data programs, Thrust generator Subcomponents Signal amplifier, Library utilities, Reactive valve, Rocket nozzles P..
1. Introduction 1. Introduction 해당 내용은 Alexander Kossiakoff의 Systems engineering principles and practice - 3th edition을 정리한 것입니다. 앞으로 진행할 프로젝트는 여러가지 시스템이 통합된 형태가 될 것이다. 물론 온갖 나의 망상의 결과물이지만...! 데이터 수집 시스템, 데이터 분석 시스템, 데이터 관리 시스템, 데이터 리포팅 시스템 등등..... 여러가지 시스템와 연계과정들을 생각해보았는데, 이들을 모두 독립적인 시스템으로 만들고, 높은 일반화수준을 갖도록 설계할 예정이다. 목표는 'Too' long-life cycle system 이다. 이를 위해서는 물론, 플랫폼 독립적이며 유지보수성을 매우 높게 고려하면서, 신뢰성을 극대화 시켜야 ..
14. Intractability 1. Introduction 우리는 앞서서 DFA(Deterministic Finite Automata)라는 기계를 배웠다. 이 기계는 매우 강력하여 수많은 계산을 위한 모델이 될 수 있다. DFA는 Tape와 Tape head를 가지는 추상화된 기계인데, Tape는 input을 저장하고, finite symbol들을 가지고 있다. Tape head는 Tape의 input을 하나씩 차례대로 읽어들인다. 그런데, 이보다 더 강력한 기계가 존재하는데 바로 Turing machine이다. Turing machine의 Tape는 input을 저장할 뿐만아니라, output, intermediate result 또한 저장한다. finite symbol들을 가진다. Tape head는 Tape의 input을 차례로..
13. Linear Programming 1. Brewer's problem Brewer's problem은, 맥주공장에서 한정된 자원을 가지고 어떻게 맥주와 에일을 생산해야 최대의 이익을 올릴 수 있는지 결정하는 문제이다. 자원은 이미 한정되어 있고, 맥주와 에일을 1개 생산하는 데는 특정 수치의 자원의 조합을 투입해야 한다. 예를 들어, 자원 X가 480, Y가 160, Z가 1190개가 있다고 해보자. 맥주 A를 만드는데는 X, Y, Z가 각각 5, 4, 35개가 필요하다. 에일 B를 만드는데는 X, Y, Z가 각각 15, 4, 20개가 필요하다. 맥주 A는 개당 13달러의 이윤을, 에일 B는 23달러의 이윤을 남기고, 이윤을 최대화 하고 싶다. 이를 A는 맥주 생산량, B는 에일 생산량 변수로 하여 방정식으로 표현하면 다음과 같다. 최대..
12. Reductions 1. Introduction Reduction이란 다음을 의미한다. If you can use an algorithm that solve Y to help solve X, Problem X reduces to problem Y 즉, 문제 X를 문제 Y를 푸는데 사용한 알고리즘을 활용해 해결할 수 있으면, 문제 Y로 축소된다고 보는 것이다. 우리는 문제 X에 대한 인스턴스를 문제 Y에 대한 인스턴스로 변환(preprocessing)하고, 알고리즘으로 해결한 후, 다시 결과를 변환(postprocessing)시킨다. 따라서 문제 X를 해결하는 총 비용은, 문제 Y를 해결하는 비용 + Reduction 비용이다. 예를 들어, N개의 item에 대한 중간값을 구한다고 해보자. Preprocessing없이, 바로..
11. Data Compression 1. Introduction Date compression을 통해 우리는 정보를 손실없이 유지하면서 저장공간과 데이터 전송시 시간을 줄일 수 있다. 많은 파일들은 redundancy를 가지고 있고, 이를 제거하는 것이 data compression의 핵심이다. Moore's law에 의해 우리는 이전보다 더욱 많은 저장공간과 빠른 속도를 가지게 되었지만, 그만큼 더 많은 데이터들이 생산되고 있다. 따라서, data compression이 여전히 매우 중요하다. 파일 압축, 이미지 압축, 커뮤니케이션 등 여러가지 영역에서 data compression이 응용되고 있다. Data compression과정은, bitstream B를 compress하여 C(B)를 만들고, 다시 expand하여 original ..
10. Regular Expressions 1. Regular Expressions(REs) Resular Expression은 특정한 문자열 집합을 표현한다. 이메일인지 여부, 올바른 전화번호인지 여부 등 입력값이 올바른 형태인지를 검증할 때 쓰인다. 집합의 요소가 무한할 경우 모든 문자열들을 저장해놓고 모든 케이스에 대해 비교를 하는것은 불가능하므로, Regular Expression은 유용하다. Regular Expression을 작성하기 위한 operation 종류는 다음과 같다. operation order example RE matches concatenattion 3 AABAAB AABAAB or 4 AA | BAAB AA, BAAB closure 2 AA*A AA, ABBBBBA parentheses 1 A(A|B)AAB AAAAB..
9. Substring Search 1. Introduction Substring search란 길이 N의 텍스트에서 길이 M인 패턴을 찾는 것이다. 스팸메일을 찾거나, 유저의 입력으로부터 URL이나 RSA키를 찾는 것, 웹 스크레이핑 등 여러가지 문제를 푸는데 응용된다. 2. Brute force Algorithm Brute force는 모든 경우에 수에 대해 하나씩 하나씩 검사하면서 패턴이 존재하는지 찾는 방법이다. 예를 들어, 입력값이 ABACAD이고, CAD인 패턴을 찾고싶다고 해보자. ABA, CAD를 비교한다. 일치하지 않으므로 다음으로 넘어간다. BAC, CAD를 비교한다. 일치하지 않으므로 다음으로 넘어간다. ACA, CAD를 비교한다. 일치하지 않으므로 다음으로 넘어간다. CAD, CAD를 비교한다. 일치하므로 찾은 것이다..

티스토리툴바