전체 글
-
그래프 알고리즘알고리즘 2021. 5. 31. 19:46
최소 신장 트리 (MST : Minimum Spanning Trees) 비방향 연결 그래프를 대상으로 한다. --> 연결 그래프 : 모든 정점 간의 경로가 존재하는 그래프이다 그래프의 신장 트리(spanning tree) 그래프의 정점 집합인 V와 간선 집합의 개수는 |V| - 1 개 이다. 싸이클이 없어야 한다. 그래프의 최소 신장 트리 활용 어떻게 하면 도로를 최소한으로 만들수 있는가? 최소 신장 트리 문제를 푸는 탐욕적 알고리즘 탐욕적 기준에 따라 싸이클이 생기지 않도록 연결 그래프가 되도록 간선 추가 최소 거리를 만족하는 최소 신장 트리는 유일하지 않을 수 있다. 크루스칼 알고리즘 탐욕적으로 간선을 추가하는 방식 저밀도 그래프에서 유용하다 프림 알고리즘 탐욕적으로 정점을 추가하는 방식 고밀도 그래..
-
1차 논리인공지능 2021. 5. 29. 11:00
표현의 재고찰 명제 논리는 의미론이 문장들과 가능한 세게들 사이의 진리 관계에 기초하므로 선언적 언어이다. 하지만 명제 논리는 객체들이 많은 환경에서 간결하게 서술할 수 있는 표현력이 부족하다. 사고의 언어 자연어(natural language) 의사소통의 매개체로 작용한다. 중의성(ambiguity) 문제를 격는다. 언어는 명사의 성(gender)처럼 자의적으로 보이는 문법적 성질을 통해서도 사람의 사고에 영향을 준다. 형식 논리의 관점에서는 같은 지식을 서로 다른 두가지 방식으로 표현해도 아무런 차이가 없다. 하지만 제한된 자원을 가진 프로그램이 한 표현에서 결론에 도달할 수 있지만, 다른 표현에서는 결론에 도달 할 수 없다. 형식 언어와 자연어의 장점만 채용한 시스템 명제 논리의 장점을 기반으로 삼..
-
Multicast Routing인터넷 프로트콜 2021. 5. 24. 16:41
Unicasting, Multicasting, Broadcasting Unicasting one to one 한 사람만을 상대한다. Multicasting one to many 여러명을 상대한다. Broadcasting 모두를 대상으로 보낸다 Multicasting 대 Multiple unicasting Multicasting 근원지에서 출발하는 하나의 패킷에서 시작해서 라우터에서 복사된다. Multiple unicasting 보낸 고자 하는 대상의 수 만큼 패킷의 복사본이 만드어진다. Multicasting Address 주소지정에 224.0.0.0/4로 제안되어 있다. Multicast IP : x.y.z.w (32 bit) Multicast MAC : ~~~.y^.z.w (48 bit) 범위는 01..
-
네트워크 장비와 가상 LAN인터넷 프로트콜 2021. 5. 19. 16:36
네트워크 장비 HUB 1계층의 동작하는 장비 더미허브 보통 허브의 일을 한다. 스위치허브 가정에 있는 가정용 공유기 허브에 연결된 모든 포트를 통해서 다 보내서 브로드캐스트를 보낸다. 많이 연결되어 있으면, 전송 속도가 떨어진다 switch(Link-layer switch) 2계층에서 동작하는 장비 각 호스트를 포트의 번호와 MAC 주소로 유지한다. Learning switch 루프 문제 A -> D에게 프레임을 보낸다 하지만 b - c 단계를 반복할 뿐이다. 왜냐하면 주소는 알고있지만, Port 번호가 다르기 때문에 도착되지 않고 반복된다. 스패닝 트리 알고리즘 루프 문제 해결 최단 경로를 통해 길목에 표시를 해준다. Router 3계층에서 동작하는 장비 IP 주소를 이용한다. 가상 LAN Group1..
-
그래프(Graph)알고리즘 2021. 5. 17. 16:52
Graph G = (V , E) G : 그래프 V : 정점(vertex)의 집합 E : 정점들을 잇는 간선(Edge)의 집합 Graph의 종류 간선의 뱡향성 유무 비방향(undirected) 그래프 == 양뱡향 방향(directed) 그래프 간선의 가중치(숫자) 유무 가중치(weighted) 그래프 비가중치 그래프 Graph 용어 경로(path) - 어떤 정점에서 다음 정점을 잇는 이음선(간선)이 존재하는 일련의 정점 - 단순 경로(simple path) : 같은 정점을 두 번 거치지 않는 경로 - 경로의 길이 : 경로상의 간선의 수 싸이클(cycle) - 어떤 정점에서 그 정점 자신으로 가는 경로 - 싸이클 존재 유무 : cyclic 그래프 vs acyclic(싸이클이 하나도 없어야 한다.) 그래프 -..
-
논리적 에이전트인공지능 2021. 5. 13. 11:39
새 표현들을 이용해서 다음에 할 일을 연역할 수 있는 에이전트를 설계할 수 있다. 내부 표현(representation)들에 작용하는 추론(reasoning) 공정들로 달성된다. 인공지능에서는 지식기반 에이전트(knowledge-based?agent)가 지능에 대한 이러한 접근 방식을 내포한다. 지식 기반 에이전트 knowledge base은 지식 기반 에이전트의 핵심 구성요소이다. 새 문장을 추가하는 방법과 지식 기지에 있는 문장을 질의하는 방법이 필요하다. 이런 연산에는 Tell와 Ask이 있다. 두 연산은 Inference(추리), 기존 문장에서 새 문장을 이끌어 내는 공정이 관여할 수 있다. Inference는 누군가 Ask연산으로 지식 기지에 문가를 질의했을 때 그 답이 반드시 이전에 지식 기지..
-
탐욕적 알고리즘알고리즘 2021. 5. 10. 17:34
탐욕적 기법 탐욕적 알고리즘 에서 시작, 탐욕적인 기준에 따라 아이템을 차례로 추가하여 문제의 해답이 될 까지 계속하는 기법 단계 선택 과정 기준에 따라 현제 상태(Locally)에 최적의 선택 적정성 검정 해답 점검 -> 동적 보다 쉽다. 해답이 항상 최적해를 보장하지 않는다. 그래서 증명이 필요하다. 반드시 연속 배낭문제 각 아이템을 잘라서 배낭에 넣을 수 있다. 용량을 초과하지않고 아이템 가치의 합이 최대가 되도록 담기 정렬로도 풀 수 있다. 탐욕적 알고리즘과 우선순위 큐 탐욕적 알고리즘 구현은 우선 큐를 동반한다. 큐 (Queue) Queue는 리스트라고 하는 선형 구조 만족하는 조건 FIFO(선입선출) 들어온것 : 입력 나가는것 : 삭제 Queue에서 중요한 것 입력 순서가 중요하다. 우선순위 ..
-
유니캐스트 라우팅인터넷 프로트콜 2021. 5. 10. 17:10
Routing(경로 배정) 개념 : 최소의 비용으로 최적의 경로를 제공 Unicast Rounting: One - to - One(ch.20) Mulicast Routing: One - to - Many(group) --> SNS, Game 등 거리-방향(Distance-Vector) : Router의 숫자가 적은 방향 --> DV 방식(RIP : Routing Information Protocol) 링크 상태(Link State : LS) : 링크의 상태(지연, 분실, 성능 등)을 고려한다. LS 방식(OSPF : Open Shortest Path First) 경로-방향(Path-Vector) : 목적지까지 도달하는 경로를 고려(Full Path) PV방식(BGP : Boarder Gateway Pro..