月牙天冲 | 个人博客

发表于 更新于 分类于 阅读次数： 本文字数： 260 阅读时长 ≈ 1 分钟

动态集合上的操作： - SEARCH(S, k)：查询， - INSERT(S, x)：插入 - DELETE(S, x)：删除 - MINMUM(S)：查询最小元素的指针 - MAXMUM(S)：查询最大元素的指针 - PREDECESSOR(S, x)：查询x前一个元素的指针

栈和队列

  • 栈：假设用\(S[1,2,3,...n]\)表示一个可容纳n个元素的栈

    • 先进后出（FILO）

    • 插入操作称作：PUSH, 删除操作称作POP

      def STRACK_EMPTY(S):
          if S.top == 0:
              return True
          else:
              return False
          
      def PUSH(S, x):
          if S.top == n:
              raise "栈上溢（overflow）"
          S.top++
          S[S.top] = x

      def POP(S):
          if STRACK_EMPTY(S):
              raise "栈下溢(underflow)"
          else:
          	S.top--
          return S[S.top+1]

  • 队列：

    • 先进先出（FIFO）

    • 插入操作称作：ENQUEUE，删除称作：DEQUEUE

      def ENQUEUE(Q, x):
          Q[Q.tail] = x
          if Q.tail == Q.length:
              Q.tail = 1
          else:
              Q.tail++
              
       def DEQUEUE(Q):
          x = Q[Q.head]
          if Q.head == Q.length:
              Q.head = 1
          else:
              Q.head++
          return x

链表

与数组不同的是，链表的顺序是由各个对象里的指针决定的。

# 搜索

def LIST_SEARCH(L, k):
    x = L.head
    while x != None && x.key != k:
        x = x.next
    return x

指针和对象的实现

有根树的表示

练习

思考题

发表于 更新于 分类于 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 12 分钟

图的表示

图\(G=(V, E)\)，其中\(V\)表示结点，\(E\)表示边

  • 邻接链表： 表示稀疏图时，非常紧凑

    稀疏图：边的条数（\(|E|\)）远远小于边的结点数（\(|V|\)）的图

    • 需要空间\(\Theta(E+V)\)
    • 邻接表表示由一个包含\(|V|\)条链表的数组\(Adj\)所构成，对于结点\(u\in V\)，\(Adj[u]\)表示图\(G\)中所有与\(u\)邻接的结点

  • 邻接矩阵：能快速查询两个结点之间是否有相连

    矩阵的行号表示起始点，列号表示终点

    • 需要空间\(\Theta(V^2)\)
    • 无向图的矩阵式一个对称矩阵，因为边\((u, v)\)和边\((v, u)\)是一样的
阅读全文 »

发表于 更新于 分类于 阅读次数： 本文字数： 967 阅读时长 ≈ 4 分钟

单源最短路径

环路

前驱结点

前驱子图

松弛操作

松弛（relaxation）技术：对于每个结点\(v\)来说，我们维持一个属性\(v.d\)，用来记录从源结点\(s\)到结点\(v\)的最短路径权重的上界。我们称\(v.d\)为s到\(v\)的最短路径估计

最短路径估计和前驱结点进行初始化:

INITIALIZE-SINGLE-SOURCE(G, s):
	for each vertex v in G.V
		v.d = infty 
		v.pi = NIL 
	s.d = 0

对一条边（\(u\), \(v\)）的松弛过程:

  • 测试是否可以对\(s\)到\(v\)的最短距离进行改善
    • 将\(s\)到\(u\)的最短路径，加上结点\(u\)到\(v\)的权重,与当前\(s\)到\(v\)的最短距离进行比较
    • 如果前者更小，则更新\(v.d\)和\(v.\pi\)
RELAX(u, v, w):
	if v.d > u.d + w(u, v):
		v.d = u.d + w(u, v)
		v.pi = u

其中 w(u, v)表示：点u到点v的权重 v.d: 表示从源s到v的最短距离 v.pi: 表示v的上一个节点

松弛操作和最短路径的性质

  • 三角不等式性质
  • 上界性质
  • 非路径性质
  • 收敛性质
  • 路径松弛性质
  • 前驱子图性质

Bellman-Ford算法

边的权重可以为负值

给定带权重的有向图\(G=(V, E)\)和权重函数\(w: E\rightarrow R\)

算法返回一个布尔值

  • 如果存在权重为负值的环路，返回false（负值的环路，不停的循环，可以使总权重一直降低）
  • 反之，给出最短路径和他们的权重
BELLMAN-FORD(G, w, s):
	INITIALIZE-SINGLE-SOURCE(G, s)
	for i=1 to |G.V| - 1
		for each edge(u, v) in G.E
			RELAX(u, v)
	for each edge(u, v) in G.E
		if u.d > v.d + w(u, v):
			return False
	return True

有向无环图中的单源最短路径问题

Dijkstra算法

差分约束和最短路径

最短路径的证明

练习

24.1-1

在图24-4中运行Bellman-Ford算法,使用结点\(z\)作为源结点。在每一遍松弛过程中以图中相同的次序对每条边进行松弛，给出每遍松弛操作后的\(d\)值和\(\pi\)值。然后，把边\((z, x)\)的权重改为4， 再次运行该算法，这次使用\(s\)作为结点。

使用\(z\)作为源节点：

\(d\)的值:

松弛次数 \(s\) \(t\) \(x\) \(y\) \(z\)
0 \(\infty\) \(\infty\) \(\infty\) \(\infty\) 0
1 2 \(\infty\) 7 \(\infty\) 0
2 2 5 7 9 0
3 2 5 6 9 0
4 2 4 6 9 0

\(\pi\)的值：

\(s\) \(t\) \(x\) \(y\) \(z\)
NIL NIL NIL NIL NIL
\(z\) NIL \(x\) NIL NIL
\(z\) \(x\) \(x\) \(s\) NIL
\(z\) \(x\) \(y\) \(s\) NIL
\(z\) \(x\) \(y\) \(s\) NIL

修改权重之后

24.1-2

证明推论24.3

证明:

24.1-3

给定\(G=(V, E)\)是一个带权重且没有权重为负值的环路的有向图，对于所有结点\(v\in V\)，从源结点\(s\)到结点\(v\)之间的最短路径中，包含边的条数的最大值为\(m\)。（这里，判断最短路径的根据是权重，不是边的条数。）请对算法BELLMAN-FORD进行简单修改，可以让其在\(m+1\)遍松弛操作之后种植，即使\(m\)不是事先知道的一个值。

24.1-4

修改BELLMAN-FORD算法，使其对于所有结点v来说，如果从源节点\(s\)到结点\(v\)的一条路径上存在权重为负值的环路，则将\(v.d\)的值设置为\(-\infty\)

24.1-5

设\(G=(V, E)\)为一个带权重的有向图，其权重函数为\(w: E \rightarrow R\)。请给出一个时间复杂度为\(O(VE)\)的算法，对于每个结点\(v \in V\)，计算出数值$^*(v) = {(u, v)} $

24.1-6

假定\(G=(V, E)\)为一个带权重的有向图，并且图中存在一个权重为负值的环路。给出与i个有限的算法来列出所有该环路上的结点。请证明算法的正确性。

思考题

发表于 更新于 分类于 阅读次数： 本文字数： 406 阅读时长 ≈ 1 分钟

算法导论

发表于 更新于 分类于 阅读次数： 本文字数： 400 阅读时长 ≈ 1 分钟

题目

创建10个goroutine,id分别是0,1,2,3...9

每个goroutine只能打印最后一位是自己id号的数字， 例如: 3号只能打印3, 13, 23, 33...

编写一个程序，依次打印1-10000

第一想法是全局锁，如果只用一个锁，那就是10个goroutine一起抢锁，10个协程加10个锁的话,还要交替解锁。所以选择用channel，goroutine交替向下个管道发送消息。

读取空的channel会根据channel类型返回空的数据，所以需要判断channel读取是否成功，i, ok <- c,判断ok的值

我的解答

解析题目，10个goroutine，但是需要依次打印1-10000，

import (
	"fmt"
	"time"
)


var IsRunning = true

func print(gid int, m map[int]chan int) {
	curChan := m[gid]
	nextChan := m[(gid+1)%10]
	for IsRunning {
		select {
		case i, ok := <-curChan:
			if ok {
				fmt.Println(fmt.Sprintf("%d   goroutine id=%d", i, gid))
				i++
				if i > 10000 {
					IsRunning = false
				} else {
					nextChan <- i
				}
			}
		}
	}

}

func printInOrder() {

	memo := map[int]chan int{}
	for i := 0; i < 10; i++ {
		c := make(chan int, 1)
		memo[i] = c
	}
	fmt.Printf("%#+v\n", memo)

	for i := 0; i < 10; i++ {
		go print(i, memo)
	}
	firstChan := memo[0]
	firstChan <- 0
	for IsRunning {
		// time.Sleep(time.Millisecond)
	}
	defer func() {
		for k, c := range memo {
			fmt.Printf("关闭: %d\n", k)
			close(c)
		}
	}()
}

func main() {
	start := time.Now()
	printInOrder()
	fmt.Printf("用时: %s", time.Since(start))
}
# 输出:
9976   goroutine id=6
9977   goroutine id=7
9978   goroutine id=8
9979   goroutine id=9
9980   goroutine id=0
9981   goroutine id=1
9982   goroutine id=2
9983   goroutine id=3
9984   goroutine id=4
9985   goroutine id=5
9986   goroutine id=6
9987   goroutine id=7
9988   goroutine id=8
9989   goroutine id=9
9990   goroutine id=0
9991   goroutine id=1
9992   goroutine id=2
9993   goroutine id=3
9994   goroutine id=4
9995   goroutine id=5
9996   goroutine id=6
9997   goroutine id=7
9998   goroutine id=8
9999   goroutine id=9
10000   goroutine id=0
用时: 392.8411ms

发表于 更新于 分类于 阅读次数： 本文字数： 193 阅读时长 ≈ 1 分钟

仅凭IP无法完成通信

DNS（Domain Name System）

IP地址不便记忆

DNS的产生

域名的构成

DNS查询

DNS如同互联网中的分布式数据库

ARP(Address Resolution Protocol)

ARP是一种解决地址问题的协议。以目标IP地址为线索，用来定位下一个应该接受数据分包的网络设备对应的MAC地址。

不能用于IPv6

ICMP

DHCP（Dynamic Host Configuration Protocol）

自动设置IP地址、同一管理IP地址分配。

NAT（Network Address Translator）

是用于在本地网络中使用私有地址，在连接互联网时转而使用全局IP地址的技术

IP隧道

其他IP相关技术

发表于 更新于 分类于 阅读次数： 本文字数： 39 阅读时长 ≈ 1 分钟

IP即网际协议

IP基础知识

IP地址的基础知识

路由控制

IP分割处理与再构成

IPv6

IPv4首部

IPv6首部

发表于 更新于 分类于 阅读次数： 本文字数： 926 阅读时长 ≈ 3 分钟

数据链路的作用

数据链路可以视为网络传输的最小单位

将信号与二进制0、1的转换是物理层的责任

数据链路层处理的数据也不是单纯的0、1的序列，该层把他们集合为一个叫做“帧”的块，再进行传输

数据链路相关技术:

  • MAC寻址（物理寻址）
  • 介质共享
  • 非公有网络
  • 分组交换
  • 环路检测
  • VLAN（virtual local area network，虚拟局域网络）

传输方式：

  • 以太网
  • WLAN（wireless local area network，无线局域网）
  • PPP（point to point protocol，点对点通信协议）
阅读全文 »
0%