树的遍历

morris算法(中序遍历)

空间复杂度$O(1)$

void print_out(node *cur);// 输出节点

node *find_prev(node *cur);// 寻找前驱节点

void morris(node *root) {
  node *cur = root;
  while (cur != NULL) {// 没有遍历完
    if (cur->left == NULL) {// 1: cur没有左子节点
      print_out(cur);
      cur = cur->right;
    } else {
      node *prev = find_prev(cur);
      if (prev->right == NULL) {// 2.1: prev没有右子节点
        prev->right = cur;// 修改树结构
        cur = cur->left
      } else if (prev->right == cur) {// 2.2: prev的右子节点为cur
        prev->right = NULL;// 恢复树结构
        print_out(cur);
        cur = cur->right;
      } else {
        assert(0);
      }
    }
  }
}

图的遍历

DFS

void dfs(node u) {
  u.visit = 1;
  for (int i = 0; i < u.adj.size(); i ++) {
    node v = u.adj[i];
    if (v.visit == 0) {
      dfs(v);
    }
  }
}

BFS

void bfs() {
  q.push(s);
  while (q.empty() == 0) {
    node u = q.top();
    q.pop();
    for (int i = 0; i < u.adj.size(); i ++) {
      node v = u.adj[i];
      if (v.visit == 0) {
        v.depth = u.depth + 1;
        q.push(v);
      }
    }
  }
}

连通度

tarjan算法

时间复杂度$O(V+E)$

void tarjan(int x) {
  s.push(x);
  depth ++;
  dfn[x] = depth;// dfs标记
  low[x] = depth;// tarjan标记
  in_stack[x] = 1;// 是否入栈
  int u, v;
  for (int i = 0; i < near[x].size(); i ++) {
    int v = near[x][i].v;
    if (dfn[v] == 0) {// 未被标记过
      tarjan(v);
      low[x] = my_min(low[x], low[v]);
    } else if (in_stack[v] == 1) {// 已经入栈
      low[x] = my_min(low[x], dfn[v]);
    }
  }

  if (dfn[x] == low[x]) {// 强连通分量
    block ++;// 连通块数目
    while (s.empty() == 0) {
      v = s.top();
      in_stack[v] = 0;
      s.pop();
      if (v == x) break;
    }
  }
}

网络流

EK算法

时间复杂度$O(VE^2)$

dinic算法

时间复杂度$O(V^2E)$

struct path {
  public:
    int u;// 起点
    int v;// 终点
    int c;// 容量
    int f;// 流量
    int back;// 反向边编号

    path() {
      f = 0;
    }
};
int T, n, m;
int path_num;
int s, t;
int level[MAXN];// 分层
vector<int> near[MAXN];// 邻接表
path paths[MAXM];// 所有edge

void add_path(int u, int v, int c) {
  // 正向边
  paths[path_num].u = u;
  paths[path_num].v = v;
  paths[path_num].c = c;
  paths[path_num].f = 0;
  paths[path_num].back = path_num + 1;
  near[u].push_back(path_num);
  path_num ++;
  // 反向边
  paths[path_num].u = v;
  paths[path_num].v = u;
  paths[path_num].c = 0;
  paths[path_num].f = 0;
  paths[path_num].back = path_num - 1;
  near[v].push_back(path_num);
  path_num ++;
}

int dfs(int x, int flow) {
  if (x == t) return flow;
  int total_flow = 0;
  for (int i = 0; i < near[x].size(); i ++) {
    int forward = near[x][i];
    int v = paths[forward].v;
    int w = paths[forward].c - paths[forward].f;
    if (w > 0 && level[v] == level[x] + 1) {
      int extend = dfs(v, my_min(w, flow - total_flow));
      if (extend > 0) {
        int backward = paths[forward].back;
        paths[forward].f += extend;
        paths[backward].f -= extend;
        total_flow += extend;
      }
    }
  }
  return total_flow;
}

int bfs() {
  queue<int> que;
  memset(level, 0, sizeof(level));
  que.push(s);
  level[s] = 1;
  while (que.empty() == 0) {
    int u = que.front();
    que.pop();
    for (int i = 0; i < near[u].size(); i ++) {
      int forward = near[u][i];
      int v = paths[forward].v;
      int w = paths[forward].c - paths[forward].f;
      if (w > 0 && level[v] == 0) {
        level[v] = level[u] + 1;
        que.push(v);
      }
    }
  }
  return level[t];
}

int dinic() {
  int ans = 0;
  while (1) {
    if (bfs() == 0) break;// 没有增广路
    ans += dfs(s, INF);
  }
  return ans;
}

匹配算法

最大匹配:匈牙利算法

时间复杂度$O(VE)$

vector<int> x_near[];// x的邻接表
int y_match[];// y的配对记录
int y_visit[];// 用于dfs的标记

void match() {
  for (int i = 0; i < n; i ++) {// n为x个数
    memset(y_visit, 0, sizeof(y_visit));
    if (dfs(i)) {
      ans ++;
    }
  }
}

int dfs(int x) {
  for (int i = 0; i < x_near[x].size(); i ++) {
    int index = x_near[x][i];
    if (y_visit[index] == 0) {// 没有被dfs过的y
      y_visit[index] = 1;
      if (y_match[index] == -1 || dfs(y_match[index])) {
        // 如果 (没有配对 || 已经配对的能够增广)
        y_match[index] = x;// 为x找到新的配对
        return 1;
      }
    }
  }
  return 0;
}

最优匹配:KM算法

int n;// 总数
int x_ex[MAXN];// x的期望
int y_ex[MAXN];// y的期望
int x_visit[MAXN];// 每轮配对时x的标记
int y_visit[MAXN];// 每轮配对时y的标记
int y_match[MAXN];// 与y配对的x
int y_slack[MAXN];// 每轮遍历x改变的期望
int near[MAXN][MAXN];// 邻接矩阵

int KM();
int dfs(int x);

int dfs(int x) {
  assert(x > 0);
  x_visit[x] = 1;
  for (int i = 1; i <= n; i ++) {
    if (y_visit[i] == 0) {
      int gap = x_ex[x] + y_ex[i] - near[x][i];// 两者的期望和与实际值之差
      if (gap == 0) {
        // 符合要求
        y_visit[i] = 1;// TODO
        if (y_match[i] == 0 || dfs(y_match[i])) {
          // 没有匹配 || 可以增广
          y_match[i] = x;
          return 1;
        }
      } else {
        y_slack[i] = my_min(y_slack[i], gap);
      }
    }
  }
  return 0;
}

int KM() {
  memset(x_ex, 0, sizeof(x_ex));
  memset(y_ex, 0, sizeof(y_ex));// 无期望
  memset(y_match, 0, sizeof(y_match));// 无配对

  // 最大化x期望
  for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= n; j ++) {
      x_ex[i] = my_max(x_ex[i], near[i][j]);
    }
  }

  // 为每个x进行匹配
  for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= n; j ++) {// 初始期望为无穷
      y_slack[j] = INF;
    }

    while (1) {// 直到找到配对为止
      memset(x_visit, 0, sizeof(x_visit));
      memset(y_visit, 0, sizeof(y_visit));

      int extend = dfs(i);
      if (extend == 1) break;

      // 找出最小的slack
      int min_slack = INF;
      for (int j = 1; j <= n; j ++) {
        if (y_visit[j] == 0) {// 不符合要求的y(交错树之外)
          min_slack = my_min(min_slack, y_slack[j]);
        }
      }

      // 调整x, y的期望
      for (int j = 1; j <= n; j ++) {
        if (x_visit[j] == 1) {
          x_ex[j] -= min_slack;
        }
        if (y_visit[j] == 1) {
          y_ex[j] += min_slack;
        } 
      }
    }
  }

  // 计算和
  int ans = 0;
  for (int i = 1; i <= n; i ++) {
    ans += near[y_match[i]][i];
  }

  return ans;
}

字符串匹配

KMP算法

void kmp() {// a[1], b[1]为起始项
  // 计算前缀表
  p_len = 0;
  for (int i = 2; i <= m; i ++) {// 注意初始赋值
    while (p_len && b[p_len + 1] != b[i]) {
      p_len = kmp[p_len];
    }
    if (b[p_len + 1] == b[i]) {
      p_len ++;
      kmp[i] = p_len;
    }
  }
  // 进行匹配
  p_len = 0;
  for (int i = 1; i <= n; i ++) {// 注意初始赋值
    while (p_len && b[p_len + 1] != a[i]) {
      p_len = kmp[p_len];
    }
    if (b[p_len + 1] == a[i]) {
      p_len ++;
      if (p_len == m) {
        printf("%d\n", i - p_len + 1);
        break;
      }
    }
  }
}

overleaf:https://www.overleaf.com/learn/latex/LaTeX_Graphics_using_TikZ:_A_Tutorial_for_Beginners_(Part_3)%E2%80%94Creating_Flowcharts

\begin{tikzpicture}[very thick]
\draw[style={draw=blue!50, fill=blue!20,}] (0,0) ellipse [x radius=2cm, y radius=2cm];
\coordinate [label=center:{$G$}] (A) at (-1.2,0);
\draw[style={draw=red!50, fill=red!20, opacity=0.7,}] (0.2,-0.7) ellipse [x radius=1.2cm, y radius=1.1cm];
\coordinate [label=center:{$N$}] (A) at (0.2,-0.9);
\draw[style={draw=green!50, fill=green!20, opacity=0.7,}] (0.2,0.7) ellipse [x radius=1.2cm, y radius=1.1cm];
\coordinate [label=center:{$H$}] (A) at (0.2,0.9);
\coordinate [label=center:{$H\cap N$}] (A) at (0.2,0);
\end{tikzpicture}

\begin{tikzpicture}[
%overlay, remember picture
]
\coordinate (a0) at (  0.3, 0.2);
\coordinate (b0) at (  3.3, 1.2);
\coordinate (c0) at (  4.1,-1.3);
\coordinate (d0) at (  8.1,-0.3);
\draw (c0) -- (a0);
\draw (c0) -- (d0);
\draw[style={draw=green!50, fill=green!20,}](a0)ellipse[radius=1];
\draw[style={draw=green!50, fill=green!20,}](b0)ellipse[radius=1];
\draw[style={draw=green!50, fill=green!20,}](c0)ellipse[radius=1.3];
\draw[style={draw=green!50, fill=green!20,}](d0)ellipse[radius=1.3];

%\draw[style={draw=red!50, fill=red!20,}] (2,-4) ellipse [radius=0.2];
%\coordinate [label=center:{表示牛逼的点}] (info1) at (2,-5);
%\draw[style={draw=blue!50, fill=blue!20,}] (8,-4) ellipse [radius=0.2];
%\coordinate [label=center:{表示不牛逼的点}] (info2) at (8,-5);
\coordinate (a1) at ( 0  , 0  );
\coordinate (b1) at ( 0  , 0.7);
\coordinate (c1) at ( 0.8, 0.5);
\coordinate (d1) at ( 0.5,-0.2);
\draw (a1) -- (b1);
\draw (a1) -- (c1);
\draw (a1) -- (d1);
\coordinate (a2) at ( 0  +3, 0  +1);
\coordinate (b2) at ( 0  +3, 0.7+1);
\coordinate (c2) at ( 0.8+3, 0.5+1);
\coordinate (d2) at ( 0.5+3,-0.2+1);
\draw (a2) -- (b2);
\draw (a2) -- (c2);
\draw (a2) -- (d2);
\coordinate (a3) at (-3.9+8,-1.1);
\coordinate (b3) at (-3.2+8,-2.0);
\coordinate (c3) at (-4.5+8,-0.9);
\coordinate (d3) at (-4.4+8,-2.1);
\coordinate (e3) at (-3.0+8,-1.1);
\draw (a3) -- (b3);
\draw (a3) -- (c3);
\draw (a3) -- (d3);
\draw (a3) -- (e3);
\coordinate (a4) at (12-3.9,-1.1+1);
\coordinate (b4) at (12-3.2,-2.0+1);
\coordinate (c4) at (12-4.5,-0.9+1);
\coordinate (d4) at (12-4.4,-2.1+1);
\coordinate (e4) at (12-3.0,-1.1+1);
\draw (a4) -- (b4);
\draw (a4) -- (c4);
\draw (a4) -- (d4);
\draw (a4) -- (e4);

\draw[style={draw=blue!50, fill=blue!20,}](a1)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](b1)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](c1)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](d1)ellipse[radius=0.2];

\draw[style={draw= red!50, fill= red!20,}](a2)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](b2)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](c2)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](d2)ellipse[radius=0.2];

\draw[style={draw= red!50, fill= red!20,}](a3)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](b3)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](c3)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](d3)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](e3)ellipse[radius=0.2];

\draw[style={draw=blue!50, fill=blue!20,}](a4)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](b4)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](c4)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](d4)ellipse[radius=0.2];
\draw[style={draw=blue!50, fill=blue!20,}](e4)ellipse[radius=0.2];
\end{tikzpicture}

• label参考
• label位置

\begin{tikzpicture}[
a/.style={circle,draw=blue!50,fill=blue!20,very thick,minimum size=10mm},
b/.style={circle,draw=green!50,fill=green!20,very thick,minimum size=10mm}
]
\node[a,label={[shift={(0,-2)}]1}] (n1) at (0, 0){a};
\node[a,label={[shift={(0,-2)}]2}] (n2) at (2, 0){a};
\node[b,label={[shift={(0,-2)}]3}] (n3) at (4, 0){b};
\node[a,label={[shift={(0,-2)}]4}] (n4) at (6, 0){a};
\node[b,label={[shift={(0,-2)}]5}] (n5) at (8, 0){b};
\draw[->,thick](n1) to (n2);
\draw[->,thick](n2) to (n3);
\draw[->,thick](n3) to (n4);
\draw[->,thick](n4) to (n5);
\draw[shorten >= 0pt,->,thick](n2) to[in=150,out=30,loop,looseness=4.8]node[midway,above]{a}(n2);
\draw[->,thick](n4) to[in=-30,out=-150]node[midway,below]{a}(n2);
\end{tikzpicture}

\newfontfamily\DejaVu{DejaVu Sans Mono for Powerline}
\def\Font#1{\fontsize{#1}{\baselineskip}\DejaVu\textbf}
\begin{tikzpicture}[remember picture, overlay]
  \node [shift={(0cm,-3cm)}]  at (current page.north west)
  {%
  \begin{tikzpicture}[remember picture, overlay]
    \draw [fill=gray] (0,3) -- (3,3) -- (0,0) -- cycle ;
    \draw [fill=white] (0,3) -- (2,3) -- (0,1) -- cycle ;
    \draw (0,0) to node[midway, above, rotate=45] {\textcolor{white}{\Font{9}{fork me on github}}} (3,3) ;
    \draw (0,1) to node[midway, above, rotate=45] {\includegraphics[width=.05\textwidth]{pictures/github}} (2,3) ;
  \end{tikzpicture}
  };
\end{tikzpicture}

零散笔记

摄像头(webcam)

sudo apt install v4l-util cheese
sudo cheese

修改摄像头权限

ls -ltrh /dev/video*
sudo chmod 777 /dev/video0
cheese

重启驱动

• 重启触摸板驱动

sudo modprobe -r psmouse
sudo modprobe psmouse

或

sudo rmmode psmouse
sudo modprobe psmouse

或

xinput list
xinput --disable {编号}
xinput --enable {编号}

在文件夹中执行脚本

在文件$\to$首选项$\to$行为$\to$可执行文本文件

快捷键

不要出现fn+super的组合

截屏

• 复制截图到剪切板:ctrl+print
• 复制窗口截图到剪切板:ctrl+alt+print
• 复制选区截图到剪切板:shift+ctrl+print
• 保存截图到图片:print
• 保存窗口截图到图片:alt+print
• 保存选区截图到图片:shift+print
• 录屏:shift+ctrl+alt+r

禁用快捷键

backspace

WLAN

wifi连接

参考:askubuntu

• 查看网卡名:iwconfig

• 扫描:nmcli dev wifi

• 连接:nmcli dev wifi connect WLAN_NAME password PASSWORD

• 忘记:nmcli c delete WLAN_NAME

• 关闭热点:nmcli dev disconnect wlp2s0

• 关闭wlan:nmcli radio wifi off

• 开启wlan:nmcli radio wifi on

热点

nm-connection-editor

1. +->Wifi->Mode:Hotspot

2. 开启热点

   • 设置->(右上角)Connect to Hidden Network
   • 设置$\to$wifi$\to$打开wifi热点

共享wifi

• create_ap:github

误删PATH救急

• Linux通用?

export PATH=/usr/local/sbin:/usr/local/bin:/sbin:/bin:/usr/sbin:/usr/bin:$PATH

不要忘记加:PATH

安装字体

sudo mkdir /usr/share/fonts/{name}
sudo cp {font}.ttf /usr/share/fonts/{name}
cd /usr/share/fonts/{name}
sudo mkfontscale
sudo mkfontdir
sudo fc-cache -fv

文件编码

• enca等
• iconv

功能性软件

文件管理器

由于ubuntu自带的文件管理器太睿智,推荐以下文件管理器

• pcmanfm
• nemo
• thunar
• dolphin

修改默认文件管理器

TODO:/etc/gnome/defaults.list(直接修改好像没用)

# what's the current default file manager?
xdg-mime query default inode/directory

# set nautilus as a default file manager
xdg-mime default nautilus.desktop inode/directory # application/x-gnome-saved-search

软件对应/usr/share/applications下的desktop名

matlab

离线激活

1. 输入许可证路径license_standalone.lic

2. 修改matlab所在目录的读写权限以及用户组

3. 讲破解文件的lmgrimpl文件覆盖原matlab文件

许可证失效(无法打开matlab)

删除matlab/licenses下的文件

mathematica

报错

CRITICAL FAILURE: PrintIntroduction() Error
$ProductTitle not defined.

路径不能有空格

一个解决包依赖问题的软件

sudo apt install aptitude

• (示例)卸载libreoffice

sudo aptitude purge libreoffice6.0

字体编辑

sudo add-apt-repository ppa:fontforge/fontforge
sudo apt-get update
sudo apt-get install fontforge

修改字体名称

1. 打开字体文件
2. 基础->字体信息
3. 文件->生成字体->(可选)选择TrueType(ttf)

图像编辑

sudo apt install gimp

sudo apt install krita
sudo apt install krita-l10n

图像转换

sudo apt install sam2p
sam2p shit.png shit.gif

gif录屏

• byzanz

sudo apt install byzanz 
byzanz-record --duration=50 --delay=3 --x=1030 --y=100 --height=500 demo1.gif

桌面便签(Indicator Stickynotes)

sudo add-apt-repository ppa:umang/indicator-stickynotes
sudo apt-get update
sudo apt-get install indicator-stickynotes

下载器(TODO)

• wget:单线程
• curl:单线程
• axel:多线程
• aria2:可以设置线程
• mwget:多线程版wget
• Prozilla:多线程,cmd,gui
• Downloader for X:多线程,gui
• MyGet:多线程
• Linuxdown:多线程,cmd
• Transmission:磁力,gui(不会用)
• Uget:cURL+aria2

基本没用

屏幕管理

• arandr

sudo apt install arandr

镜像源

/etc/apt/sources.list

• ubuntu 19.04

deb http://cn.archive.ubuntu.com/ubuntu/ disco main restricted
deb http://cn.archive.ubuntu.com/ubuntu/ disco-updates main restricted
deb http://cn.archive.ubuntu.com/ubuntu/ disco universe
deb http://cn.archive.ubuntu.com/ubuntu/ disco-updates universe
deb http://cn.archive.ubuntu.com/ubuntu/ disco multiverse
deb http://cn.archive.ubuntu.com/ubuntu/ disco-updates multiverse
deb http://cn.archive.ubuntu.com/ubuntu/ disco-backports main restricted universe multiverse
deb http://security.ubuntu.com/ubuntu disco-security main restricted
deb http://security.ubuntu.com/ubuntu disco-security universe
deb http://security.ubuntu.com/ubuntu disco-security multiverse

• 中科大

deb https://mirrors.ustc.edu.cn/ubuntu/ bionic main restricted universe multiverse
deb-src https://mirrors.ustc.edu.cn/ubuntu/ bionic main restricted universe multiverse
deb https://mirrors.ustc.edu.cn/ubuntu/ bionic-updates main restricted universe multiverse
deb-src https://mirrors.ustc.edu.cn/ubuntu/ bionic-updates main restricted universe multiverse
deb https://mirrors.ustc.edu.cn/ubuntu/ bionic-backports main restricted universe multiverse
deb-src https://mirrors.ustc.edu.cn/ubuntu/ bionic-backports main restricted universe multiverse
deb https://mirrors.ustc.edu.cn/ubuntu/ bionic-security main restricted universe multiverse
deb-src https://mirrors.ustc.edu.cn/ubuntu/ bionic-security main restricted universe multiverse
deb https://mirrors.ustc.edu.cn/ubuntu/ bionic-proposed main restricted universe multiverse
deb-src https://mirrors.ustc.edu.cn/ubuntu/ bionic-proposed main restricted universe multiverse

• 清华

deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic main restricted universe multiverse
deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic main restricted universe multiverse
deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-updates main restricted universe multiverse
deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-updates main restricted universe multiverse
deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-backports main restricted universe multiverse
deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-backports main restricted universe multiverse
deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-security main restricted universe multiverse
deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-security main restricted universe multiverse
deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-proposed main restricted universe multiverse
deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ bionic-proposed main restricted universe multiverse

• 网易

deb http://mirrors.163.com/ubuntu/ bionic main restricted universe multiverse
deb http://mirrors.163.com/ubuntu/ bionic-security main restricted universe multiverse
deb http://mirrors.163.com/ubuntu/ bionic-updates main restricted universe multiverse
deb http://mirrors.163.com/ubuntu/ bionic-proposed main restricted universe multiverse
deb http://mirrors.163.com/ubuntu/ bionic-backports main restricted universe multiverse
deb-src http://mirrors.163.com/ubuntu/ bionic main restricted universe multiverse
deb-src http://mirrors.163.com/ubuntu/ bionic-security main restricted universe multiverse
deb-src http://mirrors.163.com/ubuntu/ bionic-updates main restricted universe multiverse
deb-src http://mirrors.163.com/ubuntu/ bionic-proposed main restricted universe multiverse
deb-src http://mirrors.163.com/ubuntu/ bionic-backports main restricted universe multiverse

• 阿里

deb http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-security main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-updates main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-proposed main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-backports main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-security main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-updates main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-proposed main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-backports main restricted universe multiverse

apt

• apt与apt-get区别
• apt-get示例

系统监视器安装

sudo apt install gnome-system-monitor

分盘

1. 安装失败

• swap:1024M,主分区
• /:10G,主分区
• /boot:128M,主分区
• /home:剩余,主分区

2. 安装成功

• swap:4096M,逻辑分区
• /:剩余,主分区

3. 未知

• swap:4096M,逻辑分区
• /boot:200M,主分区
• /:10G,主分区
• /home:剩余,逻辑分区

4. 未知

• /:全部,主分区

驱动

ubuntu安装mac设备驱动

总览:github
触摸板/键盘:github

参考代码(不适用于macbook8,1)

sudo echo -e "\n# applespi\napplespi\nspi_pxa2xx_platform\nintel_lpss_pci" >> /etc/initramfs-tools/modules
sudo
sudo apt install dkms
sudo git clone https://github.com/roadrunner2/macbook12-spi-driver.git /usr/src/applespi-0.1
sudo dkms install -m applespi -v 0.1

安装软件

基本

• sublime
• chromium:注意数据备份.config/chromium
  • tamper monkey
  • Adblock Plus
  • SwitchyOmega
  • crxMouse Top Gestures
• dukto:3系统互传软件
• hyper:配置文件~/.hyper.js
• vscode
• gnome-tweak:如果还在用gnome
  • dash to panel
  • topicons plus
  • user themes
• 搜狗输入法:CSDN
  • 官网下载deb
  • sudo apt install -f && sudo dpkg -i sougou.deb
  • 设置->区域和语言->键盘输入法系统(点击任务栏的输入法图标->Configure)
• 日语输入法

  sudo apt install fcitx-mozc # sudo apt install fcitx-anthy # im-config -n fcitx

重启(fcitx configuration)

• 片假名切换:f7
  • gparted:磁盘分区
  • exfat-utils:支持exfat格式的u盘

非基本

• Indicator Stickynotes
• QQ(见wine)
• wps

deepin wine软件

• QQ
• TIM
• QQ轻聊版
• 微信
• Foxmail
• 百度网盘
• 360压缩
• WinRAR
• 迅雷极速版

详细,github

软件的文件存放位置

• QQ:

/home/lynx/.deepinwine/Deepin-QQ/dosdevices/c:/users/lynx/My Documents/Tencent Files/$account/FileRecv

deepin wine字体异常处理

修改注册表(TODO)

1. 新建(任何位置,文件名随意)zh.reg
   1.1. 字体链接

   [HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\CurrentVersion\FontLink\SystemLin] "字体名"="字体文件"

   1.2. 字体(强制)替换

   [HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\CurrentVersion\FontSubstitutes] "字体名"="字体文件"

   1.3 字体(缺失)替换

   [HKEY_CURRENT_USER\Software\\Wine\\Fonts\\Replacements] "字体名"="字体文件"

2. 修改注册表(貌似没用)

deepin-wine regedit zh.reg

补充字体文件

• 字体文件存放位置:./deepin-wine/软件名/driver_c/windows/fonts/

wps软件

缺少字体的处理方法

该方法已失效

下载并解压字体文件夹wps-font-symbols

git clone https://github.com/pengphei/wps-font-symbols
sudo cp -r wps-font-symbols /usr/share/fonts
# cd /usr/share/fonts
# sudo chmod 755 wps-font-symbols
cd /usr/share/fonts/wps-font-symbols
# sudo chmod 644 *
sudo mkfontdir
sudo mkfontscale
fc-cache

或直接从windows复制对应字体

系统设置

笔记本行为设定

• 合盖不休眠:/etc/systemd/logind.conf

HandleLidSwitch=ignore

CSDN

密钥环

密码和密钥$\to$默认密钥环$\overset{\mbox{右键}}{\to}$更改密码$\to$空白

grub配置

• 位置

/etc/default/grub

• 内容修改

GRUB_DEFAULT=saved
GRUB_SAVEDEFAULT=true

• 生效设置

sudo grub-set-default 2
sudo update-grub

数字任意

时间配置

sudo apt-get install ntpdate
sudo ntpdate time.windows.com
sudo hwclock --localtime --systohc

gnome-shell-entensions

• sysgeek
• linux.cn

chrome扩展

sudo apt-get install chrome-gnome-shell

chrome浏览器插件

重启gnome-shell

alt+f2$\to$r

extension位置

• ~/.local/share/gnome-shell/extensions
• /usr/share/gnome-shell/extensions

解决显示应用程序2个dock

cd /usr/share/gnome-shell/extensions
sudo rm -rf ubuntu-dock@ubuntu.com

解决桌面图标在重启后乱序

安装一个新的桌面图标扩展,关闭gnome-tweaks的桌面图标显示

外观修改

修改登录背景图片

/etc/alternatives/gdm3.css:

#lockDialogGroup {
  background: url(file:///usr/share/backgrounds/Aatrox.jpg);
  background-position: center;
  background-size: cover; }

默认开机动画

sudo update-alternatives --config default.plymouth

修改开机动画

ubuntugeek
更多

1. 创建新文件夹

sudo mkdir /usr/share/plymouth/themes/myTheme

2. vi myTheme/myTheme.plymouth

[Plymouth Theme]
Name=MyTheme
Description=随你
ModuleName=script

[script]
ImageDir=/usr/share/plymouth/themes/myTheme
ScriptFile=/usr/share/plymouth/themes/myTheme.script

3. 复制png(必须)图片到myTheme

4. vi myTheme/myTheme.script

wallpaper_image = Image("Aatrox_1080.png");
screen_width = Window.GetWidth();
screen_height = Window.GetHeight();
resized_wallpaper_img = wallpaper_image.Scale(screen_width, screen_height);
wallpaper_sprite = Sprite(resized_wallpaper_img);
wallpaper_sprite.SetZ(-100);

5. 安装主题

sudo update-alternatives --install /usr/share/plymouth/themes/default.plymouth default.plymouth /usr/share/plymouth/themes/myTheme/myTheme.plymouth 100
sudo update-alternatives --config default.plymouth
sudo update-initramfs -u

修改grub主题

1. /boot/grub/themes文件夹创建
2. 配置文件/etc/grub.d/00_header:

# You should have received a copy of the GNU General Public License
# along with GRUB.  If not, see <http://www.gnu.org/licenses/>.

GRUB_THEME="/boot/grub/themes/Vimix/theme.txt"
GRUB_GFXMODE="1920x1080x32"

可按照尺寸修改背景图片

3. 更新配置

sudo update-grub

语言和文字

• 对彩色表情的支持(TODO):

  • fonts-noto-color-emoji
  • fonts-emojione

• 对特定软件使用特定语言打开(不能已经打开其他窗口)

sh -c "LANGUAGE=en /bin/chromium-browser %U"

• 修改语言和编码

  • 位置:/etc/default/locale
  • 查看当前语言:locale

• locale备份

LANG=zh_CN.UTF-8
LANGUAGE=zh_CN:en_US:en
LC_CTYPE="zh_CN.UTF-8"
LC_NUMERIC="zh_CN.UTF-8"
LC_TIME="zh_CN.UTF-8"
LC_COLLATE="zh_CN.UTF-8"
LC_MONETARY="zh_CN.UTF-8"
LC_MESSAGES="zh_CN.UTF-8"
LC_PAPER="zh_CN.UTF-8"
LC_NAME="zh_CN.UTF-8"
LC_ADDRESS="zh_CN.UTF-8"
LC_TELEPHONE="zh_CN.UTF-8"
LC_MEASUREMENT="zh_CN.UTF-8"
LC_IDENTIFICATION="zh_CN.UTF-8"
LC_ALL=

AS和cmake笔记

android的cpu架构

• android查看cpu架构(termux)

cat /proc/cpuinfo

• AArch32是ARMv7架构的一种执行状态
• AArch64是ARMv8架构的一种执行状态
  • 参考
  • 参考
• 64位ARMv8包含上面两种状态
  • 参考
  • 知乎
  • 知乎

cmake在AS中的使用

不要把mk和cmake两种方法混淆

输出控制(message)

(TODO)如果想直接看到打印信息,使用WARNING以上的级别进行打印

• message(WARNING "fuck")
  • 在Build->Build Output->CMake warnings查看
  • 在Build->Build Output->Toggle View查看

Android

Android Studio版本为3.5

OpenCV for Android 3.x:只使用java模块

参考:CSDN,示例:压缩图片

1. File->New->Import Module->选择opencv文件夹下的sdk/java文件夹,此时Android Studio会自动加载Module name
2. File->Project Structure->Dependencies->选择app->添加Module Dependency->选择opencv
3. 将opencv文件夹下的sdk/native/libs下自己手机cpu对应的架构文件夹复制到app/libs下
4. 将opencv模块的build.gradle的complieSdkVersion,buildToolVersion,minSdkVersion,targetSdkVersion改成和app的build.gradle一样
5. 在app的build.gradle的android节点下添加

   sourceSets { main { jni.srcDirs = [] jniLibs.srcDirs = ['libs'] } }

然后点击sync now

6. 在使用opencv前进行初始化

   static { if (!OpenCVLoader.initDebug()) { ... } }

常见问题

1. Caused by: CvException [org.opencv.core.CvException: OpenCV(4.1.1) /build/master_pack-android/opencv/modules/java/generator/src/cpp/utils.cpp:101: error: (-215:Assertion failed)

在Mat与Bitmap互转的时候长宽设置不对

OpenCV for Android 3.x:使用native模块

方法一

1. CMakeLists.txt编写

在CMakeLists.txt中确定两个关键路径

• /sdk/native/jni/include:头文件位置
• /sdk/native/libs/${ANDROID_ABI}/libopencv_java3.so:库位置

cmake_minimum_required(VERSION 3.4.1)

#1
set(opencv_version OpenCV4-android-sdk)
set(opencv_lib libopencv_java4.so)

#2
include_directories(/home/lynx/fuck_mount/Android/Proj/${opencv_version}/sdk/native/jni/include)
add_library(fuck SHARED IMPORTED)
  set_target_properties(fuck PROPERTIES IMPORTED_LOCATION
      /home/lynx/fuck_mount/Android/Proj/${opencv_version}/sdk/native/libs/${ANDROID_ABI}/${opencv_lib})


add_library(保持原样)

find_library(保持原样)

target_link_libraries(
        native-lib

        #3
        fuck

        ${log-lib})

2. 修改app的build.gradle

在android节点下插入

sourceSets {
  main {
    jniLibs.srcDirs = ['/home/lynx/fuck_mount/Android/Proj/OpenCV4-android-sdk/sdk/native/libs']
  }
}

方法二

参考:CSDN

还没有成功

1. CMakeLists.txt编写

在CMakeLists.txt中确定一个关键路径

• /sdk/native/jni/include:头文件位置

cmake_minimum_required(VERSION 3.4.1)

#1
set(opencv_version OpenCV4-android-sdk)
set(opencv_lib libopencv_java4.so)

#2
set(OpenCV_STATIC ON)
set(OpenCV_DIR /home/lynx/fuck_mount/Android/Proj/${opencv_version}/sdk/native/jni)
  find_package(OpenCV REQUIRED)
if (OpenCV_FOUND)
  message(WARNING "opencv libs: ${OpenCV_LIBS}")
else (OpenCV_FOUND)
  message(WARNING "opencv not found")
endif(OpenCV_FOUND)

add_library(保持原样)

find_library(保持原样)

target_link_libraries(
        native-lib

        ${log-lib}

        #3
        ${OpenCV_LIBS})

常见问题

1. java.lang.UnsatisfiedLinkError: dlopen failed: library "libopencv_java3.so" not found

这是由于忘记了上面的第2步.Android Studio默认的jni路径为app/src/main/jniLibs,除了在CMakeLists.txt中导入opencv的库以外还需要二选一

• 将对应版本opencv的库(libs/下一级的各个${ANDROID_ABI}文件夹)移动到jniLibs下
• 在build.gradle中修改默认jni路径(见上面第2步)

2. 各种undefined reference to *

如std::ios_base::Init::Init()等

未解决

3. undefined reference to `AndroidBitmap_getInfo'

各类AndroidBitmap的问题

在CMakeLists.txt增加

target_link_libraries(
        # TODO 解决 AndroidBitmap 报错
        jnigraphics)

参考:CSDN,这是一个很小的库,展示一个稳定的,基于C语言的接口,使本机代码安全地访问Java对象的像素缓冲区的位图

OpenCV for Android 4.x:使用native模块

方法一

同3.x版本的方法一

常见问题

1. java.lang.UnsatisfiedLinkError: dlopen failed: library "libc++_shared.so" not found

stackoverflow

(不确定的解决方法)在app的gradle中修改

externalNativeBuild {
  cmake {
    cppFlags ""
      arguments "-DANDROID_STL=c++_shared"
  }
}

不要使用gnustl_shared或gnustl_static,已经过时

2. java.lang.UnsatisfiedLinkError: dlopen failed: library "libopencv_java4.so" not found

解决方案同3.x版本

OpenCV for Android 4.x:使用java+native模块

参考:CSDN

1. 加载native模块

2. File->New->Import Module->选择opencv文件夹下的sdk/java文件夹,自己定义模块的名字

3. 修改模块的gradle文件

// 将原来的application改成library
apply plugin: 'com.android.library'

android {
  // 将版本信息改得和`app`的`build.gradle`一样
  compileSdkVersion 29
  buildToolsVersion "29.0.2"
  defaultConfig {
    // 删除applicationId
    minSdkVersion 15
    targetSdkVersion 29
    versionCode 1
    versionName "1.0"
    testInstrumentationRunner "androidx.test.runner.AndroidJUnitRunner"
  }
  // 不改动
  buildTypes {
    release {
      minifyEnabled false
        proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.txt'
    }
  }
}

4. (重复)修改app的gradle文件,加载native/lib模块

javacv(使用不完整OpenCV 4.1.0)

不同导入方法,import的class位置可能不同

opencv部分功能的初始化

github原文

Loader.load(opencv_java.class);// 不能直接放在class开头

使用远程导入

app的build.gradle示例(最外节点)

ext {
    versions = [
            'javacv': '1.4.4',
            'ffmpeg': '4.1',
            'opencv': '4.0.1'
    ]
}

dependencies {
    ...
    implementation(group: 'org.bytedeco', name: 'javacv-platform', version: versions.javacv) {
      exclude group: 'org.bytedeco.javacpp-presets'
    }
    implementation group: 'org.bytedeco.javacpp-presets', name: 'ffmpeg', version: "${versions.ffmpeg}-${versions.javacv}"
    implementation group: 'org.bytedeco.javacpp-presets', name: 'ffmpeg', version: "${versions.ffmpeg}-${versions.javacv}", classifier: 'android-arm'
    implementation group: 'org.bytedeco.javacpp-presets', name: 'ffmpeg', version: "${versions.ffmpeg}-${versions.javacv}", classifier: 'android-arm64'
    implementation group: 'org.bytedeco.javacpp-presets', name: 'opencv', version: "${versions.opencv}-${versions.javacv}"
    implementation group: 'org.bytedeco.javacpp-presets', name: 'opencv', version: "${versions.opencv}-${versions.javacv}", classifier: 'android-arm'
    implementation group: 'org.bytedeco.javacpp-presets', name: 'opencv', version: "${versions.opencv}-${versions.javacv}", classifier: 'android-arm64'
}

作为lib导入

根据手机具体的cpu架构进行导入

app的build.gradle

dependencies {
    implementation fileTree(dir: 'libs', include: ['*.jar'])
}

将文件(视具体情况)

• javacpp.jar
• javacv.jar
• openblas.jar
• openblas-android-arm64.jar
• opencv.jar
• opencv-android-arm64.jar
  复制到app/libs/文件夹里

常见错误

1. cpu架构错误/缺少(需添加-android-arm之类的库)

2019-10-27 16:01:32.439 29256-29322/? E/AndroidRuntime: FATAL EXCEPTION: AsyncTask #1
    Process: com.github.crazyorr.ffmpegrecorder, PID: 29256
    java.lang.RuntimeException: An error occurred while executing doInBackground()

2. 没有对opencv初始化

2019-10-27 16:00:43.930 28933-28933/? E/AndroidRuntime: FATAL EXCEPTION: main
    Process: com.example.javacv, PID: 28933
    java.lang.UnsatisfiedLinkError: No implementation found for long org.opencv.core.Mat.n_Mat() (tried Java_org_opencv_core_Mat_n_1Mat and Java_org_opencv_core_Mat_n_1Mat__)

3. 缺少openblas的相关jar库

2019-10-27 15:59:23.158 28618-28618/? E/AndroidRuntime: FATAL EXCEPTION: main
    Process: com.example.javacv, PID: 28618
    java.lang.NoClassDefFoundError: Failed resolution of: Lorg/bytedeco/openblas/presets/openblas;

OpenCV 4.x source code

参考:CSDN

1. 修改参数

Android Studio的sdk下的ndk:ndk/build/cmake/android.toolchain.cmake(第112行)

elseif(ANDROID_TOOLCHAIN_NAME MATCHES "-[0-9].[0-9]$")
  set(ANDROID_TOOLCHAIN clang) # 将gcc改成clang
endif()

opencv 4.x源码:/platforms/android/build_sdk.py(第113行)

self.cmake_vars = dict(
    ANDROID_STL="c++_static", # change `gnustl_static` to `c++_static` or `c++_shared`
    ANDROID_ABI=self.name,
    ANDROID_PLATFORM_ID=platform_id,
)

opencv 4.x源码:/CMakeLists.txt(第426行和429行)(可以根据需要修改)

# OCV_OPTION(BUILD_SHARED_LIBS        "Build shared libraries (.dll/.so) instead of static ones (.lib/.a)" NOT (ANDROID OR APPLE_FRAMEWORK) )
OCV_OPTION(BUILD_SHARED_LIBS        "Build shared libraries (.dll/.so) instead of static ones (.lib/.a)" ON ) # 生成动态库
OCV_OPTION(BUILD_opencv_apps        "Build utility applications (used for example to train classifiers)" (NOT ANDROID AND NOT WINRT) IF (NOT APPLE_FRAMEWORK) )
OCV_OPTION(BUILD_opencv_js          "Build JavaScript bindings by Emscripten" OFF )
OCV_OPTION(BUILD_ANDROID_PROJECTS   "Build Android projects providing .apk files" OFF )
# OCV_OPTION(BUILD_ANDROID_PROJECTS   "Build Android projects providing .apk files" ON  IF ANDROID )

2. 配置JAVA_HOME

使用Android Studio的JDK位置

export JAVA_HOME=/home/lynx/fuck_mount/AS/jre

3. 执行platforms/android/build_sdk.py,完成编译

./build_sdk.py --ndk-path {ndk路径} --sdk_path {android sdk路径} {目标位置} {opencv源码位置}
# example
/home/lynx/fuck_mount/opencv_4_1_0/opencv-4.1.0/platforms/android/build_sdk.py --ndk_path /home/lynx/fuck_mount/Android/SDK/ndk/18.1.5063045 --sdk_path /home/lynx/fuck_mount/Android/SDK /home/lynx/fuck_mount/opencv_4_1_0/android_build /home/lynx/fuck_mount/opencv_4_1_0/opencv-4.1.0

• sdk-path:Android Studio的SDK目录
• ndk-path:Android Studio的SDK目录下ndk/{ndk版本号文件}

额外说明

不需要额外安装的软件:jdk,ninja-build,ndk.直接使用android studio的即可
不需要安装的软件:ant,ccache

目前还没能成功编译android project

能够混合使用:

• OpenCV 3.x的java库(配置见上)
• TODO

常见问题

1. java.lang.UnsatisfiedLinkError: dalvik.system.PathClassLoader[DexPathList[[zip file "/data/app/com.example.stitch-sPWgBONIqUrdX9XLB1OY6w==/base.apk"],nativeLibraryDirectories=[/data/app/com.example.stitch-sPWgBONIqUrdX9XLB1OY6w==/lib/arm64, /data/app/com.example.stitch-sPWgBONIqUrdX9XLB1OY6w==/base.apk!/lib/arm64-v8a, /system/lib64, /product/lib64]]] couldn't find "libnative-lib.so"

缺少相应ABI的so库(目前计时在gradle里加入abiFilters也没有用),上述报错是因为没有编译全ABI.ABI配置:opencv-4.x/platforms/android/ndk-18-api-level-21.config.py

Linux

OpenCV source code 3.x(3.4.7)

gui安装

和4.x一样

常见问题

1. fatal error: Eigen/Core: 没有那个文件或目录``#include <Eigen/Core>

   1. 修改WITH_EIGEN=OFF

   2. (或)

      • 先保证安装eigen:sudo apt install libeigen3-dev
      • 添加EIGEN_INCLUDE_PATH=/usr/include/eigen3(视具体情况)

2. ippicv_linux_20141027.tgz下载失败

   CMake Error at 3rdparty/ippicv/downloader.cmake:71 (file): file DOWNLOAD HASH mismatch for file: [/home/lynx/fuck_mount/opencv_3_0_0/opencv/3rdparty/ippicv/downloads/linux-8b449a536a2157bcad08a2b9f266828b/ippicv_linux_20141027.tgz] expected hash: [8b449a536a2157bcad08a2b9f266828b] actual hash: [5c4f36bf7b2421d52289f0297ba1406f] status: [28;"Timeout was reached"]

TODO

3. ippicv_2019_lnx_intel64_general_20180723.tgz下载超时

   IPPICV: Download: ippicv_2019_lnx_intel64_general_20180723.tgz CMake Warning at cmake/OpenCVDownload.cmake:193 (message): IPPICV: Download failed: 28;"Timeout was reached"

   1. 在opencv/opencv_3rdparty的ippicv对应分支中下载对应的tgz

   2. 将tgz放入/home/lynx/Downloads/

   3. 修改opencv的source code: vi /3rdparty/ippicv/ippicv.cmake,将ippicv的https地址改为file:/home/lynx/Downloads/

   4. 重新cmake-gui

OpenCV source code 4.x(4.1.0)

依赖包

sudo apt install libgtk2.0-dev pkg-config

命令行安装(TODO)

1. cmake

cd {生成makefile的位置}
cmake {source的位置}

2. make

cd {生成makefile的位置}
make

3. make install

make install {安装的位置}

gui安装

参考:CSDN

1. 安装cmake-gui

sudo apt install cmake-gui

2. 启动cmake-gui

cd {build二进制文件的目录}
cmake-gui {opencv source code}

3. Configure->Unix Makefiles:Use default native compilers->finish

4. 狂点Configure知道没有红色区域

5. 赋值

6. 狂点Configure

7. Generate,等到Generating done

8. 在build路径make

sudo make -j4 # 具体看有多少cpu
cat /proc/cpuinfo | grep "processor" | wc -l # 查看cpu个数
sudo make install

9. 配置opencv4.pc(2选1)

   • 修改PKG_CONFIG_PATH:增加{你cmake_install的路径}/lib/pkgconfig(opencv4.pc所在的路径)
   • (TODO,没试过)复制opencv4.pc到/usr/lib/pkgconfig

10. 配置库路径,(新建)/etc/ld.so.conf.d/opencv.conf

{你cmake_install路径}/lib/ # 自己的lib路径

sudo ldconfig

11. 编译测试

如果是opencv.pc将opencv4改成opencv

pkg-config --modversion opencv4
g++ a.cpp `pkg-config --cflags --libs opencv4` -o test && ./test

常见问题

1. 在其他项目中用CMake导入OpenCV模块:

   find_package(OpenCV REQUIRED) include_directories(${OpenCV_INCLUDE_DIRS})

之后cmake出现By not providing "FindOpenCV.cmake" in CMAKE_MODULE_PATH ...:

这是由于没有设置环境变量OpenCV_DIR,设置为OpenCV编译后的目录下含有OpenCVConfig.cmake的对应路径

requests(静态html/json)

参数设置

cookies

headers

headers = {
  'User-Agent': 'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/79.0.3945.79 Chrome/79.0.3945.79 Safari/537.36',
  'Host':'music.163.com',
  'Referer':'https://music.163.com'
}

selenium + phantomjs(js渲染)

安装

sudo apt install phantomjs
python3 -m pip install selenium # 不要直接用pip3

题解

使用tarjan缩点,并计算出度为0点的数量

题解

1. 按仇恨值取出罪犯对(u, v)

2. 对每个罪犯x,如果没有标记其敌人(enemy[x] == -1),则进行标记(enemy[u] = fa[v])

3. 对每个罪犯x,如果已经标记了敌人,则讲敌人与另一个罪犯合并(union(enemy[u], v))

二分搜索，默认升序

lower_bound(a,a + n,b,cmp)

前闭后开[first, last)区间进行二分查找，返回大于或等于val的第一个元素位置
如果所有元素都小于val，则返回last的位置，且last的位置是越界的

upper_bound(a,a + n,b,cmp)

返回序列[first, last)中的第一个大于值val的位置

binary_search(a,a + n,b,cmp)

在已排序的[first, last)中寻找元素val，如果[first, last)内有等于val的元素，它会返回true，否则返回false，它不返回查找位置

全排列，默认next升序

next_permutation(a, a + n, b, cmp);
prev_permutation(a, a + n, b, cmp);

循环？

运算符重载？

=重载的例子（class之外）

sb& sb::operator=(const sb& a)
{
  if (this == &a)
    return *this;
  x = a.y;
  y = a.x;
  return *this;
}

==重载

bool operator==(sb a, sb b)
{
  if (a.x == b.x&&a.y == b.y)
    return 1;
  return 0;
}

浮点数精度控制

cout << fixed << setprecision(9) << a << endl;
cout << setiosflags(ios::scientific) << setprecision(4) << a << endl;

vector使用

vector <fuck> edge[100];
edge[1].push_back(temp);
for (int i = 0; i < edge[1].size(); i ++)
{
  edge[1].at(i).u = 1;
}
edge[1].clear();

queue

queue<int> q;
q.front();

priority_queue

struct vfuck
{
  long long dis;
}vnode[50001];
struct cmp
{
  bool operator()(vfuck a, vfuck b)
  {
    return a.dis > b.dis;
  }
};
priority_queue <vfuck, vector<vfuck>, cmp> pq;// 最小堆
while (pq.empty() == 0)
{
  tmp = pq.top();
  pq.push(tmp);
  pq.pop();
}

struct path {
  int len;// 长度
  friend bool operator < (path a, path b) {// 不能是 >
    return a.len > b.len;// 最小堆
  }
};

priority_queue <path> paths;// 最小堆

map

赋值/输出

map <string, int> fuck;
map <string, int>::iter;
for (iter = fuck.begin(); iter != fuck.end(); iter ++)
{
  fuck["***"] = 1;
  cout << iter->first << iter->second;
}

其他

cnblog

通用

建表

create table if not exists customers(
    cid char(4) not null,
    cname char(20) not null,
    city char(20),
    discnt real,
    primary key ( cid )
) character set = utf8 -- 支持中文;

修改并查看注释(comment)

alter table customers
change column cid
cid char(4) not null comment '编号',
change column cname
cname char(20) not null comment '姓名',
change column city
city char(20) comment '城市',
change column discnt
discnt real comment '折扣';
show full columns from customers;

insert去重

• ignore

insert ignore into table (column)
 values
 ...

• on duplicate key update

TODO

• replace into

TODO

更新表数据

update table_name set item="shit" where fuck="fuck";

每组前n

参考

计算时间差

SELECT TIMESTAMPDIFF(MONTH,'2009-10-01','2009-09-01');
SELECT TIMESTAMPDIFF(MONTH,'2009-10-01','2009-09-01') as a;

其中MONTH部分可以更改为

• SECOND
• MINUTE
• HOUR
• DAY
• MONTH
• YEAR

通配符

select season_id, id, title, p_year, c_year from season
where title like '%鲁路修%'
order by p_year;

其他

添加用户

insert

use mysql
insert into user ( Host, User, Select_priv, Insert_priv, Update_priv, Delete_priv, Create_priv, Drop_priv, Reload_priv, Shutdown_priv, Process_priv, File_priv, Grant_priv, References_priv, Index_priv, Alter_priv, Show_db_priv, Super_priv, Create_tmp_table_priv, Lock_tables_priv, Execute_priv, Repl_slave_priv, Repl_client_priv, Create_view_priv, Show_view_priv, Create_routine_priv, Alter_routine_priv, Create_user_priv, Event_priv, Trigger_priv, Create_tablespace_priv, ssl_type, ssl_cipher, x509_issuer, x509_subject, max_questions, max_updates, max_connections, max_user_connections, plugin, authentication_string, password_expired, password_last_changed, password_lifetime, account_locked )
  values
  ('localhost', 'niabie', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', '', '', '', '', 0, 0, 0, 0, 'mysql_native_password', password(''), 'N', '2019-11-07 15:17:00', null, 'N');
flush privileges;# 更新

用户具有创建数据库等的权限,authentication_string不需要则填null

create

参考

create user lynx;
update user set Host='localhost', authentication_string=password('1111') where User='lynx';
flush privileges;# 更新
grant all on database.table to 'lynx'@'localhost';# 分配database的table权限给用户
show grants for lynx@localhost;# 显示用户权限

用户没有创建数据库的权限

修改数据库位置

• 查看数据库存放位置

show variables like '%dir%';
-- 或
select @@datadir

修改数据库存放位置

参考:digitalocean

1. 暂停mysql服务

sudo systemctl stop mysql
sudo systemctl status mysql

2. 转移目录

sudo rsync -av /var/lib/mysql {dir}
sudo mv /var/lib/mysql /var/lib/mysql.bak

3. 修改mysql配置

/etc/mysql/mysql.conf.d/mysqld.cnf

[mysqld]
datadir = {dir}/mysql/

4. 修改apparmor访问rules

/etc/apparmor.d/tunables/alias

alias /var/lib/mysql -> {dir}/mysql/,

sudo systemctl restart apparmor

5. 创建mysql所需的的最小文件结构

sudo mkdir /var/lib/mysql/mysql -p

6. 重启mysql

sudo systemctl start mysql
sudo systemctl status mysql
# sudo rm -Rf /var/lib/mysql.bak
# sudo systemctl restart mysql

其他

• 创建数据库并选择

create database homework3;
show databases;
use homework3;
show tables;

• 查看版本等

select version();
select now();
select user();

• 查看端口

show variables like 'port';

安装

sudo pip3 install scrapy

报错

pyopenssl 19.1.0 has requirement cryptography>=2.8, but you'll have cryptography 2.3 which is incompatible.

创建项目

scrapy startproject project_name

将会创建一个project_name文件夹,文件夹结构

project_name/-+-project_name/-+-spiders/---__init__.py
              |               |
              |               +-items.py
              |               |
              |               +-middlewares.py
              |               |
              |               +-pipelines.py
              |               |
              |               +-settings.py
              |               |
              |               `-__init__.py
              |
              `-scrapy.cfg

构建item模型

project_name/items.py

制作爬虫

scrapy genspider fuck "itcast.cn" # 示例网站

将在project_name/spiders/下创建fuck.py并初始化代码框架

重置桌面配置

dconf reset -f /org/gnome/

sudo

在sudo模式下使用用户的.vimrc

sudo -E vim file

当前目录,只保留file

• xargs

find /当前目录 -type f ! -name "file"|xargs rm -f

• find自带命令

find /当前目录 -type f ! -name "file" -exec rm -f {} \

递归删除

除.java

find ./ -name "*.java" | xargs rm -rfv

批量修改文件名

rename 's/原内容/改后内容/' *

打包

tar czvf FileName.tar DirName

• 计算目录大小

du -h --max-depth=1 .

• 合并文件夹

cp -frp new/* old/

-f强制覆盖,-r递归,-p保持新文件的属性不变

dpkg

• 查找已装软件?

dpkg -l|grep filename

• 卸载软件

dpkg -r filename

或?

dpkg -P filename

• 彻底删除标识为rc的配置信息

rc:软件已卸载,配置文件还在

dpkg -l | grep ^rc | cut -d' ' -f3 | sudo xargs dpkg --purge

目录分析(du)

示例

du -d1 -b -a .
du -d0 -m .

cat

• 输出固定行数

cat $file | head -n +6
``` 

[详细](https://blog.csdn.net/NFR413/article/details/78966085)

## curl

- 下载`$file`

```bash
curl -O $pathtofile

• 命令行中输出表达式的值

echo $[1 == 2]

Linux的算术运算

进程

• 切换到后台

<ctrl+z>

• 查看后台进程

jobs

• 使第N个进程在前台/后台运行

fg %N
bg %N

不加N默认对最后一个进程操作

ctags

• vim设定源

固定

set tags=$path

先当前目录,后向上找

set tags=tags;
set autochdir

ln链接

• 文件夹软链接

ln -s $exists $new

wc统计行数

find -maxdepth 10 -type f | xargs wc -l
wc -l `find -name '*.*'`

更改用户/权限

sudo chmod -R 777 *
sudo chown -R user * # sudo chown -R user:usergroup *

parallel并行(TODO)

参考

文件

不同版本文件对比

• 同一文件

git diff branch1 branch2 file

• 不同文件

git diff branch1:(绝对路径) branch2:(绝对路径)

从版本中删除文件(?)

git rm 文件 --cached

博客园
stackoverflow

git filter-branch --tree-filter 'rm -f {file}' HEAD

不跟踪已删除的文件

git add --update

显示新增文件

• 不需要git add

git ls-files --others --exclude-standard
git status --porcelain

• 在git add 之后

git diff --name-only --diff-filter=A --cached # All new files in the index  
git diff --name-only --diff-filter=A          # All files that are not staged  
git diff --name-only --diff-filter=A HEAD     # All new files not yet committed

更新单个文件

git checkout origin/master path_to_file

恢复单个文件到历史版本

git checkout -- $filepath
git reset $commit_id $pathtofile

查看历史版本的文件

git show {log}:{filename}

版本控制

回复到上一版本

git reset --hard HEAD
git reset --hard HEAD^
git reset --hard HEAD^^
git reset --hard HEAD~100

回复到新版本

廖雪峰

删除commit

TODO

分支

删除本地分支

git branch -d branchname

重命名本地分支

git branch -m branchname1 branchname2

删除远程分支

git push origin --delete branchname

删除master需要在github上修改默认分支后才能删除

仓库

查看远程仓库

git remote -v

增加仓库

git remote add 名字 地址

删除仓库

git remote rm 名字

添加.gitignore后重新跟踪

git rm -r --cached .
git add .

强制覆盖本地

git fetch
git reset --hard origin/master
git pull

修改remote

git remote set-url origin [url]

半导体物理基础

半导体材料

• 导体:$\rho < 10^{-4}\Omega\cdot cm$
• 绝缘体:$\rho > 10^{9}\Omega\cdot cm$

本征半导体,空穴及其导电作用

• 载流子:可以自由移动的带电粒子

• 电导率:与材料单位体积中所含载流子数有关,载流子浓度越高,电导率越高

• 本征激发:当半导体受热或光照激发时,某些电子从外界获得足够的能量而挣脱共价键的束缚,离开原子成为自由电子,同时在共价键中留下相同数量的空穴

• 空穴:共价键中的空位

• 电子空穴对:由热激发而产生的自由电子和空穴对

半导体的重要特性

• 在本征半导体中自由电子和空穴总是成对产生,其自由电子-空穴对随温度的增高而显著增加
• 空穴的导电作用

本证半导体的缺点:载流子少,导电性差,温度稳定性差

杂质半导体

参入杂质的本征半导体称为杂质半导体

P型半导体

• 参入3价杂质元素(如硼,镓和铟)的半导体

• 空穴(p)是多数载流子(多子),它主要由掺杂形成;自由电子(n)是少数载流子(少子),由热激发形成

• 空穴很容易俘获电子,使杂质原子成为负离子.3价杂质因而也称为受主杂质($N_A$)
  $$ N_A + n = p $$

N型半导体

• 参入5价杂质元素(如磷)的半导体

• 自由电子(n)是多数载流子,主要由杂质原子提供;空穴(p)是少数载流子,由热激发形成

• 提供自由电子的5价杂质原子因带正电荷而成为正离子.因此5价杂质原子也称为施主杂质($N_D$)
  $$ n = p + N_D $$

载流子的漂移与扩散

• 漂移电流:在电场作用下,载流子(自由电子/空穴)在电场作用下的漂移运动形成的电流

• 扩散电流:因浓度差,载流子从浓度高处向浓度低处扩散运动,形成的电流

PN结

对于P型半导体和N型半导体的结合面,离子薄层形成的空间电荷区称为PN结

在空间电荷区,由于缺少多子,所以也称耗尽层

PN结的单向导电性

• 当外加电压使PN结中P区的电位高于N区的电位,称为加正向电压,简称正偏;反之称为加反向电压,简称反偏

• PN结加正向电压时,呈现低电阻,具有较大的正向扩散电流

• PN结加反向电压时,呈现高电阻,具有很小的反向漂移电流

• PN结$V$-$I$特性表达式:$i_D=I_S(e^{v_D/V_r}-1)$
  $I_S$:反向饱和电流
  $V_T$:温度的电压当量.在常温下$V_T=\dfrac{kT}{q}=26mV$

PN结的反向击穿

• 电击穿(可逆)
  • 雪崩击穿:有正温度系数
  • 齐纳击穿:有负温度系数
• 热击穿(不可逆)

PN结的电容效应

• 扩散电容$C_D$:TODO

• 势垒电容$C_B$:TODO

二极管

二极管的$V$-$I$特性

二极管的伏安特性曲线可表示:$i_D=I_S(e^{v_D/V_T}-1)$

• 硅二极管的死区电压$V_{th}=0.5-0.8V$左右
• 锗二极管的死区电压$V_{th}=0.1-0.3V$左右

二极管的主要参数

• 最大整流电流$I_F$

• 反向击穿电压$V_{BR}$和最大反向工作电压$V_{RM}$:实际工作时,最大反向工作电压一般只按反向击穿电压的一半计算

• 反向电流$I_R$在室温下,最大反向工作电压下的反向电流值.硅二极管的反向电流一般在$nA$级;锗二极管在$\mu A$级

• 极间电容$C_d=C_B+C_D$(TODO)

• 反向恢复时间$T_{RR}$

• 正向压降$V_F$:二极管能够导通的正向最低电压.硅二极管约$0.6-0.8V$,锗二极管约$0.2-0.3V$

二极管电路的简化模型分析方法

理想模型

恒压降模型

管压降恒定:

• 硅管$0.7V$
• 锗管$0.3V$

折线模型

硅管:

• 门槛电压$V_{th}=0.5V$
• 导通电流为1$mA$时,管压降为$0.7V$
• $r_D=200\Omega$

小信号模型

常温下微变电阻$(300K)r_d=\dfrac{V_T}{I_D}=\dfrac{26(mV)}{I_D}$

模型分析法应用举例

限幅电路

开关电路

低电压稳压电路

小信号工作情况分析

TODO

齐纳二极管

半导体三极管

三极管的结构和符号

• 集电极$c$ollector,集电区,集电结
• 基极$b$ase,基区
• 发射极$e$mitter,发射区,发射结

放大状态下三极管的工作原理

实现放大的外部条件:发射结正偏,集电结反偏

实现放大的内部条件:发射区杂质浓度远大于基区杂质浓度,且基区很薄

共基极直流放大系数$\bar{\alpha}=\dfrac{\text{传输到集电极的电流}}{\text{发射极注入电流}}=\dfrac{I_{C}-I_{CBO}}{I_{E}}\approx\dfrac{I_C}{I_E}$

共射极直流放大系数$\bar{\beta}=\dfrac{\bar{\alpha}}{1-\bar{\alpha}}$

反向饱和电流/穿透电流$I_{CEO}=(1+\bar{\beta})I_{CBO}$

当$I_C >> I_{CEO}$时,忽略$I_{CEO}$,则$\bar{\beta}\approx\dfrac{I_C}{I_B}$

三极管的三种组态

• 共发射极接法:CE
• 共基极接法:CB
• 共集电极接法:CC

BJT的$I$-$V$特性曲线

输入特性曲线

$$i_B=f(v_{BE})|_{v_{CE}=const}$$

• 死区
• 非线性区
• 近似线性区

输出特性曲线

$$i_C=f(v_{CE})|_{i_B=const}$$

• 饱和区:$i_C$明显受$v_{CE}$控制的区域,该区域内,一般$v_{CE} < 0.7V$(硅管).此时,发射结正偏,集电结正偏或反偏电压很小

• 截止区:$i_C$接近0的区域,相当$i_B=0$的曲线的下方.此时,$v_{BE}$小于死区电压

• 放大区:$i_C$平行于$v_{CE}$轴的区域,曲线基本平行等距.此时,发射结正偏,集电结反偏

• Early效应
  输出特性比较平坦的部分随着$V_{CE}$的增加略向上倾斜

BJT的主要参数

1. 电流放大系数

   • 共发射极直流电流放大系数$\bar{\beta}=\dfrac{I_C-I_{CEO}}{I_B}\approx\dfrac{I_C}{I_B}|_{v_{CE}=const}$

   • 共发射极交流电流放大系数$\beta=\dfrac{\Delta I_C}{\Delta I_B}|_{v_{CE}=const}$

   • 共基极直流电流放大系数$\bar{\alpha}=\dfrac{I_C-I_{CBO}}{I_E}\approx\dfrac{I_C}{I_E}$

   • 共基极交流电流放大系数$\alpha=\dfrac{\Delta I_C}{\Delta I_E}|_{v_{CB}=const}$
     当$I_{CBO}$和$I_{CEO}$很小时,$\bar{\alpha}\approx\alpha,\bar{\beta}\approx\beta$,可以不加区分

2. 极间反向电流

3. 极限参数

   • 集电极最大允许电流$I_{CM}$
   • 集电极最大允许功率损耗$P_{CM}=I_CV_{CE}$
   • 反向击穿电压
   • $V_{(BR)CBO}$:发射极开路时的集电结反向击穿电压
   • $V_{(BR)EBO}$:集电极开路时的发射结的反向击穿电压
   • $V_{(BR)CEO}$:基极开路时的集电极和发射极间的击穿电压

温度对BJT参数及特性的影响

温度对BJT参数的影响

温度对BJT特性曲线的影响

三极管放大电路

共射极放大电路的工作原理

静态

静态工作点(TODO)

动态

BJT放大电路的图解分析法

静态工作点的图解分析

• 负载线
  • 输入:$V_{BE}=V_{BB}-i_BR_b$
  • 输出:$V_{CE}=V_{CC}-i_CR_c$

动态工作情况的图解分析

静态工作点对波形失真的影响

放大电路的动态范围

温度对工作点的影响(定性)

1. 温度变化对$I_{CBO}$的影响

$I_{CBO}=I_{CBO(T_0=25^{\circ}C)}\cdot e^{k(T-T_0)}$

温度$T$上升$\to$输出特性曲线上移

2. 温度变化对输入特性曲线的影响

$V_{BE}=V_{BE(T_0=25^{\circ}C)}-(T-T_0)\times2.2\times10^{-3}V$

温度$T$上升$\to$输入特性曲线左移

3. 温度变化对$\beta$的影响

温度每升高1$^{\circ}C,\beta$要增加$0.5\%\sim1.0\%$

温度$T$上升$\to$输出特性曲线族间距增大

基极分压式射极偏置电路

• 工作原理

TODO

场效应管

场效应管的分类

1. MOSFET(IGFET)绝缘栅型
   1. 增强型
      • N沟道
      • P沟道
   2. 耗尽型
      • N沟道
      • P沟道
2. JFET结型(耗尽型)
   1. N沟道
   2. P沟道

耗尽型:场效应管没有加偏置电压时,就有导电沟道存在
增强型:场效应管没有加偏置电压时,没有导电沟道

结构

• 源极$s$ource
• 栅极$g$ate
• 漏极$d$rain

特性曲线

输出特性曲线

1. 截止区
2. 可变电阻区(非饱和区)
3. 饱和区(恒流区,放大区):必须让FET工作在饱和区(放大区)才有放大作用

• N沟道:$v_{GS},v_{DS}\uparrow,i_D\uparrow$
• P沟道:$v_{GS},v_{DS}\downarrow,|i_D|\uparrow$

转移特性曲线

• N沟道:$v_{GS},i_D\uparrow$
• P沟道:$v_{GS},|i_D|\uparrow$

主要参数

1. $V_T$:(增强型参数)开启电压
   $V_{TN}$:N沟道增强型开启电压
2. $V_P$:(耗尽型/结型参数)夹断电压
3. 饱和漏电流$I_{DSS}$(耗尽型):在$V_{GS}=0$的情况下,当$V_{DS} > V_P$时的漏极电流称为饱和漏极电流.通常令$|V_{DS}|=10V,V_{GS}=0V$时测出的$i_D$就是$I_{DSS}$.在转移特性上,就是$V_{GS}=0$时的漏极电流
4. 直流输入电阻$R_{GS}$:在漏源之间短路的条件下,漏源之间加一定电压时的栅源直流电阻就是直流输入电阻

N沟道增强型MOSFET

工作原理

1. $V_{GS}$对沟道的控制作用

   • 当$V_{GS}\le0$时
     无导电沟道.$d,s$间加电压时,也无电流产生
   • 当$0 < V_{GS} < V_{TN}$时
     产生电场,但未形成导电沟道(反型层),$d,s$间加电压后,没有电流产生
   • 当$V_{GS} > V_{TN}$时
     在电场作用下产生导电沟道,$d,s$间加电压后,将有电流产生.$V_{GS}$越大,导电沟道越厚

2. $V_{DS}$对沟道的控制作用
   当$V_{GS}$一定($V_{GS} > V_{TN}$)时

   • $V_{DS}$增加$\to I_D$增加$\to$沟道电位梯度增加$\to$靠近漏极$d$处的电位升高$\to(d)$电场强度减小$\to(d)$沟道变薄
   • 当$V_{DS}$增加到使$V_{GD}=V_{TN}$时,在紧靠漏极处出现预夹断
   • 预夹断后,$V_{DS}$增加$\to$夹断区延长$\to$沟道电阻增加$\to I_D$基本不变

3. $V_{DS}$和$V_{GS}$同时作用时
   $V_{DS}$一定,$V_{GS}$变化时,给定一个$V_{GS}$,就有一条不同的$i_D$-$V_{DS}$曲线

N沟道耗尽型MOSFET

P沟道MOSFET

沟道长度调制等几种效应

1. 沟道长度调制效应
   饱和区的曲线并不是平坦的

2. 衬底调制效应(体效应)

   • 衬底未与源极并接时,衬底与源极间的偏压$V_{BS}$将影响实际的开启/夹断电压和转移特性
     • 阈值电压升高
     • TODO
   • 为保证导电沟道与衬底之间的PN结反偏,要求
     • N沟道:$V_{BS}\le0$
     • P沟道:$V_{BS}\ge0$

3. 击穿效应

   1. 漏衬击穿:外加的漏源电压过高,将导致漏极到衬底的PN结击穿
   2. 栅极击穿:栅极电压过高,绝缘层击穿
      • 通常在MOS管的栅源间接入双向稳压管,限制栅极电压

JFET的结构和工作原理

工作原理

1. $V_{GS}$对沟道的控制作用
   当$V_{GS} < 0$时:PN结反偏$\to$耗尽层加厚$\to$沟道变窄
   $V_{GS}$继续减小,沟道继续变窄
   当沟道夹断时,对应的栅源电压$V_{GS}$称为夹断电压$V_P$或$V_{GS(off)}$
   对于N沟道的JFET,$V_P < 0$

2. $V_{DS}$对沟道的控制作用
   当$V_{GS}=0$时:$V_{DS}$增加$\to g,d$间PN结的反向电压增加,使靠近漏极处的耗尽层加宽,沟道变窄,从上至下呈楔形分布
   当$V_{DS}$增加到使$V_{GD}=V_P$时,在紧靠漏极处出现预夹断.此时$V_{DS}$增加$\to$夹断区延长$\to$沟道电阻增加$\to i_D$基本不变

3. $V_{GS}$和$V_{DS}$同时作用时
   当$V_P < V_{GS} < 0$时,导电沟道更容易夹断,对于同样的$V_{DS},i_D$的值比$V_{GS}=0$时的值要小
   在预夹断处:$V_{GD}=V_{GS}-V_{DS}=V_P$

FET和BJT重要特性的比较

1. 对应关系

2. 输入对输出的控制

   • BJT:基-射极间电压$V_{BE}$控制集电极电流$i_C$
   • MOS管:栅源电压$V_{GS}$控制漏极$i_D$
   • 在放大区域内,MOS管的$i_D$与$V_{GS}$之间是平方关系,而BJT的$i_C$与$V_{BE}$之间是指数关系.所以通常BJT的跨导要大于MOS管的跨导
   • 因MOS管的栅极电流$i_G=0$而BJT的基极电流$i_B\not=0$,且电压$V_{BE}$首先影响$i_B$(或$i_E$)然后通过$i_B$()实现对$i_E$()的控制,故常将BJT称为电流控制器件,MOS管称为电压控制器件

3. 跨导:TODO

4. 输出电阻:TODO

5. MOS管的$K_n$与BJT的$\beta$或$\alpha$:TODO

场效应管放大电路

基本共源极放大电路的组成

TODO

基本共源放大电路的工作原理

TODO

用图解方法确定静态工作点$Q$

TODO

放大电路模型

信号

• 信号:信息的载体
• 电信号:用电量来描述信息的变化

模拟信号和数字信号

• 时间连续,数值连续:模拟信号
• 事件离散,数值连续:AD(analog,digital)转换新号
• 时间连续,数值离散:DA转换新号
• 事件离散,数值离散:数字信号

放大电路

放大电路的符号及模拟信号放大

放大电路模型

电压放大模型

$A_v=\dfrac{v_o}{v_i}=A_{vo}\dfrac{R_L}{R_o+R_L}$

1. 负载大小会影响增益的大小
2. 减小负载的影响
3. 减小输入回路对信号的衰减影响

电流放大模型

$A_i=\dfrac{i_o}{i_i}=A_{is}\dfrac{R_o}{R_o+R_L}$

1. 减小负载的影响
2. 减小对信号源的衰减

互阻放大模型

TODO

互导放大模型

TODO

隔离放大电路模型

TODO

放大电路的主要性能指标

输入电阻

$R_i=\dfrac{v_i}{i_i}$

决定了放大电路从信号源吸取信号幅值的大小

• 电压放大和互导放大->输入信号为电压-> $R_i$大
• 电流放大和互阻放大->输入信号为电流-> $R_i$小

输出电阻

$R_o=\dfrac{v_t}{i_t}|_{v_s=0,R_L=\infty}$

决定了放大电路带负载的能力

• 电压放大和互阻放大->输出信号为电压-> $R_o$小
• 电流放大和互导放大->输出信号为电流-> $R_o$大

增益

• 电压增益$A_v=\dfrac{v_o}{v_i}$
• 电流增益$A_i=\dfrac{i_o}{i_i}$
• 互阻增益$A_r=\dfrac{v_o}{i_i}$
• 互导增益$A_g=\dfrac{i_o}{v_i}$

其中$A_v,A_i$常用分贝$(dB)$表示

• 电压增益$=20\lg|A_v|$
• 电流增益$=20\lg|A_i|$
• 功率增益$=10\lg A_p$

频率响应(基本概念)及带宽(识图)

• 频率响应:在输入正弦信号下,输出随输入信号频率连续变化的稳态响应

• 频率失真

  • 幅度失真:对不同频率信号增益不同产生的失真
  • 相位失真:对不同频率的信号相移不同产生的失真

非线性失真

由元件非线性特性引起的失真
在频谱图上表现为新的频率分量产生

• 频谱图

运算放大器

• 符号
• 电路模型

集成电路运算放大器

• 当$A_{V_O}(v_P-v_N)\ge V_+$时,$v_O=V_+$
• 当$A_{V_O}(v_P-v_N)\le V_-$时,$v_O=V_-$
• 电压传输特性$v_O=f(V_P-V_N)$

运算放大器的电压传输特性

设$v_p > v_N$

1. 线性区

$V_- < A_{V_O}(v_p-v_N) < V_+$
$v_O=A_{V_O}(v_p-v_N)$

2. 饱和区
   • $A_{V_O}(v_p-v_N)\ge V_+$
     $v_O=+V_{om}=V_+$
   • $A_{V_O}(v_p-v_N)\le V_-$
     $v_O=-V_{om}=V_-$

理想运算放大器

理想运算放大器特点

• 开环差模电压增益$A_{V_O}=\infty$
• 差模输入电阻$r_{id}=\infty$
• 输出电阻$r_O=0$

反馈(概念)

讲系统的输出返回到输入端并以某种方式改变输入,进而影响系统功能的过程

• 正反馈
• 负反馈

反馈的电压增益

深度负反馈

• $1+A_{V_O}F_V >> 1$
• 闭环增益$A\approx\dfrac{1}{F}$(反馈系数)

$A_V=\dfrac{v_o}{v_i}\approx\dfrac{1}{F_V}=1+\dfrac{R_2}{R_1}$

虚短和虚断

$A_V=\dfrac{v_o}{v_i}\approx\dfrac{1}{F_V}=\dfrac{v_o}{v_f}=\dfrac{v_o}{v_N} \Rightarrow v_i\approx v_f$或$v_P\approx v_N$

• 虚短:在深度负反馈作用下,$v_N$自动跟踪$v_P$,净输入电压$(v_P-v_N)\to0$,即$P$端与$N$端相当于短路
• 虚断:由于$(v_P\approx v_N)$,而运放的输入电阻阻值又很高,因此流经两输入端之间的电流$i_P=i_N\approx0$

同相放大电路

1. 电压增益

根据虚短和虚断的概念

• $v_n=v_p=v_i$
• $\dfrac{v_n-0}{R_1}=\dfrac{v_o-v_n}{R_2}$
  $\to A_V=\dfrac{v_o}{v_i}=\dfrac{R_1+R_2}{R_1}=1+\dfrac{R_2}{R_1}$

2. 输入电阻

$R_i=\dfrac{v_i}{i_i}\to\infty$

3. 输出电阻

$R_O=r_O\parallel[(R_1\parallel r_i)+R_2]\to0$

同相放大电路-电压跟随器

$v_o=v_n\approx v_p=v_i$

反相放大电路

1. 电压增益

根据虚短和虚断的概念

• $v_n\approx v_p=0$(虚地)
• $\dfrac{v_i-v_n}{R_1}=\dfrac{v_n-v_O}{R_2}$
  $\to A_V=\dfrac{v_O}{v_i}=-\dfrac{R_2}{R_1}$(负号表示输出与输入反向)

2. 输入电阻

$R_i=\dfrac{v_i}{i_i}=\dfrac{v_i}{v_i/R_1}=R_1$

3. 输出电阻

$R_O=r_O\parallel R_2\to0$

求差电路

$R_4=R_1,R_2=R_3$

• 电压增益:$A_v=\dfrac{v_o}{v_{i2}-v_{i1}}$

• 输入电阻:$R_i=\dfrac{v_{i2}-v_{i1}}{i_2}$

• 输出电阻:$R_o\to0$

求和电路

$R_1=R_2=R_3$

输出再接一级反向电路

数字逻辑

数字信号

1. 模拟信号:时间和数值均连续变化的电信号,如正弦波,三角波

2. 数字信号:在时间上和数值上均是离散的信号

3. 模拟信号的数字表示:由于数字信号便与存储,分析和传输,通常将模拟信号转换为数字信号

数字信号的描述方法

1. 二值数字逻辑和逻辑电平

   • 二值数字逻辑:0,1数码
     • 二进制数:表示数量
     • 二值逻辑:表示事物状态
   • 表示方式:在电路中用低,高电平表示0,1两种逻辑状态

2. 数字波形:信号逻辑电平对时间的图形表示

   • 主要参数
     • 周期($T$):两个相邻脉冲之间的时间间隔
     • 脉冲宽度($t_w$):脉冲幅值的50%所跨越的时间
     • 占空比($Q$):脉冲宽度栈整个周期的百分比
     • 上升/下降时间($t_r/t_f$):从脉冲幅值10%到90%锁经历的时间

二值逻辑变量与基本逻辑运算

• 逻辑符号/逻辑表达式

逻辑门电路

分类

一般特性

1. 输入和输出的高,低电平

   • $V_{IL(max)}$:输入低电平的上限值
   • $V_{IH(min)}$:输入高电平的下限值
   • $V_{OL(max)}$:输出低电平的上限值
   • $V_{OH(min)}$:输出高电平的下限值

2. 噪声容限

在保证输出电平不变的条件下,输出电平允许波动的范围

负载门输入高电平时的噪声容限:$V_{NH}-$当前级门输出高电平的最小值时允许负向噪声电压的最大值
$V_{NH}=V_{OH(min)}-V_{IH(min)}$

负载门输入低电平时的噪声容限:$V_{NL}-$当前级门输出低电平的最大值时允许正向噪声电压的最大值
$V_{NL}=V_{IL(max)}-V_{OL(max)}$

3. 传输延迟时间

开关速度的参数,说明门电路在输入脉冲波形的作用下,其输出波形相对于输入波形延迟了多长的时间

4. 功耗

   • 静态功耗:电路没有状态转换时的功耗,即门电路空载时电源总电流$I_D$与电源电压$V_{DD}$的乘积
   • 动态功耗:电路在输出状态转换时的功耗
   • 对于TTL门电路,静态功耗是主要的.CMOS电路的静态功耗非常低,有动态功耗

5. 延时-功耗积
   是速度功耗综合性的指标,用符号$DP$表示
   $DP=\dfrac{t_{pLH}+t_{pHL}}{2}P_D$

6. 扇入与扇出数

   • 扇入数:取决于逻辑门的输入端的个数
   • 扇出数:在正常工作情况下,所能带同类门电路的最大数目

MOS开关及其等效电路

当$v_1 < V_T$:MOS管截止,输出高电平
当$v_1 > V_T$并且比较大:MOS管工作在可变电阻区,输出低电平

• 当输入为低电平时
  MOS管截止,相当于开关断开,输出为高电平

• 当输入为高电平时
  MOS管工作在可变电阻区,相当于开关闭合,输出为低电平

MOS管相当于一个由$V_{GS}$控制的无触点开关

CMOS反向器

CMOS逻辑门

CMOS传输门

TODO

TTL

• TTL反向器
• TTL与非门
• TTL或非门

半导体存储器(基本概念)

• RAM(随机存取存储器):在运行状态可以随时进行读或写操作.存储的数据必须有电源供应才能保存,一旦掉电,数据全部丢失

• ROM(只读存储器):在正常工作状态只能读出信息.断电后信息不会丢失

• 字长(位数)

• 字数

• 地址

• 存储容量=字数$\times$位数

• 掩摸ROM

  • 存储矩阵的每个交叉点是一个存储单元,存储单元中有期间存入1,无器件存入0
  • 出厂时已经固定,适合大量生产,便宜,非易失性

• 可变长ROM(PROM)

  • 存储单元与掩摸ROM不同
  • 熔丝由易熔合金制成,出厂时每个节点上都有,编程时讲不用的熔断.一次性编程,不能改写

• 可擦除的的可编程ROM(EPROM)

  • 存储单元与掩摸ROM不同
  • 用紫外线擦除的PROM(UVEPROM)
  • SIMOS 叠栅注入MOS管
    • 若$G_f$上充负电荷,则$G_c$处于正常逻辑高电平下不导通
    • 若$G_f$上为充负电荷,则$G_c$处于正常逻辑高电平下导通
    • 写入:雪崩注入.$D$-$S$间加高压($20-25V$),发生雪崩击穿,同时在$G_c$上加$25V,50ms$宽的正脉冲,吸引高速电子穿过$SiO_2$到达$G_f$,形成注入电荷
    • 擦除:通过照射产生电子-空穴对,提供泄放通道.紫外线照射20-30分钟,阳光下一周,荧光灯下3年

• 电可擦除的可编程ROM(E$^2$PROM)

  • 微客服UVEPROM擦除慢,操作不便的缺点,采用FLOTOX(浮栅隧道氧化层MOS管)
  • $G_f$与$D$之间有小的隧道区,$SiO_2$厚度$< 2\times10^{-8}m$
  • 当场强大到一定大小($10^7V/cm$)时,电子会穿越隧道
  • TODO

• 快闪存储器(Flash Memory)

• 静态随机存储器SRAM

  • 存储单元:6个N沟道增强型MOS管

• 动态随机存储器DRAM

  • 利用MOS管栅极电容可以存储电荷的原理

• SRAM和DRAM的区别

  • SRAM:速度快,贵

微电子学的新发展(基本概念)

• 冯诺依曼架构:用数学模型和算法来描述和模仿神经元的行为和相互关系,但计算仍然运行在传统的计算机上

• 非冯诺依曼架构:用电子器件模拟生物神经元的功能,构建新的神经计算机

• 忆阻器:$V(t)=M(q(t))I(t)$.功能如同电阻,但在关掉电源后,仍能记忆先前通过的电荷量.忆阻器的电阻值取决于多少电荷经过了这个器件:让电荷以一个方向流过,电阻会增加;让点何以相反的方向流过,电阻就会减小

  • 工作原理:一块极薄的二氧化钛($TiO_2$)被夹在两个电极中间,分成2个部分,一般是正常的二氧化钛,另一半进行了掺杂,少了几个氧原子($TiO_{2-x}$),掺杂的那一半带正电.当电流从掺杂的一边通向正常的一边时,在电场的影响下缺氧的掺杂物会往正常的一侧游移,使得掺杂的部分会占较高的比重,整体的电阻降低
  • 特点
    • 输入输出关系是非线性的
    • 输入和输出都是连续的,其存储的精度理论上是无限的
    • 无源电路元器件,方便将其应用在电路中,形成混合型电路
    • 非易失性
    • 高集成密度,高读写速度,低功耗,多值计算
  • 应用前景
    • TODO
    • 存算一体

• 石墨烯:一种由碳原子构成的单层片状结构的新材料

  • 极薄极轻,比表面积$2630m^2/g$
  • 导热率为$3000-5000W/mK$
  • 极强的力学性能
  • 优良的导电性
  • 制备方法
    • 物理方法
      • 机械剥离法
      • 液相或气相直接剥离法
    • 化学方法
      • 表面析出生长法
      • 氧化石墨还原法
      • 化学气相沉积法
      • 化学合成法
  • 应用前景
    • 低成本石墨烯电池
    • 可折叠弯曲屏
    • 石墨烯传感器
    • 石墨烯过滤器
    • 石墨烯生物器件
    • 石墨烯感光元件
    • 太阳能电池
    • 柔性微处理器
  • 由石墨烯到二维材料
    1. 结构有序
    2. 在二维平面生长
    3. 在第三维度超薄

• 自旋场效应晶体管

  • 电子的电荷与自旋:在半导体材料中有电子和空穴两种载流子,极化电子优自旋向上和向下两种载流子
  • 电子的自旋极化:TODO

• 柔性电子学

  • 概念:涵盖有机电子,塑料电子,生物电子,纳米电子,印刷电子等技术,是将有机/无机材料电子器件制作在柔性/可延性基板上的新兴电子技术.相对于传统电子,柔性电子具有更大的灵活性.
  • 应用场景:TODO,柔性显示,有机电致发光显示与照明,化学与生物传感器,柔性光伏,柔性逻辑与存储,柔性电池,可穿戴设备
  • 柔性电子器件的材料
    • 碳纳米管
    • 金属氧化物半导体薄膜
    • 金属纳米薄膜,金属纳米线
    • 有机高分子薄膜
    • 水凝胶离子导体
    • 液态金属
  • 柔性电子制造方法
    • 转移印刷
    • 喷墨印刷
    • 纤维结构形成
  • 可拉伸结构的设计:TODO

提纲

半导体三极管

• 输入特性曲线
• 输出特性曲线
  • 区域,含义
• 主要参数

三极管放大电路

• 共射极放大电路
  • 工作原理
  • 计算静态工作点
  • 负载线
  • 失真和静态工作点的关系
  • 温度对工作点的影响(定性)
  • 基极分压式射极偏置电路(认识,工作原理)

场效应管

• 不同类型的管子
  • 符号
  • 结构
  • 工作原理
  • 特性曲线
    • 输出(分区)
    • 转移
  • 几种效应
  • 主要(直流)参数

场效应管放大电路

• 基本共源极放大电路
  • 工作原理(不要求公式)
• 图解法求静态工作点
  • 负载线与输出特性曲线

放大电路模型

• 基本定义
• 符号
• 增益的定义
• 几种模型
• 性能指标
  • 输入电阻
  • 输出电阻
  • 增益
  • 频率响应和带宽:基本概念,识图
  • 非线性失真:概念,识图(不要求计算)

运算放大器

• 组成单元
• 结构框图
• 符号
• 电路模型
• 参数特点
• 理想运放
• 反馈:概念
• 深度负反馈:概念
• 虚短,虚断
• 几种电路
  • 基本形式
  • 特征

数字逻辑

• 概念
• 逻辑符号,逻辑表达式

逻辑门电路(不要求分析)

• 基本参数
• 反向器,与非门,或非门,传输门
• TTL(反向器)(认识)

1 数据库系统概述

1.1 基本概念

• 数据库系统(Database System, DBS)
  DBS的组成部分
  • 数据库
  • 数据库管理系统
  • 数据库管理员
  • 软件平台
  • 硬件平台

1.4 数据库内部结构体系

• 数据库系统的三级模式
  • 概念模式(模式)
  • 外模式(子模式,用户模式)
  • 内模式(物理模式)

2 数据模型

2.1 数据模型的基本概念

• 概念模型

  • 常用的概念模型:实体-联系(E-R)模型,面向对象模型等

• 逻辑模型

  • 常用的逻辑模型:关系模型,对象关系模型

• 物理模型:由DBMS负责实现

2.3.1 实体-联系(E-R)模型

关键字:关键字时可用于区分同一个实体集中不同实体的最小属性集合
函数对应:m

2.3.2 扩充E-R模型

扩充的实体-联系(EE-R)模型

1. IS-A联系:如果实体集$B$时实体集$A$的一个子集,且具有比实体集$A$更多的属性,则我们称实体集$A$与实体集$B$之间存在着一种特殊的IS-A联系,其中:

   • 实体集$A$被称为超(实体)集
   • 实体集$B$被称为子(实体)集
     子集$B$可以通过IS-A联系继承超集$A$中的所有属性

2. 弱实体(Weak Entity)

   • 如果一个实体$A$的存在需要依赖于其他某个实体的存在,那么实体$A$被称为弱实体

3. 属性的划分

4. 属性基数(Cardinality of Attributes)

5. Cardinality of Entity Participation in a Relationship(实体在一个联系中的参与基数)
   参与方式:(0,m)

2.3.3 面向对象模型

2.3.4 谓词模型

2.4.1 关系模型与关系模型数据库系统

关系中的基本概念

• 关系模式
• 关系数据库模式
• 元组
• 关键字(键/key)
  • 主关键字
  • 外关键字

3 关系数据库系统

3.3.0.1 关系数据结构

表结构

• 表框架(Frame)

• 元组(Tuple)

  • 在表框架中可按行(row)存放数据,其中的每一行数据被称为一个元组
  • 在一$n$元表中,一个元组由$n$个元组分量组成,其中:第$j$个元组分量就对应着表框架中的第$j$个属性($j=1,2…n$)

关系(Relation)

• 具有$n$个属性的关系称为$n$元关系
• 关系名及其所有属性的属性名构成了关系框架.设关系的名为$R$,其属性名为$A_1,A_2…A_n$,则该关系的框架是$R(A_1,A_2…A_n)$

键(Key)

在二维表中凡能唯一最小标识元组的属性集称为该表的键,或称关键字

• 候选键(Candidate Key)
• 主键(Primary key)

每一张二维表都至少存在一个键

• 外键(Foreign Key)
  • 如果表$A$中的属性集$F$时表$B$的键,则称该属性集$F$为表$A$的外键(或称外关键字)
  • 其中
    • 表$A$被称为引用表,表$B$被称为被引用表
    • 表$A$和表$B$可以是同一张二维表

3.3.0.2 关系操纵

空值处理

• 在算术表达式中出现空值,其运算结果也为空值
• 在逻辑运算表达式中出现空值,其运算结果为逻辑假

3.3.0.3 关系中的数据约束

三类数据完整性约束

• 实体完整性约束:主键中的属性不能有空值

• 参照完整性约束:外键要么取空值,要么是被引用表中当前存在的某元组上的主键值

• 用户定义的完整性:用户自己定义的属性取值约束

3.3.1 关系的表示

笛卡尔乘积

$D_1\times D_2\times…\times D_n$

• $D_1,D_2,…,D_n$是$n$个集合
• 设集合$D_i$的元素个数为$r_i(i=1,2,…,n)$,则他们的笛卡尔乘积的结果元素个数为$r_1\times r_2\times…\times r_n$

关系$R$

• $n$元关系$R$是一个$n$元有序组的集合

• 设$n$元关系$R$的属性域分别是$D_1,D_2,…,D_n$,那么这$n$个域的笛卡尔乘积也是一个$n$元有序组的集合,并且与关系$R$存在联系:$R\subseteq D_1\times D_2\times…\times D_n$

3.3.2 关系操纵的表示

相容表

投影运算

选择运算

关系的笛卡尔乘积

• 笛卡尔乘积满足交换律和结合律

• 如果关系$R$和$S$中存在相同的属性名,则必须在结果关系中对其中的一个进行换名

3.3.3 关系模型与关系代数

3.3.4 关系代数中的扩充运算

交运算

除运算

• 除运算的推导过程
  若$Head(R)=\{A_1…A_nB_1…B_n\},Head(S)=\{B_1…B_m\}$
  $R\div S=\pi_{A_1…A_n}(R)-\pi_{A_1…A_n}((\pi_{A_1…A_n}(R)\times S)-R)$
  1. $T_{\max}=\pi_{A_1…A_n}(R)$
  2. $R_{\max}=T_{\max}\times S$
  3. $T_1=R_{\max}-R$
  4. $T_2=\pi_{A_1…A_n}(T_1)$
  5. $R\div S=T_{\max}-T_2$

join运算

• 又称$\theta$-联接运算,可以将关系$R$和关系$S$根据join条件$F$合并为一个关系

• 联接条件$F$的构造方式

• join运算的推导公式
  $R\underset{F}{\bowtie}S=\sigma_F(R\times S)$

• 联接运算与笛卡尔乘积运算的关系

natural join运算

• 功能:根据两个关系中的同名属性进行等值联接

• 运算结果

  • 结果关系中的元组

• natural join运算的推导公式

A 关系演算

A.1 一阶谓词演算

一阶谓词演算中的基本概念

A.1.3 谓词

A.1.4 指派

A.2 关系的表示

关系演算系统

• 元组关系演算

• 域关系演算

A.3 关系操纵的表示

• 设$R$和$S$时两个模式相同的关系表,他们对应的谓词分别为$R(t)$和$S(t)$,则

  1. $R\cup S=\{t|R(t)\vee S(t)\}$
  2. $R-S=\{t|R(t)\wedge\lnot S(t)\}$
  3. $\sigma_F(R)=\{t|R(t)\wedge F\}$
  4. $\pi_{A_{i_1},A_{i_2},…,A_{i_k}}(R)=$TODO

• 设有$m$元的关系$R$和$n$元的关系$S$,他们对应的谓词分别为$R(u)$和$S(v)$,则
  $R\times S=$TODO

关系演算表达式

• 关系演算表达式$\{t|\varphi(t)\}$表示由公式$\varphi(t)$的所有成真指派所构成的集合
• 可将$\{t|\varphi(t)\}$简写为$\varphi(t)$

关系演算的原子公式

关系演算公式(简称为公式)

A.4 关系演算的例子

关系的联结

1. 可以通过相关谓词的逻辑与运算实现两个关系的笛卡尔乘积
   $R(p)\wedge S(q)$
2. 通过选择条件$F$实现两个关系的$\theta$-联结
   $R(p)\wedge S(q)\wedge F$
3. 可以通过两个谓词中的公共变元(同名变元)实现两个关系的自然联结
   $R(x,y,z)\wedge S(y,u,v)$

• 自联结:谓词名不变,对部分变元进行重命名,从而实现关系的自联结(同名变元取值相等)

元组插入,删除与修改操作

• 删除:$S(sno, sn, sd, sa)\wedge\lnot S(‘S_1’, sn, sd, sa)$

• 插入:$S(t)\vee R(t)$

• 修改:
  $R(sno, sn, sd, sa)=\exists x(S(sno, sn, sd, x)\wedge sno=S_7\wedge sa=29)$
  $(S(sno, sn, sd, sa)\wedge sno\not=S_7)\vee R(sno, sn, sd, sa))$

A.5 关系演算的安全限制

无限关系

无穷验证

B 关系数据库语言SQL

B.2 SQL数据定义功能

基表创建

B.3 SQL数据操纵功能

B.3.1 SQL的基本查询功能

B.3.1.2 常用谓词

like谓词的使用方法

column [ NOT ] like val1 [ escape val2 ]

• 模板(pattern):val1

  • _:可以匹配任意一个字符
  • %:可以匹配任意一个字符串(包括空字符串)

• 转移指示字符:val2

  • 紧跟在val2之后的_或%不再是通配符,而是其自身

B.3.1.5 自连接

B.3.1.6 结果排序

order by <列名> [ asc | desc ] {, ...}

• 升序asc,降序desc,默认升序

B.3.2 分层结构查询与集合谓词使用

where子句中的集合谓词

• in谓词:标量与集合量之间的属于比较

expr [ not ] in ( subquery )

• 限定比较谓词:标量与集合中元素之间的量化比较

expr 运算符 some|any|all ( subquery )

• exists谓词:是否为空集的判断谓词

[ not ] exists ( subquery )

B.3.3 select语句间的运算

• union [all]
• intersect [all]
• except [all]

不加all只选取不同的值

B.3.4 SQL计算,统计,分类的功能

B.3.4.1 统计功能

• count统计:

  • count(*):返回集合中的元组个数
  • count(colname):返回在colname属性上取值非空的元组个数
  • count(distinct colname):返回colname取值非空且互不相同的元组个数

• sum,avg,max,min统计

• null在统计函数中的处理:TODO

B.3.4.3 分类功能

• 分类统计查询

  • 分组查询子句

    group by colname { , colname ...}

  根据属性colname的取值的不同,将满足where条件的元组划分为不同的集合

• 分组选择子句:having group_condition

B.3.5 select语句使用的一般规则

B.4 SQL的更新功能

• 元组删除

delete from table_name
[ where search_condition ];

• 元组插入

insert into table_name [ ( colname {, colname ... } ) ]
values ( expr | null {, expr | null ...} ) | subquery;

• 元组修改

update table_name
set colname = expr | null | subquery, ...
[ where search_condition ];

B.5 视图

B.5.2 视图的删除

• 在执行视图的删除操作时,将连带删除定义在该视图上的其他视图

B.5.3 视图上的操作

• 对视图可以作查询操作

  • 视图上的查询操作将首先被改写为基表上的查询操作,然后才能得到执行

• 一般不允许执行视图上的更新操作,只有在特殊情况下才可以进行

• 可更新视图

4 数据库的安全性与完整性保护

4.1 数据库的安全性

4.1.2 数据库安全的基本概念与内容

• 客体:数据库中的数据及其载体
• 主体:数据库中数据的访问者

4.1.4 SQL对数据库安全的支持

• 操作对象

  • 表,视图
  • 属性
  • 域(type),udt(用户定义数据类型)
  • 存储过程/函数,触发器

• 授权语句
  grant <操作权限列表> on <操作对象> to <用户名列表> [ with grant option ]

• 回收语句
  revoke <操作权限列表> on <操作对象> from <用户名列表> [ restrict | cascade ]

  • cascade:连锁回收
  • restrict:在不存在连锁回收问题时才能回收权限,否则拒绝回收

4.2 数据库的完整性

TODO

5 事务处理,并发控制与故障恢复技术

5.1 事务处理

5.1.1 事务

• 事务
  一个事务是指由一条SQL语句或者一组SQL语句所构成的一个执行过程,并具有ACID四个特性
  由每个用户所执行的一个不能被打断的对数据库的操作序列被称为事务

5.1.2 事务的性质

1. 原子性(Atomicity)

2. 一致性(Consistency)
   数据库的一致的状态可以理解为数据库中所有数据的正确性,他要求数据库中的数据必须满足

   • 在数据库中显式定义的各种完整性约束
   • 用户心目中的隐式数据约束

5.1.4 有关事务的语句

3. 隔离性(Isolation)
   一个事物的执行与并发执行的其他事务之间是相互独立的,互不干扰,这被称为事务执行的隔离性

4. 持久性(Durability)

• 设置事务的隔离级别
  • readuncommitted:未提交读
  • readcommitted:提交读
  • readrepeatable:可重复读
  • serializable:可序列化(可串行化)

5.1.5 事务的组成

1. 事务控制操作

   • 事务的开始:start T
   • 提交事务:commit T
   • 回退(放弃)事务:abort T

2. 数据访问操作

   • input(A):将数据对象A的值从磁盘中读入内存缓冲区
   • output(A):将内存缓冲区中数据对象A的至写入磁盘
   • read(A, t):将内存缓冲区中数据对象A的值读入内存变量t

     在一个read操作中,有可能隐含着一个input操作

   • write(A, t):将内存变量t的值写入内存缓冲区中数据对象A

5.2 并发控制技术

5.2.1 事务的并发执行

• 多个事务的执行方式

  • 串行执行
    • 以事务为单位,多个事务依次顺序执行
  • 并发执行
  • 并发执行的可串行化
    • 如果一组事务并发执行的结果等价于他们之间的某种串行执行的结果,则称其为可串行化调度

• 并发控制的目标:实现并发事务的可串行化调度

• 调度:一个或多个事务中的数据库访问操作,按照这些操作在DBMS(database management system)被执行的时间先后,排序所形成的一个操作序列
  给定一组并发事务$T_1,T_2…T_k$,他们之间的调度$H$必须满足

  1. 必须包括所有事物的所有操作,包括每一个事务的结束命令(commit/abort)
  2. 单个事物内部的操作顺序必须保持不变

• 串行调度

• 可串行化调度

• 事务及调度的表示方法

  • 事务用符号$T_1,T_2…$表示
  • $r_i(X)$表示事务$T_i$读数据库对象$X$
  • $w_i(X)$表示事务$T_i$写数据库对象$X$

• 冲突可串行化

  • 冲突(conflict):指调度中的一对相邻操作(op1; op2),他们满足:如果交换它们两者的执行顺序,那么涉及的事务中至少有一个的行为会改变
  • 冲突的判断办法
    • 同一事务的任意两个相邻的操作都是冲突
    • 不同事物对统一数据对象的写/读-写冲突
  • 冲突等价:如果通过一系列相邻操作的非冲突交换能够将一个调度转换为另一个调度,称这两个调度是冲突等价的
  • 冲突可串行化:如果一个调度$S$冲突等价于这一组事务之间的一个串行调度,称$S$时冲突可串行化的
    • 冲突可串行化调度必定是一个可串行化调度
    • 一个可串行化调度不一定是冲突可串行化的

• 冲突可串行化的判断:优先图

• 视图等价

  • 一个冲突可串行化调度一定是视图可串行化调度

• 三种数据不一致现象

  • 丢失修改(lost updata)
    • 一个事务的修改结果破坏了另一个事务的修改结果
    • 对多个事务并发修改同一个数据对象的情况未加控制
  • 脏读(dirty read)
    • 读到了错误的数据
    • 一个事务读取了另一个事务未提交的修改结果
  • 不可重复读(unrepeatable read)
    • 在一个事务的执行过程中,前后两次读同一个数据对象所获得的值出现了不一致
    • 在两次读操作之间插入了另一个事务的写操作

5.2.2 封锁

• 排它锁(X锁)

• 共享锁(S锁)

• 锁相容矩阵

• 锁的申请与释放

5.2.3 封锁协议

• 一级封锁协议
  事务$T$在写数据对象$A$之前,必须先申请并获得$A$上的X锁,并维持到事务$T$的执行结束(包括commit与rollback)才释放加在$A$上的锁
  防止丢失修改

• 二级封锁协议
  事务$T$在读数据对象$A$之前,必须先申请并获得$A$上的S锁,在读操作完成后可以释放$A$上的S锁
  防止丢失修改,脏读

• 三级封锁协议
  事务$T$在读数据对象$A$之前,必须先申请并获得$A$上的S锁,并维持到事务$T$的执行结束才释放被加在$A$上的S锁
  防止丢失修改,脏读,不可重复读

5.2.4 两阶段封锁协议

以事务为单位来规定封锁的使用原则:对一个事务在执行过程中需要调用的所有锁申请和锁释放的动作顺序进行了约定

根据锁的申请与释放操作的调用时间,可以将一个事务的执行过程划分为两个阶段

• 第一个阶段:申请并获得锁
• 第二个阶段:释放持有的锁

在一个事务$T$中,如果所有的封锁请求都先于所有的解锁请求,则该事务被称为两阶段封锁事务,简称2PL事务(或者说采用两阶段封锁协议的事务)

假设系统采用X锁和S锁,有关封锁的申请与释放操作表示如下:

• $sl_i(A)$:事务$T_i$申请数据对象$A$上的一个S锁

• $xl_i(A)$:事务$T_i$申请数据对象$A$上的一个X锁

• $u_i(A)$:事务$T_i$释放自己在数据对象$A$上所持有的锁

• 封锁的使用规定:在每一个事务$T_i$中

  1. 采用如下的封锁协议
     • $r_i(A)$之前必须有$sl_i(A)$或$xl_i(A)$,而且在两者之间没有$u_i(A)$
     • $w_i(A)$之前必须有$xl_i(A)$,而且在两者之间没有$u_i(A)$
     • 每一个$sl_i(A)$或$xl_i(A)$之后必须有一个$u_i(A)$
  2. 必须遵循两阶段封锁协议
  3. 保证事务调度的合法性
     • 如果$xl_i(A)$出现在调度中,那么后面不能再有$sl_i(A)$或$xl_j(A)$,除非中间插入了$u_i(A)$
     • 如果$sl_i(A)$出现在调度中,那么后面不能再有$xl_j(A)$,除非中间插入了$u_i(A)$

定理:由2PL事务所构成的任意合法调度$S$都是冲突可串行化的(用归纳法证明)

5.2.5 封锁粒度

• 多粒度封锁

  • 如果在一个系统中同时支持多种封锁粒度供事务选择使用,这种封锁方法被称为多粒度封锁
  • 可以按照封锁粒度的大小构造出一颗多粒度树,以树中的每个节点作为封锁对象,可以构成一个多粒度封锁协议

• 意向锁

  • 使用规定
    • 如果对一个节点加意向锁,则说明该节点的下层节点正在被加锁
    • 对任一节点加锁时,必须先对它的上层节点加意向锁
  • 三种常见的意向锁
    • 意向共享锁(IS锁):如果对节点$N$加IS锁,表示准备在节点$N$的某些后裔节点上加S锁
    • 意向排它锁(IX锁):如果对节点$N$加IX锁,表示准备在节点$N$的某些后裔节点上加X锁
    • 共享意向排它锁(SIX锁):如果对节点$N$加SIX锁,表示对节点$N$本身加S锁,并准备在$N$的某些后裔节点上加X锁

• 多粒度封锁协议
  • 申请封锁的顺序:上->下
  • 释放封锁的顺序:下->上

5.2.6 活锁与死锁

死锁

• 例子:$r_1(B),r_2(B),w_1(B)$

• 解除法

  • 超时死锁检测法
    • 事务的执行时间超时
    • 锁申请的等待时间超时
  • 等待图法
  • 时间戳死锁检测法
    • 每个事物都具有一个用于死锁检测的时间戳
    • 如果事务$T$必须等待另一个事务$U$所持有的锁
      • 等待-死亡方案:
        • 如果$T$比$U$老,那么允许$T$等待$U$持有的锁
        • 如果$U$比$T$老,那么事务$T$死亡(被回滚)
      • 伤害-等待方案:
        • 如果$T$比$U$老,他将伤害$U$,$U$必须被回滚
        • 如果$U$比$T$老,那么$T$等待$U$持有的锁

活锁

• 例子:

  • $T_1$(卖票):$xl_1(A),r_1(A),w_1(A),u_1(A)$
  • $T_2$(剩余票额查询):$sl_2(A),r_2(A),u_2(A)$
  • 先启动一个$T_2$,再启动一个$T_1$:$T_1$处于等待状态,在已经运行的$T_2$结束之前,不断有新启动的$T_2$加进来

• 解决方法:先来先服务

5.3 数据库恢复技术

5.3.2 数据库故障分类

• 小型故障

  • 事物内部故障

• 中性故障

  • 系统故障
  • 外部影响

• 大型故障

  • 磁盘故障
  • 计算机病毒
  • 黑客入侵

5.3.3.1 转储

• 静态转储:无事务运行时

• 动态转储

• 海量转储:每次转储全部数据库

• 增量转储:更新过的

5.3.3.2 日志

undo日志

• 记录格式

  • 开始一个事务:<Start T>
  • 提交事务$T$:<Commit T>
  • 放弃事务$T$:<Abort T>
  • 更新记录:<T, X, V>,事务$T$修改了数据库元素$X$的值,$X$的旧值是$V$

• 记载规则

  1. 如果事务$T$修改了数据库元素$X$,则<T, X, V>必须在$X$的新值写到磁盘前写到磁盘
  2. 如果事务$T$提交,则<Commit T>必须在事务$T$改变的所有DB元素写到磁盘后再写到磁盘

• 恢复过程

  1. 将所有事务划分为两种类型
     • 已提交事务:有<Start T>和<Commit T>
     • 未提交事务:有<Start T>没有<Commit T>
  2. 从undo日志的尾部向头部扫描整个日志,对每条更新记录<T, X, Y>:
     • 如果<Commit T>已被扫描到,则继续扫描下一条日志记录
     • 否则,由恢复管理器将数据库中的$X$的值改为$V$
  3. 在日志的尾部为每个未结束的事务$T$写入一条日志记录<Abort T>,并刷新日志(flush log)

• 检查点
  在日志中插入检查点的处理过程

  1. 系统停止接受启动新事务的请求
  2. 等所有当前活跃的事务提交或中止,并且在日志中写入<Commit T>或<Abort T>
  3. 将日志记录刷新到磁盘
  4. 写入日志记录<CKPT>,并再次刷新日志
  5. 重新开始接受新的事务

• 在故障恢复时,只要逆向扫描到第一条<CKPT>记录,就可以结束故障恢复工作

• 非静止检查点
  设置非静止检查点的步骤

  1. 写入日志记录<Start CKPT(T1, ..., Tk)>
  2. 等待$T_1, …, T_k$所有事务的提交或终止,在这个过程中允许启动执行新的事务
  3. 当$T_1, …, T_k$都已经完成时,写入日志记录<End CKPT>并刷新日志

• 带有非静止检查点undo日志的恢复

  1. 先遇到<End CKPT>记录
     • 继续向后(头部)扫描,直到出现与之相对应的<Start CKPT(...)>记录就可以结束故障恢复工作
  2. 先遇到<Start CKPT(T1, ..., Tk)>记录,故障恢复工作需要撤销两类事务的操作
     • 在<Start CKPT(T1, ..., Tk)>记录之后启动的事务
     • $T_1, …, T_k$中在系统崩溃前尚未完成的事务

• undo日志的不足

  • 在将事务改变的所有数据写到磁盘前不能提交该事务
  • 在事务的提交过程中需要执行许多写磁盘操作,增加了事务提交的时间开销

redo日志

• 记录格式

  • redo日志的记录格式与undo一样,唯一区别:在更新记录<T, X, V>中记载的是更新后的值

• 记载规则

  • 在修改磁盘上的任何数据库元素$X$之前,要保证所有与$X$这一修改有关的日志记录(包括提交记录<Commit T>)都必须出现在磁盘上

• 恢复过程

  1. 先扫描一遍日志文件,确定所有已经提交的事务
  2. 再从日志头部开始扫描,对每条更新记录<T, X, V>
     • 如果$T$时未提交事务,则继续扫描日志
     • 如果$T$是已提交的事务,则为数据库元素$X$写入新值$V$(有可能是冗余的写操作)
  3. 对每个未完成的事务(提交记录<Commit T>没有写入磁盘),在日志的尾部写入<Abort T>并刷新日志

• 非静止检查点

  1. 写入日志记录<Start CKPT(T1, ..., Tk)>($T_1, …, T_k$时当前所有活跃事务的标识符),并刷新日志.同时获得当时所有已提交事务的标识符集合$S$
  2. 将集合$S$中的事务已经写到内存缓冲区但还没有写道数据库磁盘的数据库元素写入磁盘
  3. 写入日志记录<End CKPT>并刷新日志,不需等待事务$T_1, …, T_k$或新开始事务的结束

• 带检查点redo日志的恢复

  • 找到最后一个被记入日志的<End CKPT>,假设与之对应的检查点记录时<Start CKPT(T1, ..., Tk)>,并找到最早出现的<Start Ti>
  • 重做$T_1, …, T_k$,以及在<Start CKPT()>后开始的已经被提交事务

• redo日志的不足

  • 要求事务提交和日志就刷新之前将所有修改过的数据保留在内存缓冲区中,可能增加事务需要的平均缓冲区的数量
  • 如果被访问的数据对象$X$不是完整的磁盘块,那么在undo日志与redo日志之间可能产生相互矛盾的请求

undo/redo日志

• 记录格式

  • 更新记录的格式<T, X, v, w>,不仅记录更新前的值$v$,同时也要记录更新后的值$w$

• 记载规则

  1. 在由于某个事务$T$所做的改变而修改磁盘上的数据库元素$X$之前,更新记录<T, X, v, w>必须出现在磁盘上
  2. 在每一条<Commit T>后面必须紧跟一条Flush Log操作

     事务提交(Commit)和写数据库磁盘(Output)的操作顺序是随机的

• 恢复过程

  1. 根据<Commit T>是否已经出现在磁盘中来确定事务$T$是否已经被提交
  2. 从后往前,撤销(undo)所有未提交的事务
  3. 从前往后,重做(redo)所有已提交的事务

• 检查点

  1. 写入日志记录<Start CKPT(T1, ..., Tk)>($T_1, …, T_k$是当前所有活跃事务的标识符),并刷新日志
  2. 将所有被修改过的缓冲区写到数据库的磁盘中去
  3. 写入日志记录<End CKPT>并刷新日志

• 带检查点日志的恢复

5.3.4 恢复策略

• 小型故障的恢复

  • 利用未结束事务的undo操作进行恢复

• 中型故障的恢复

  • 非正常中止的事务:undo
  • 已完成提交的事务:redo

• 大型故障的恢复

  • 先利用后备副本进行数据库恢复,再利用日志进行数据库的恢复

5.3.5 数据库镜像

将整个数据库的数据(或主要数据)实时复制到另一个磁盘中

5.4 事务处理实现技术

6 数据库中的数据交换

7 数据库的物理组织

8 关系数据库的规范化理论

8.2.1 函数依赖

• 平凡.非平凡函数依赖

• 完全函数依赖
  在关系模式$R(U)$中,如有$X\subseteq U,Y\subseteq U$,满足$X\to Y$,且对任何$X$的真子集$X’$都有$X’\not\to Y$,则称$Y$完全函数依赖于$X$,记作$X\overset{f}{\to}Y$

• 部分函数依赖

• 传递函数依赖
  在关系模式$R(U)$中,如有$X\subseteq U,Y\subseteq U,X\subseteq U$且满足$X\to Y,Y\not\subset X,Y\not\to X,Y\to Z$,则称$Z$传递函数依赖于$X$.否则称为非传递函数依赖(直接函数依赖)

• Armstrong公理系统

  • 基本规则
    • 自反规则:如果$Y$是$X$子集,则$X\to Y$
    • 增广规则:如果$X\to Y$,则$XZ\to YZ$
    • 传递规则:如果$X\to Y,Y\to Z$,则$X\to Z$
  • 扩充规则
    • 分解规则:如果$X\to YZ$,则$X\to Y$且$X\to Z$
    • 合并规则:如果$X\to Y$且$X\to Z$,则$X\to YZ$
    • 伪传递规则:如果$X\to Y$且$WY\to Z$,则$WX\to Z$

• 关键字(码,键,key)
  在关系模式$R(U,F)$中,如有$K\subseteq U$且满足$K\overset{f}{\to}U$,则称$K$为关系$R$的关键字

• 主属性集

  • 由关系模式$R$的所有关键字中的属性所构成的集合被称为关系模式$R$的主属性集
  • 主属性集中的属性被称为关系模式$R$的主属性

• 非主属性集

计算属性集$X$在函数依赖集$F$上的闭包$X_F^+$(简写为$X^+$)

$X^+=X$
repeat
 $oldX^+=X^+$
 foreach 函数依赖 $Y\to Z\in F$ do
  if $Y\subseteq X^+$ then $X^+=X^+\cup Z$
until ($oldX^+ == X^+$)

寻找关系模式$R(U,F)$的关键字$K$

输入:关系模式$R(U,F)$
输出:关系$R$的一个关键字$K$

$K=U$
foreach 属性 $A\in K$ {
 计算 $(K-A)_F^+$
 if $(K-A)_F^+$ 包含了$R$的所有属性 then {
  $K=K-A$
 }
}
return $K$

优化算法:设$F$时关系上的最小函数依赖集.根据$F$中的函数依赖,可将$U$划分为

1. 只在函数依赖的左边出现过的属性的集合$U_L$
2. 只在函数依赖的右边出现过的属性的集合$U_R$
3. 在两边都出现的属性的集合$U_A$
   其中

• $U_L$中的属性时没一个关键字的组成部分
• $U_R$中的属性不可能出现在任何一个关键字中
• 在关键自己算算法中,只需针对$U_A$中的属性进行for循环计算

$K=U-U_R$
foreach 属性 $A\in U_A$ {
 计算 $(K-A)_F^+$
 if $(K-A)_F^+$ 包含了$R$的所有属性 then {
  $K=K-A$
 }
}
return $K$

8.2.2 与函数依赖有关的范式

• 第一范式
  关系模式$R(U)$中的每个属性值都是一个不可分割的数据量
  如果不满足第一范式,那么也就不能被称为关系

• 第二范式
  关系模式$R(U)\in1NF$,且每个非主属性都完全函数依赖于关键字
  判断一个关系$R$是否满足2NF:

  1. 找到关系$R$的所有非主属性和所有候选关键字
  2. 检查每一个非主属性$A$和每一个关键字$K$之间的函数依赖,判断是否存在非主属性对于关键字的部分函数依赖

模式分解的方法

设关系模式$R$属性集合为$Head(R),F$时其函数依赖集.将其分解到满足范式$M$的步骤如下

1. 找出所有不满足范式$M$要求的函数依赖关系
2. 选择一个不符合要求的函数依赖关系作如下的分解
   假设$X\overset{f}{\to}Y\in F^+$且不满足范式$M$的要求,则将关系模式$R$分解为如下的两个子关系
   • $R_1(X\cup Y,\{X\to Y\})$
   • $R_2(Head(R)-Y,F_2)$,其中$F_2=\{A\to B|A\to B\in F^+$且$(A\cup B)\subseteq Head(R_2)\}$
3. 对于分解得到的子关系模式$R_2$重复上述的步骤1和2,直到所有的子关系模式都能满足范式$M$的要求
4. 合并那些具有相同关键字的子关系模式

• 第三范式
  设关系模式$R(U)\in$2NF,且每个非主属性都不传递函数依赖于关键字,则称关系模式$R(U)$满足第三范式
  如果关系$R\not\in$3NF,那么在关系$R$中必然存在以下形式的函数依赖$X\overset{f}{\to}Y$,其中$Y$是单个的非主属性,$X$不是关系$R$的关键字

• BCNF
  设关系模式$R(U)$满足1NF,且若$X\to Y$是$X$必含有该关系模式的关键字,则称关系模式$R(U)$满足BCNF范式

• 若$R(U)\in$BCNF,则$R(U)\in$3NF

8.2.3 多值依赖与第四范式

• 多值依赖(MVD)

  • 设有关系模式$R(U),X,Y\subseteq U$
  • $R(U)$满足
    1. 多$X$的一个确定值,存在$Y$的一组值与之对应
    2. 且$Y$的这组值又与关系中的其他属性$(U-X-Y)$的取值不相关
  • 称$Y$多值依赖于$X$,记为$X\to\to Y$

• 非平凡的多值依赖
  设在关系模式$R(U)$中,$X\to\to Y$且$U-X-Y\not=\emptyset$,则称$X\to\to Y$是非平凡的多值依赖,否则称其为平凡的多值依赖

• 多值依赖的性质
  在一个关系模式$R(U)$中

  1. 如有$X\to\to Y$,则必有$X\to\to(U-X-Y)$
  2. 如有$X\to Y$,则必有$X\to\to Y$

• 有关FD和MVD的推导规则

• 第四范式
  在$R(U)$中,如果$X\to\to Y$是非平凡多值依赖,则$X$必含有关键字,此时称关系模式$R$满足第四范式
  特点

  1. 函数依赖:要满足BCNF
  2. 不是函数依赖的多值依赖:只允许出现平凡多值依赖

8.3.1 函数依赖理论

• 函数依赖集的等价
  如果两个函数依赖集$F_1$和$F_2$的闭包是相等的,称函数依赖集$F_1$等价于函数依赖集$F_2$

• 最小函数依赖集

  • 与函数依赖集$F$向等价的所有函数依赖集中的最小者被称为函数依赖集$F$的最小函数依赖集
  • 也被称为最小覆盖

最小函数依赖集的判定条件