{Programing}/{Paper}8 2회차 : An Efficient Heuristic Procedure for Partitioning Graphs 수학적으로 분할 문제를 표현하기 위해 몇가지 정의를 따를 필요가 있다. 1. 그래프 G는 가중치 w를 가지는 n개의 노드로 구성2. p는 양수3. 행렬 C는 그래프 G에 대한 연결 가중치 행렬이다.4. k는 양의 정수로 그래프 G를 몇개로 나눌것인가를 결정한다. 5. v는 그래프 G의 k-way 분할은 공집합이 아니고, 그래프 G의 쌍으로 분리된 부분집합이다. v들의 합집합은 G이다. 분할을 다음을 만족해야한다. 여기서 |x| 표식은 집합 x의 크기이고 x의 모든 원소의 크기의 합과 같다.분할의 cost는 모든 i,j에 대한 cij의 합이다. 여기서 i와 j는 각각 다른 부분집합이다.cost는 분할에서 모든 외부 cost를 합한것이다. 분할문제에서는 그래프 G의 분할이 허용할만한 최소 cost를 찾는것을.. 2017. 5. 16. 1회차 : An Efficient Heuristic Procedure for Partitioning Grapths 제목 : An Efficient Heuristic Procedure for Partitioning Grapths Abstract : cost를 가진 edge의 edge cut을 cost합이 최소화 하는 방향으로 주어진 크기의 부분집합으로 그래프의 노드 분할에 대한 문제를 고려했다.예로 전자 회로의 보드에 최소연결로 부품을 올리기 위한 문제가 있음.휴리스틱한 방법으로 최적의 분할을 찾기 위해 이 논문을 작성함. Intro :주어진 그래프 G는 cost를 가진 Edge로 이루어져있고, Edge의 cost 합이 최소화되게 잘라서 주어진 최대 크기보다 크지않은 G의 부분집합으로 나누는 문제를 다룸.전자회로의 부품을 카드사이의 연결을 최소화하고 인쇄된 카드에 위치시키는 문제에서 부품이 그래프의 노드이고, 회로 연.. 2017. 5. 16. 1회차 : A load balancing scheme for massively multiplayer online games 제목 : A load balancing scheme for massively multiplayer online games Abstract : 분산 MMOG 서버구조에 대한 내용. 이 구조에서의 서버노드는 플레이어 상태 업데이트로 인한 Overload의 가능성이 존재함. 여기에서의 load는 각 서버 노드에 접속한 플레이어의 숫자에 비례한다.단, 이 논문에서는 동종의 동일스펙 서버노드로 한정하고 진행한다.두가지 주 목표를 가지고 load balancing 구조를 제안함.1. 각 서버 노드의 load에 비례하여 load를 할당하고 서버간 통신 overhead를 줄이는것.2. load를 각 서버 노드의 점유 대역폭으로 간주하는것. 여기에서 4가지 구조의 알고리즘을 제안.ProGReGA가 Overhead 감소에.. 2017. 5. 16. 논문 읽는 방법. 논문은 총 3번에 걸쳐 읽는것이 좋다. 1. 첫번째 읽을때는 대략적인 아이디어 파악.2. 두번째 읽을때는 디테일한 내용을 제외하고 파악.3. 세번째 읽을때는 깊게 이해할것. 1. 1회차때는 1. 5~10분 이내로 끝낼것. 2. 제목과 Abstract, intro를 읽읅것. 3. section과 subsection의 제목만 읽고 스킵. 4. 결론 읽기. 5. reference를 읽으면서 읽었던 논문에 대한 파악. 1회차가 끝나고 다음에 대한 내용을 정리할것. 1. 논문의 카테고리가 어떤것인가? 논문의 타입은?2. 문맥. 다른 논문과의 관계는 어떤가? 문제를 어떤 이론을 통해 분석했는가?3. 단정. 유효한 가정인가?4. 기고, 논문의 중심 기고는 무엇인가.5. 명료. 논문이 잘써졌는가? 2. 2회차때 1. .. 2017. 5. 16. 이전 1 2 다음
