CS50哈佛大学计算机科学导论

Lecture 0 - Scratch

介绍了二进制，之后主要讲了Scratch的基本操作，以及如何使用Scratch制作一个游戏。Scratch是一种编程语言，可以通过拖拽的方式编写代码(类似于拼图)，适合学习编程的入门者。
感觉用处Scatch用处不大，适合小孩子入门学习编程，但是对于大学生来说，学习Scratch的意义不大，可以直接学习C语言。

Lecture 1 - C

经典程序开头

1
2
3
4
5
#include <stdio.h>
int main(void)
{
    printf("hello, world\n");
}

head file: #include <stdio.h>，stdio.h是一个头文件，里面包含了一些函数的声明，#include是一个预处理指令，告诉编译器在编译之前先包含stdio.h文件的内容。
library: 库，stdio.h是一个库，里面包含了一些函数的定义，printf就是其中一个函数，printf函数的作用是打印输出，printf函数的定义在stdio.h中。
main function: int main(void)，main函数是程序的入口，程序从main函数开始执行，main函数的返回值是int类型，int是整数的意思，main函数的参数是void，void是空的意思，表示main函数没有参数。

常见的获取输入的函数

导入#include<cs50.h>头文件，cs50.h头文件中包含了一些获取输入的函数。
get_char: get_char函数，get_char函数的作用是获取用户输入的字符，get_char函数的定义在stdio.h中。
get_int: get_int函数，get_int函数的作用是获取用户输入的整数。
get_string: get_string函数，get_string函数的作用是获取用户输入的字符串。
get_float: get_float函数，get_float函数的作用是获取用户输入的浮点数。
get_double: get_double函数，get_double函数的作用是获取用户输入的双精度浮点数。
get_long: get_long函数，get_long函数的作用是获取用户输入的长整数。

format codes

%c: c是char的缩写，%c是一个格式化代码，%c的作用是打印一个字符。
%d: d是decimal的缩写，%d是一个格式化代码，%d的作用是打印一个整数。
%f: f是float的缩写，%f是一个格式化代码，%f的作用是打印一个浮点数。
%lf: lf是double的缩写，%lf是一个格式化代码，%lf的作用是打印一个双精度浮点数。
%s: s是string的缩写，%s是一个格式化代码，%s的作用是打印一个字符串。
%5.2f:右对齐并占用宽度为5个字符，保留2位小数。
%-10s:左对齐并占用宽度为10的字符串。

条件语句

条件语句的作用是根据条件来执行不同的代码。
if-else语句

1
2
3
4
5
6
7
8
9
10
11
12
if (x < y)
{
    printf("x is less than y\n");
}
else if (x > y)
{
    printf("x is greater than y\n");
}
else
{
    printf("x is equal to y\n");
}

switch语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
switch (n)
{
    case 1:
        printf("n is 1\n");
        break;
    case 2:
        printf("n is 2\n");
        break;
    case 3:
        printf("n is 3\n");
        break;
    default:
        printf("n is not 1, 2, or 3\n");
        break;
}

运算符

+: 加法运算符。
-: 减法运算符。
*: 乘法运算符。
/: 除法运算符。
%: 取余运算符。
++: 自增运算符。
--: 自减运算符。
&&: 逻辑与运算符。
||: 逻辑或运算符。
!: 逻辑非运算符。
==: 相等运算符。
!=: 不相等运算符。
>: 大于运算符。
<: 小于运算符。
>=: 大于等于运算符。
<=: 小于等于运算符。
&: 按位与运算符。
|: 按位或运算符。
^: 按位异或运算符。
~: 按位取反运算符。
<<: 左移运算符。
>>: 右移运算符。
=: 赋值运算符。
+=: 加法赋值运算符。
-=: 减法赋值运算符。
*=: 乘法赋值运算符。
/=: 除法赋值运算符。
%=: 取余赋值运算符。
<<=: 左移赋值运算符。
>>=: 右移赋值运算符。
&=: 按位与赋值运算符。
^=: 按位异或赋值运算符。
|=: 按位或赋值运算符。

循环语句

循环语句的作用是重复执行一段代码。
while循环

1
2
3
4
while (true)
{
    printf("hello, world\n");
}

do-while循环

1
2
3
4
5
do
{
    printf("hello, world\n");
}
while (true);

for循环

1
2
3
4
for (int i = 0; i < 50; i++)
{
    printf("hello, world\n");
}

写循环时，注意死循环的问题，死循环会导致程序卡死，无法继续执行。如果程序进入了死循环，可以按ctrl+c强制退出程序。

局部变量

局部变量的作用域是在函数内部，局部变量只能在函数内部使用。

1
2
3
4
5
6
7
8
int f1(int a){
    int b,c;  //a,b,c仅在函数f1()内有效
    return a+b+c;
}
int main(){
    int m,n;  //m,n仅在函数main()内有效
    return 0;
}

全局变量

全局变量的作用域是在整个程序内部，全局变量可以在程序的任何地方使用。

1
2
3
4
5
6
7
8
9
10
11
12
int a, b;  //全局变量
void func1(){
    //TODO:
}
float x,y;  //全局变量
int func2(){
    //TODO:
}
int main(){
    //TODO:
    return 0;
}

局部变量和全局变量的区别

  1. 全局变量在内存中的位置固定，局部变量在内存中的位置不固定。
  2. 全局变量在程序的任何地方都可以使用，局部变量只能在函数内部使用。
  3. 全局变量的作用域是整个程序，局部变量的作用域是函数内部。
  4. 全局变量的生命周期是整个程序，局部变量的生命周期是函数内部。
  5. 全局变量的默认值是0，局部变量的默认值是随机值。
  6. 如果全局变量和局部变量同名，优先使用局部变量。

静态变量

静态变量的生命周期是整个程序，静态变量的作用域是局部的。
静态变量的初始化只会执行一次。

1
2
3
4
5
6
7
8
9
10
11
void func1(){
    static int a = 0;
    a++;
    printf("%d\n",a);
}
int main(){
    func1();  //1
    func1();  //2
    func1();  //3
    return 0;
}

输入的a是1，2，3，而不是1，1，1。

函数

函数的作用是封装一段代码，函数的参数是输入，函数的返回值是输出。

1
2
3
4
5
6
7
8
9
int add(int a, int b)
{
    return a + b;
}
int main(void)
{
    int x = add(1, 2);
    printf("%d\n", x); //3
}

add函数的参数是a和b，add函数的返回值是a+b。

函数的定义

1
2
3
4
int add(int a, int b)
{
    return a + b;
}

函数的声明

1
int add(int a, int b);

函数的调用

1
int x = add(1, 2);

终端命令

cd: change directory，切换目录。
ls: list，列出当前目录下的文件。
mkdir: make directory，创建目录。
cp: copy，复制文件。
mv: move，移动文件/重命名文件（根据参数的不同进行不同的操作）。
rm: remove，删除文件。
rmdir: remove directory，删除目录。
touch: 创建文件。
cat: concatenate，查看文件内容。
chmod: change mode，修改文件权限。

数据范围

char: 1字节，-128~127。
unsigned char: 1字节，0~255。
short: 2字节，-32768~32767。
unsigned short: 2字节，0~65535。
int: 4字节，-2147483648~2147483647。
unsigned int: 4字节，0~4294967295。
long: 4字节，-2147483648~2147483647。
unsigned long: 4字节，0~4294967295。
float: 4字节，-3.4E+38~3.4E+38。
double: 8字节，-1.7E+308~1.7E+308。
如果进行的运算超过了数据范围，会发生溢出，溢出的结果不是正确的结果。除了溢出问题，还有精度问题，浮点数的精度是有限的，如果进行的运算超过了浮点数的精度，会发生精度丢失，精度丢失的结果不是正确的结果。

Lecture 2 - Arrays

命令行参数

clang编译器的参数
-o: output，指定输出文件的名称。
-l: library，指定链接的库。
-I: include，指定头文件的路径。
-g: debug，生成调试信息。
-O: optimize，优化代码。
-Wall: 显示所有警告信息。
-Werror: 将警告信息当成错误信息。
-std: 指定C语言的版本。

1
2
clang hello.c -o hello
clang hello.c -o hello -lcs50

程序编译过程

  1. 预处理：预处理器将源代码中的宏定义和头文件插入到源文件中，生成.i文件。
  2. 编译：编译器将.i文件编译成汇编代码，生成.s文件。
  3. 汇编：汇编器将.s文件编译成机器码，生成.o文件。
  4. 链接：链接器将.o文件链接成可执行文件。
  5. 加载：加载器将可执行文件加载到内存中，程序开始执行。
  6. 运行：程序开始执行。

调试vscode

利用printf调试

printf的作用是打印输出，可以利用printf来调试程序。

利用调试器

调试器的作用是帮助我们找到程序中的错误。

  1. 在vscode中打开要调试的文件。
  2. 在要调试的文件中设置断点。
  3. 点击右上侧的调试按钮。
  4. 程序会在断点处暂停，可以查看变量的值。

数据类型

bool 1byte value: true/false
char 1byte value: 'a'
double 8byte value: 3.14
float 4byte value: 3.14
int 4byte value: 42
long 8byte value: 42
string 可变的(根据字符的个数而变化) value: "hello"

数组

数组的作用是存储一组相同类型的数据。

1
2
3
4
5
6
// 数组的定义
int scores[3];
// 数组的初始化
scores[0] = 72;
scores[1] = 73;
scores[2] = 33;

string.h

string.h是一个头文件，里面包含了一些字符串的函数。
strlen: strlen函数，strlen函数的作用是获取字符串的长度。
strcmp: strcmp函数，strcmp函数的作用是比较两个字符串是否相等。
strcat: strcat函数，strcat函数的作用是将两个字符串拼接起来。
strcpy: strcpy函数，strcpy函数的作用是将一个字符串复制到另一个字符串中。

ctype.h

ctype.h是一个头文件，里面包含了一些字符的函数。
isalpha: isalpha函数，isalpha函数的作用是判断字符是否是字母。
isdigit: isdigit函数，isdigit函数的作用是判断字符是否是数字。
islower: islower函数，islower函数的作用是判断字符是否是小写字母。
isupper: isupper函数，isupper函数的作用是判断字符是否是大写字母。
tolower: tolower函数，tolower函数的作用是将字符转换成小写字母。
toupper: toupper函数，toupper函数的作用是将字符转换成大写字母。

命令行参数

argc: argc是一个整数，argc的作用是获取命令行参数的个数。
argv: argv是一个字符串数组，argv的作用是获取命令行参数的值。
argv[0]存储的是程序的名称，argv[1]存储的是第一个命令行参数的值，argv[2]存储的是第二个命令行参数的值，以此类推。

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include <cs50.h>

int main(int argc, string argv[])
{
    for (int i = 0; i < argc; i++)
    {
        printf("%s\n", argv[i]);
    }
}

echo: echo命令，echo命令的作用是打印输出。
echo $?: $?是一个特殊变量，$?的作用是获取上一个命令的返回值。

Lecture 3 - Algorithms

复杂度

时间复杂度：时间复杂度是一个函数，表示程序运行所需要的时间。
空间复杂度：空间复杂度是一个函数，表示程序运行所需要的内存。

时间复杂度比较

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

查找

顺序查找/线性查找：顺序查找是一种简单的查找算法，按照顺序依次查找，直到找到指定的元素。（数组无序有序都可）
二分查找/折半查找：二分查找是一种高效的查找算法，将数组分成两半，每次查找都可以排除一半的元素。（数组有序）

结构体

结构体的作用是将多个数据组合成一个数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 定义结构体
typedef struct
{
    string name;
    string dorm;
}
student;
// 初始化结构体
student s;
s.name = "David";
s.dorm = "Eliot";
// 使用结构体
printf("%s is in %s.\n", s.name, s.dorm);

排序

选择排序：选择排序是一种简单的排序算法，每次选择最小的元素放到最前面。
冒泡排序：冒泡排序是一种简单的排序算法，每次比较相邻的两个元素，如果顺序不对就交换位置。

递归

递归的作用是将一个大问题分解成一个个小问题。

1
2
3
4
5
6
7
8
9
10
11
12
void countdown(int n)
{
    if (n == 0)
    {
        printf("Blastoff!\n");
    }
    else
    {
        printf("%d\n", n);
        countdown(n - 1);
    }
}

归并排序：归并排序是一种高效的排序算法，将数组分成两半，对每一半进行排序，然后将两个有序的数组合并成一个有序的数组。
快速排序：快速排序是一种高效的排序算法，每次选择一个元素作为基准，将数组分成两半，将小于基准的元素放到左边，将大于基准的元素放到右边，然后对左右两边的数组进行排序。

Lecture 4 - Memory

十六进制

十六进制：0~9，A~F，0x开头。比如0x1A，0xFF。
十六进制与二进制的转换：每四位二进制数对应一位十六进制数。
1001 1100 -> 0x9C

指针

指针的作用是存储内存地址。指针的内容是内存地址，指针的类型是指针指向的变量的类型。

1
2
int n = 50;
int *p = &n;

&是一个运算符，&的作用是获取变量的内存地址。
*是一个运算符，*的作用是获取指针指向的变量的值。

1
2
3
4
%p: 打印指针的值。
printf("%p\n", p); //0x7ffeea3b4a3c
%d: 打印指针指向的变量的值。
printf("%d\n", *p); //50

cs50课程中string本质就是一个字符数组，string的类型是char *。

stdlib.h

stdlib.h是一个头文件，里面包含了一些函数。
malloc: malloc函数，malloc函数的作用是分配内存。
free: free函数，free函数的作用是释放内存。

内存泄漏 memory leak

内存泄漏是指分配了内存但是没有释放内存，堆积的内存泄漏会导致内存不足，程序崩溃。

内存溢出 out of memory

内存溢出是指程序申请内存时，没有足够的内存供申请者使用。

NULL

NULL是一个特殊的指针，NULL的值是0，NULL的作用是表示指针不指向任何内存地址。

sizeof

sizeof是一个运算符，sizeof的作用是获取变量的大小。

交换

1
2
3
4
5
6
7
8
9
10
11
12
13
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
int main(void)
{
    int x = 1;
    int y = 2;
    swap(&x, &y);
    printf("x is %d, y is %d\n", x, y); //x is 2, y is 1
}

swap函数的参数是指针，swap函数的作用是交换两个变量的值。swap函数的参数不能是值，因为值传递的方式无法改变变量的值。

输入

scanf: scanf函数，scanf函数的作用是获取用户输入的值。

1
2
3
4
5
6
#include <stdio.h>
int x;
scanf("%d", &x);
char *s = malloc(50*sizeof(char));
scanf("%s", s);
free(s);

文件

文件的作用是存储数据。

文件的打开

fopen: fopen函数，fopen函数的作用是打开文件。'r’表示读取，'w’表示写入，'a’表示追加。在文件不存在时，'r’会报错，'w’会创建文件，'a’会创建文件。'r+'表示读取和写入，'w+'表示读取和写入，'a+'表示读取和追加。'rb’表示读取二进制文件，'wb’表示写入二进制文件，'ab’表示追加二进制文件。'r+b’表示读取和写入二进制文件，'w+b’表示读取和写入二进制文件，'a+b’表示读取和追加二进制文件。

1
FILE *file = fopen("phonebook.csv", "a");

文件的关闭

fclose: fclose函数，fclose函数的作用是关闭文件。

1
fclose(file);

文件的读取

fgetc: fgetc函数，fgetc函数的作用是从文件中读取一个字符。

1
int c = fgetc(file);

fgets: fgets函数，fgets函数的作用是从文件中读取一行字符。

1
2
3
char *s = malloc(50*sizeof(char));
fgets(s, 50, file);
free(s);

fread: fread函数，fread函数的作用是从文件中读取一段字符。

1
2
3
char *s = malloc(50*sizeof(char));
fread(s, 1, 50, file);
free(s);

fscanf: fscanf函数，fscanf函数的作用是从文件中读取格式化的字符。

1
2
3
char *s = malloc(50*sizeof(char));
fscanf(file, "%s", s);
free(s);

文件的写入

fputc: fputc函数，fputc函数的作用是向文件中写入一个字符。

1
fputc('A', file);

fputs: fputs函数，fputs函数的作用是向文件中写入一行字符。

1
fputs("Hello, world\n", file);

fwrite: fwrite函数，fwrite函数的作用是向文件中写入一段字符。

1
fwrite("Hello, world\n", 1, 13, file);

fprintf: fprintf函数，fprintf函数的作用是向文件中写入格式化的字符。

1
fprintf(file, "Hello, world\n");

Lecture 5 - Data Structures

队列 queue

队列的特点是先进先出FIFO。

栈 stack

栈的特点是后进先出LIFO。

链表 linked list

链表的特点是每个节点都包含了下一个节点的地址。

数组 array

数组的特点是每个元素都有一个索引，可以通过索引来访问元素。

树 tree

树的特点是每个节点都包含了子节点的地址。

二叉树 binary tree

二叉树的特点是每个节点都包含了左子节点和右子节点的地址。

二叉搜索树 binary search tree

二叉搜索树的特点是每个节点都包含了左子节点和右子节点的地址，左子树的值都小于根节点的值，右子树的值都大于根节点的值。

字典 dictionary

字典的特点是每个元素都包含了键和值。

哈希表 hash table

哈希表的特点是每个元素都包含了键和值，哈希表的键是唯一的，哈希表的值可以重复。

散列函数 hash function

散列函数的作用是将键转换成索引。

散列冲突 hash collision

散列冲突是指两个键经过散列函数转换后得到了相同的索引。

散列冲突的解决方法

  1. 开放寻址法：如果发生了散列冲突，就寻找下一个空的索引。
  2. 链接法：如果发生了散列冲突，就将元素放到链表中。
  3. 再散列法：如果发生了散列冲突，就使用另一个散列函数。

trie树/字典树/前缀树

trie树的核心思想是空间换时间，trie树的特点是每个节点都包含了子节点的地址，trie树的每个节点都包含了26个子节点的地址，trie树的每个节点都包含了一个布尔值，布尔值的作用是判断当前节点是否是一个单词的结尾。

Lecture 6 - Python

Python

Python是一种编程语言，Python的特点是简单易学，Python的缺点是运行速度慢。

创建一个python文件

1
code hello.py
1
print("hello, world")

运行hello.py

1
python hello.py

导入库

1
2
3
4
from xx import xx
from cs50 import get_string
import xx
import sys

安装库

1
2
pip install 库名
pip install cs50

函数

函数的作用是封装一段代码，函数的参数是输入，函数的返回值是输出。

1
2
3
def square(x):
    print(x * x)
    return x * x

输出

print函数，print函数的作用是打印输出。

1
2
3
answer = get_string("What's your name?\n") # David
print("hello, " + answer) # hello, David
print(f"hello, {answer}") # hello, David

条件语句

条件语句的作用是根据条件来执行不同的代码。
if-else语句

1
2
3
4
5
6
if x < y:
    print("x is less than y")
elif x > y:
    print("x is greater than y")
else:
    print("x is equal to y")

in

in是一个运算符，in的作用是判断一个元素是否在一个序列中。

1
2
3
name = "David"
print("D" in name) # True
print("X" in name) # False

循环语句

循环语句的作用是重复执行一段代码。
while循环

1
2
while True:
    print("hello, world")

for循环

1
2
for i in range(50):
    print("hello, world",end="")

main函数

main函数是程序的入口，程序从main函数开始执行。

1
2
3
4
def main():
    print("hello, world")
if __name__ == "__main__":
    main()
1
2
3
4
5
6
def main():
    woof(3)
def woof(n):
    for i in range(n):
        print("woof")
main()

运算符

+: 加法运算符。
-: 减法运算符。
*: 乘法运算符。
/: 除法运算符。
%: 取余运算符。
//: 整除运算符。
**: 幂运算符。
+=: 加法赋值运算符。
-=: 减法赋值运算符。
*=: 乘法赋值运算符。
/=: 除法赋值运算符。
%=: 取余赋值运算符。
//=: 整除赋值运算符。
**=: 幂赋值运算符。
==: 相等运算符。
!=: 不相等运算符。
>: 大于运算符。
<: 小于运算符。
>=: 大于等于运算符。
<=: 小于等于运算符。
and: 逻辑与运算符。
or: 逻辑或运算符。
not: 逻辑非运算符。
is: 身份运算符。
is not: 身份运算符。
in: 成员运算符。
not in: 成员运算符。
&: 按位与运算符。
|: 按位或运算符。
^: 按位异或运算符。
~: 按位取反运算符。
<<: 左移运算符。
>>: 右移运算符。
=: 赋值运算符。

1
2
3
4
x = int(input("x: ")) # 1
y = int(input("y: ")) # 3
z = x / y 
print(f"{z:.10f}") # 0.3333333333

exception

exception的作用是捕获错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
try:
    x = int(input("x: "))
    y = int(input("y: "))
except ValueError:
    print("Error: invalid input")
    sys.exit(1)
try:
    result = x / y
except ZeroDivisionError:
    print("Error: cannot divide by 0")
    sys.exit(1)
print(f"{x} / {y} = {result}")

def get_int(prompt):
    while True:
        try:
            n = int(input(prompt))
            return n
        except ValueError:
            pass

list

list的特点是类似于数组，但是list的长度是随时可变的。

1
2
3
4
5
6
7
8
9
scores = [72, 73, 33]
scores.append(100)
print(scores) #[72, 73, 33, 100]
print(scores[0]) #72
print(scores[1]) #73
print(scores[2]) #33
print(scores[3]) #100
average = sum(scores) / len(scores)
print(f"Average: {average}") #Average: 69.5

dict

dict的特点是每个元素都包含了键和值。

1
2
3
4
5
6
7
people = {
    "David": "717-555-0101",
    "Brian": "717-555-0102",
    "Joanna": "717-555-0103"
}
people["David"] = "717-555-0104"
print(people["David"]) #717-555-0104
1
2
3
4
5
6
7
8
9
10
11
12
people = [
    {"name": "David", "number": "717-555-0101"},
    {"name": "Brian", "number": "717-555-0102"},
    {"name": "Joanna", "number": "717-555-0103"}
]
name = input("Name: ")
for person in people:
    if person["name"] == name:
        print(f"Number: {person['number']}")
        break
else:
    print("Not found")

tuple

tuple的特点是元素不可变，操作类似于list。

1
2
coordinate = (10.0, 20.0)
print(f"x = {coordinate[0]}, y = {coordinate[1]}") #x = 10.0, y = 20.0

set

set的特点是元素不可重复。

1
2
3
4
5
6
7
8
9
s = set()
s.add(1)
s.add(2)
s.add(3)
s.add(4)
s.add(3)
s.add(2)
s.add(1)
print(s) #{1, 2, 3, 4}

sys

sys是一个库，sys的作用是提供了一些系统相关的功能。

1
2
3
4
5
form sys import argv
if len(argv) == 2:
    print(f"hello, {argv[1]}")
else:
    print("hello, world")

Artifical Intelligence

chatgpt

ChatGPT是一种基于人工智能的聊天机器人，使用自然语言处理技术生成自然对话。GPT是Generative Pre-trained Transformer的缩写，可以翻译为“生成式预训练变换器”，是一种基于深度学习的自然语言处理技术。ChatGPT由OpenAI公司开发，它的前身是GPT，是一种基于深度学习的自然语言处理技术，可以生成自然语言文本。

决策树 decision tree

决策树是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。从数据产生决策树的机器学习技术叫做决策树学习，通俗说就是决策树。

minimax算法

在零和博弈中，玩家均会在可选的选项中将其N步后优势最大化或者令对手优势最小化。在这种情况下，一种最佳策略是一种能够使自己的最小利益最大化的策略。这种策略被称为最小最大策略，简称minimax策略。minimax算法是一种基于搜索的算法，它的作用是在零和博弈中找到最佳策略。
minimax算法是一种经典的博弈树搜索算法，主要用于解决零和博弈问题，如棋类游戏。该算法的核心思想是通过遍历博弈树的所有节点，找到能够使己方收益最大化的动作。在极大极小算法中，需要计算一个博弈树，每个节点代表一个游戏状态，每条边代表一个可能的动作。算法在博弈树中交替进行最大化（己方）和最小化（对手）操作，以评估不同动作的价值。

神经网络

神经网络是一种模拟人脑神经网络的数学模型，它的作用是模拟人脑神经元之间的连接关系，用于识别模式和关系，从而实现人工智能。神经网络由神经元组成，神经元之间通过突触连接，神经元之间的连接强度称为权重，神经元之间的连接关系称为拓扑结构。神经网络的训练过程是通过调整权重来实现的，神经网络的训练过程称为反向传播。

Lecture 7 - SQL

flat-file database

flat-file database是一种简单的数据库，它的特点是数据存储在一个文件中，每一行代表一条记录，每一列代表一个字段。

csv

csv是一种简单的数据库，它的特点是数据存储在一个文件中，每一行代表一条记录，每一列代表一个字段，每一列之间用逗号分隔。

1
2
3
4
5
import csv
with open("students.csv", "r") as file:
    reader = csv.DictReader(file)
    for row in reader:
        print(row["name"], row["dorm"], row["birth"])

统计个数

1
2
3
4
5
6
7
8
9
import csv
from collections import Counter
with open("favorites.csv", "r") as file:
    reader = csv.DictReader(file)
    counter = Counter()
    for row in reader:
        counter[row["name"]] += 1
    for favorite, count in counter.most_common():
        print(f"{favorite}: {count}")

most_common()函数的作用是获取出现次数最多的元素。参数n的作用是获取出现次数最多的前n个元素。如果不指定参数n，就会获取所有元素。

CRUD

CRUD是一种数据库操作，CRUD的作用是增删改查。C是Create的缩写，表示创建。R是Read的缩写，表示读取。U是Update的缩写，表示更新。D是Delete的缩写，表示删除。
常见操作 AVG, COUNT, DISTINCT, LOWER, MAX, MIN, SUM, UPPER
WHERE, LIKE, AND, OR, NOT, BETWEEN, IN, IS NULL, ORDER BY, LIMIT, GROUP BY, HAVING
创建

1
2
3
4
5
sqlite3 favorites.db
Are you sure you want to create favorites.db? [y/N] y
sqlite> .mode csv #设置输出格式
sqlite> .import favorites.csv favorites #导入数据
sqlite> .quit #退出
1
2
3
sqlite3 favorites.db
sqlite> .schema #查看表结构
CREATE TABLE IF NOT EXISTS "favorites" (Timestamp TEXT, "language" TEXT, "problem" TEXT);

读取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sqlite3 favorites.db
sqlite> SELECT * FROM favorites;
sqlite> SELECT language FROM favorites;
sqlite> SELECT language FROM favorites LIMIT 6;
# 计数
sqlite> SELECT COUNT(*) FROM favorites;
sqlite> SELECT COUNT(language) FROM favorites
# 种类
sqlite> SELECT DISTINCT(language) FROM favorites;
sqlite> SELECT COUNT(DISTINCT(language)) FROM favorites
# WHERE
sqlite> SELECT COUNT(*) FROM favorites WHERE language = "Python";
sqlite> SELECT COUNT(*) FROM favorites WHERE language = "Python" AND problem = "Hello, world";
sqlite> SELECT language, COUNT(*) FROM favorites GROUP BY language;
sqlite> SELECT language, COUNT(*) FROM favorites GROUP BY language ORDER BY COUNT(*) DESC;

更新+删除

1
2
3
4
5
6
7
# 插入
sqlite3 favorites.db
sqlite> INSERT INTO favorites (Timestamp, language, problem) VALUES ("2020-01-01 00:00:00", "Python", "Hello, world");
# 删除
sqlite> DELETE FROM favorites WHERE Timestamp = "2020-01-01 00:00:00";
# 更新
sqlite> UPDATE favorites SET language = 'SQL', problem = 'Fifty'

嵌套查询

嵌套查询的作用是将一个查询的结果作为另一个查询的条件。

1
sqlite> SELECT * FROM favorites WHERE language IN (SELECT language FROM favorites WHERE problem = "Hello, world");

PRIMARY KEY是一种约束，PRIMARY KEY的作用是保证每一条记录都有唯一的标识。
FOREIGN KEY是一种约束，FOREIGN KEY的作用是保证两个表之间的关系。

合并多个表

JOIN是一种查询，JOIN的作用是将两个表连接起来。可以实现一对一，一对多，多对多的关系。

1
2
sqlite> SELECT * FROM shows JOIN 
genres ON show.id = genres.show_id WHERE id = 63881;

JOIN可以连接多个表。

1
sqlite> SELECT title FROM shows JOIN stars ON shows.id = stars.show_id JOIN people ON stars.person_id = people.id;

索引

索引的作用是提高查询的效率。

1
2
3
sqlite> CREATE INDEX name ON table(column, ...);
sqlite> CREATE INDEX title_index ON shows(title);
sqlite> SELECT * FROM shows WHERE title = "The Office";

索引的底层实现是B树，B树的特点是每个节点都包含了多个子节点的地址，B树的每个节点都包含了多个键，B树的每个节点都包含了多个值，B树的每个节点都包含了一个布尔值，布尔值的作用是判断当前节点是否是叶节点。用空间换时间。
默认情况下，主键会自动创建索引，外键是没有索引的。

互斥

一些共享变量需要互斥访问，互斥的作用是保证同一时间只有一个线程访问共享变量。如果不互斥访问，就会发生竞态条件，竞态条件的结果是不确定的。
SQL为了保证数据的一致性，会自动加锁，自动加锁的作用是保证同一时间只有一个线程访问共享变量。

SQL注入攻击

1
2
3
4
# 安全
rows = db.execute("SELECT * FROM users WHERE username = ? AND password = ?", username, password)
# 不安全
rows = db.execute(f"SELECT * FROM users WHERE username = '{username}' AND password = '{password}'")

Lecture 8 - HTML, CSS, JavaScript

标记语言(markup language)是一种计算机语言，它的作用是定义文档的结构和格式。标记语言的特点是使用标记来定义文档的结构和格式。标记语言包括HTML，CSS，XML，Markdown，LaTeX等。

数据包

数据包是一种数据结构，它的作用是将数据封装成一个整体。数据包的特点是包含了数据和数据的长度。数据包用于网络通信，数据包的发送方将数据封装成数据包，数据包的接收方将数据包解析成数据。

协议

协议是一种规则，它的作用是定义了数据的格式和数据的含义。协议的特点是定义了数据的格式和数据的含义。协议用于网络通信，协议的发送方将数据封装成数据包，协议的接收方将数据包解析成数据。

TCP

TCP是一种协议，它的作用是保证数据的可靠传输。TCP的特点是保证数据的可靠传输。TCP用于网络通信，TCP的发送方将数据封装成数据包，TCP的接收方将数据包解析成数据。

UDP

UDP是一种协议，它的作用是保证数据的快速传输。UDP的特点是保证数据的快速传输。UDP用于网络通信，UDP的发送方将数据封装成数据包，UDP的接收方将数据包解析成数据。

HTTP

HTTP是一种协议，它的作用是定义了客户端和服务器之间的通信规则。HTTP的特点是定义了客户端和服务器之间的通信规则。HTTP用于网络通信，HTTP的发送方将数据封装成数据包，HTTP的接收方将数据包解析成数据。

DHCP

DHCP是一种协议，它的作用是自动分配IP地址。DHCP的特点是自动分配IP地址。DHCP用于网络通信，DHCP的发送方将数据封装成数据包，DHCP的接收方将数据包解析成数据。

DNS

DNS是一种协议，它的作用是将域名转换成IP地址。DNS的特点是将域名转换成IP地址。DNS用于网络通信，DNS的发送方将数据封装成数据包，DNS的接收方将数据包解析成数据。

HTML

HTML是一种标记语言，它的作用是定义网页的结构和内容。HTML的特点是使用标记来定义网页的结构和内容。HTML用于网页，HTML的发送方将数据封装成数据包，HTML的接收方将数据包解析成数据。

url格式

url格式是一种格式，它的作用是定义了url的结构和含义。url格式的特点是定义了url的结构和含义。url格式用于网页，url格式的发送方将数据封装成数据包，url格式的接收方将数据包解析成数据。
https://www.example.com/path
https://www.example.com/folder/file.html

状态码

状态码是一种标记，它的作用是表示请求的结果。状态码的特点是表示请求的结果。状态码用于网页，状态码的发送方将数据封装成数据包，状态码的接收方将数据包解析成数据。
200 OK 请求成功
301 Moved Permanently 永久重定向
302 Found 临时重定向
304 Not Modified 未修改
307 Temporary Redirect 临时重定向
400 Bad Request 请求错误
401 Unauthorized 未授权
403 Forbidden 禁止访问
404 Not Found 请求失败
410 Gone 请求失败
418 I'm a teapot 我是一个茶壶
500 Internal Server Error 服务器错误
503 Service Unavailable 服务器错误

HTML

HTML是一种标记语言，它的作用是定义网页的结构和内容。
标签分为单标签和双标签，单标签由一个标签名组成，双标签由一个开始标签和一个结束标签组成。

1
2
3
4
5
6
7
8
9
<!DOCTYPE html>
<html>
    <head>
        <title>hello, world</title>
    </head>
    <body>
        <h1>hello, world</h1>
    </body>
</html>

<!DOCTYPE html>是一个标签，<!DOCTYPE html>的作用是定义文档的类型。
<html>是一个标签，<html>的作用是定义文档的根元素。
<head>是一个标签，<head>的作用是定义文档的头部。
<title>是一个标签，<title>的作用是定义文档的标题。
<body>是一个标签，<body>的作用是定义文档的主体。
<h1>是一个标签，<h1>的作用是定义文档的标题。
<p>是一个标签，<p>的作用是定义文档的段落。
<a>是一个标签，<a>的作用是定义文档的链接。
<img>是一个标签，<img>的作用是定义文档的图片。
<ul>是一个标签，<ul>的作用是定义文档的无序列表。
<ol>是一个标签，<ol>的作用是定义文档的有序列表。
<li>是一个标签，<li>的作用是定义文档的列表项。
<table>是一个标签，<table>的作用是定义文档的表格。
<tr>是一个标签，<tr>的作用是定义文档的表格行。
<td>是一个标签，<td>的作用是定义文档的表格单元。
<th>是一个标签，<th>的作用是定义文档的表格标题。
<div>是一个标签，<div>的作用是定义文档的块级元素。
<span>是一个标签，<span>的作用是定义文档的行内元素。
<form>是一个标签，<form>的作用是定义文档的表单。
<input>是一个标签，<input>的作用是定义文档的输入框
除了上面的标签，还有很多标签，参考前端网站MDN

注释

注释的作用是注释掉一段代码。

1
<!-- <h1>hello, world</h1> -->

超链接

超链接的作用是跳转到另一个网页。

1
<a href="https://www.harvard.edu/">https://www.yale.edu/</a>

meta标签

meta标签的作用是定义文档的元数据。

1
2
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">

正则表达式

正则表达式是一种模式，它的作用是匹配字符串。正则表达式的特点是匹配字符串。正则表达式用于网页，正则表达式的发送方将数据封装成数据包，正则表达式的接收方将数据包解析成数据。

1
<input type="text" pattern="[0-9]{3}-[0-9]{3}-[0-9]{4}">

CSS

CSS是一种标记语言，它的作用是定义网页的样式。

class

class是一种属性，它的作用是定义网页的样式。class的特点是定义网页的样式。class用于网页，class的发送方将数据封装成数据包，class的接收方将数据包解析成数据。

1
<h1 class="red">hello, world</h1>
1
2
3
.red {
    color: red;
}

id

id是一种属性，它的作用是定义网页的样式。id的特点是定义网页的样式。id用于网页，id的发送方将数据封装成数据包，id的接收方将数据包解析成数据。

1
<h1 id="red">hello, world</h1>
1
2
3
#red {
    color: red;
}

javascript

javascript是一种编程语言，它的作用是定义网页的行为。
let的作用是定义变量。let的特点是定义变量。let用于网页，let的发送方将数据封装成数据包，let的接收方将数据包解析成数据。

1
2
3
4
5
<h1 id="red">hello, world</h1>
<script>
    let heading = document.querySelector("#red");
    heading.style.color = "red";
</script>

DOM Document Object Model

DOM是一种数据结构，它的作用是表示网页的结构。DOM的特点是表示网页的结构。DOM用于网页，DOM的发送方将数据封装成数据包，DOM的接收方将数据包解析成数据。

route

route是一种路径，它的作用是表示网页的路径。route的特点是表示网页的路径.
https://www.example.com/route?key=value&key=value

Lecture 9 - Flask

Flash是实际是python的第三方库。
index.html

1
2
3
4
5
6
7
8
9
10
<!DOCTYPE html>
<html lang="en">
    <head>
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <title>hello</title>
    </head>
    <body>
        hello, {{ placeholder }} 
    </body>
</html>
1
2
3
4
5
6
7
8
9
10
from flask import Flask，render_template, request
app = Flask(__name__)
@app.route("/")
def index():
    # if "name" in request.args:
    #     name = request.args["name"]
    # else:
    #     name = "world"
    name = request.args.get("name", "world")
    return render_template("index.html", placeholder=name)

继承

layout.html

1
2
3
4
5
6
7
8
9
10
<!DOCTYPE html>
<html lang="en">
    <head>
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <title>{% block title %}{% endblock %}</title>
    </head>
    <body>
        {% block body %}{% endblock %}
    </body>
</html>

greet.html

1
2
3
4
5
{% extends "layout.html" %}
{% block title %}hello{% endblock %}
{% block body %}
    hello, {{ name }}
{% endblock %}
1
2
3
4
5
6
from flask import Flask，render_template, request
app = Flask(__name__)
@app.route("/greet", methods=["POST"])
def greet():
    name = request.form.get("name", "world")
    return render_template("greet.html", name=name)

jinja2是一种模板语言，它的作用是定义网页的结构和内容。jinja2的特点是使用标记来定义网页的结构和内容。

1
2
3
4
5
6
```html
{% extends "layout.html" %}
{% block title %}hello{% endblock %}
{% block body %}
    hello, {% if name %}{{ name }}{% else %}world{% endif %}
{% endblock %}

如果name不为空，就显示name，否则就显示world。

Cookie 是一些数据, 存储于你电脑上的文本文件中。当web服务器向浏览器发送web页面时，在连接关闭后，服务端不会记录用户的信息。Cookie 的作用就是用于解决 “如何记录客户端的用户信息”: 当用户访问web页面时，他的名字可以记录在cookie中。当用户下一次访问该页面时，可以在cookie中读取用户访问记录。

Ajax

Ajax(Asynchronous Javascript And XML)，即是异步的JavaScript和XML，Ajax其实就是浏览器与服务器之间的一种异步通信方式

API

应用程序接口（API，Application Programming Interface）是基于编程语言构建的结构，使开发人员更容易地创建复杂的功能。它们抽象了复杂的代码，并提供一些简单的接口规则直接使用。
客户端 JavaScript 中有很多可用的 API — 他们本身并不是 JavaScript 语言的一部分，却建立在 JavaScript 语言核心的顶部，为使用 JavaScript 代码提供额外的超强能力。他们通常分为两类：
浏览器 API内置于 Web 浏览器中，能从浏览器和电脑周边环境中提取数据，并用来做有用的复杂的事情。例如Geolocation API提供了一些简单的 JavaScript 结构以获得位置数据，因此你可以在 Google 地图上标示你的位置。在后台，浏览器确实使用一些复杂的低级代码（例如 C++）与设备的 GPS 硬件（或可以决定位置数据的任何设施）通信来获取位置数据并把这些数据返回给你的代码中使用浏览器环境；但是，这种复杂性通过 API 抽象出来，因而与你无关。
第三方 API缺省情况下不会内置于浏览器中，通常必须在 Web 中的某个地方获取代码和信息。例如Twitter API 使你能做一些显示最新推文这样的事情，它提供一系列特殊的结构，可以用来请求 Twitter 服务并返回特殊的信息。

JSON

JSON(JavaScript Object Notation)是存储和交换文本信息的语法，类似XML。JSON比XML更小、更快，更易解析。JSON易于人阅读和编写。

Lecture Cybersecurity

最常用的密码

  1. 123456
  2. admin
  3. 12345678
  4. 123456789
  5. 1234
  6. 12345
  7. password
  8. 123
  9. Aa123456
  10. 1234567890

password manager

password manager是一种软件，它的作用是为用户生成一个随机足够长的复杂的密码，然后将随机密码保存到一个文件中。

two-factor authentication

two-factor authentication是一种认证方式，是在密码认证的基础上，再增加一层认证。

hash

hash是一种算法，它的作用是将任意长度的数据转换成固定长度的数据。将用户的密码利用哈希函数转换成hash值，然后将hash值保存到数据库中。
但是只使用用户密码进行输入，如果用户密码相同，经过哈希函数，可能会得到同一个哈希值。因此我们会进行salting的操作，这样哈希函数就需要两个输入，不仅是密码，还有另一个值，称为salt。salt是一个随机值，这样即使用户的密码相同，经过哈希函数，得到的哈希值也不同（扰动输出）。

cryptography

cryptography加密是将明文转换成密文，解密是将密文转换成明文。

passkey

通行密钥(passkey)主要想要实现的，是在原本的「用户名-密码」安全体系外，寻找一种更为简单、直接，但同样具备安全性的用户身份验证方式。这个替代验证手段的思路具体到原理，从某种程度上来说则是真的「干掉了密码」。通行密钥将以往需要加密储存在服务器端的登录信息，替换为非对称加密技术中的口令。和包含用户名、密码的传统凭证数据不同，在非对称加密技术中，注册通行密钥的设备会成一段「公钥」和「私钥」交给提供注册服务的服务器。
我们可以把公钥类比于带「防盗」锁的传统信箱，把私钥类比于信箱的锁的钥匙。邮递员投递的信件就是我们要加密的信息，通过投递到信箱中加密起来，然后也只有信箱的主人才有钥匙能够打开信箱读取信件的内容。如果一个人手上没有钥匙，那就需要用暴力开防盗锁，整个过程不仅耗时耗力，最后也往往没办法打开那把防盗锁。与之对应的，如果某些内容被公钥加密了，则该内容能且仅能被私钥解密。
非对称加密的可靠性正来源于此——若无私钥，在有限的算力和有限的时间内我们一般无法完成极大整数的因数分解；如果加密内容能被解密，则说明对方拥有私钥。
所以只要服务器用公钥加密一段认证信息，用户设备上的私钥钥可以解密这段认证信息，那么就可以证明我是「我」了，这也是通行密钥的实现基础，而通过这一个间接匹配就完成了密码认证。整个过程既不用劳神费力的敲入具体的密码、也不需要让密码离开本地设备，更能避免因为服务器受攻击而导致密码泄露，降低传输风险。

end-to-end encryption

端到端加密始于加密系统，这是一种通过将信息转换为密文的不可读格式来保护信息的方法。 只有拥有密钥的用户才能将消息解密或解密为明文。 使用 E2EE，发送者或创建者对数据进行加密，只有指定的接收者或阅读者才能对其进行解密。

ransomware

勒索软件是一种恶意软件，它的作用是加密用户的文件，然后勒索用户赎金。