👨‍💻Zhenry's Notebook Set

Search

SearchSearch

CCCS笔记4-编程与数据结构

Nov 21, 20247 min read

CrashCourseComputerScience

课程全名：Crash Course Computer Science

学习资料：

  1. Youtube 原视频
  2. b站搬运中字视频

10早期编程语言

Hint

如何实现将根据不同情况设计不同的程序输入计算机，并保存计算机的结果？

  • 控制面板的必须性：实现可控编程
  • 插线板plugboard编程：改变插线实现程序变动。
  • 面板（开关）编程panel Programing：适合家用，拨动开关实现程序变动。
  • 冯诺依曼架构

|250

11 编程语言发展史

Hint

硬件编程高复杂性，门槛高，学习慢，难以推广使用。

插线板，开关等编程方式都属于硬件编程。

machine code机器码：二进制码，位数和排列有计算机可以理解含义。

一条机器指令可能是：10101000 00000010

pesudo code伪代码：不可运行，用于算法的直观理解

Initialize sum to 0
For each number in the list:
    Add the number to sum
Output sum

汇编码 (Assembly Code)：使用mnemonics + operands 助记符+操作符号表示机器指令， 汇编语言与机器指令一一对应（通过依赖于硬件的指令集）。

MOV AX, 5     ; 将数值5移动到寄存器AX
ADD AX, 3     ; 将寄存器AX的值加上3

assembler汇编器：用于吧汇编码转化为机器码

compiler编译器：把高级语言转化为低级语言

fortran，早期占主导地位的可编译语言

cobol，一次编写，到处运行，最早的通行可编译语言

产生年份语言
60ALGOL,LISP,BASIC
70PASCAL,C,SMALLTALK
80C++,Objective-C,PERL
90PYTHON,RUBY,JAVA
00SWIFT,C#,GO

12 编程原理-语句和函数

条件语句

循环结构

封装，接口，可重复使用性

13 算法

selection sort选择排序，理解直接，复杂度高

merge sort归并排序，分组，二并一，比较每组的最小值

graph search图搜索，算法经典问题，迪杰斯特拉算法

14 数据结构

  • arrays/list/vector
    • index
  • strings，字符串的终止：空字符（二进制的0）
  • matrix
  • struct
  • node
  • linked list/circular
  • queue
    • fifo
    • enqueue
    • dequeue
  • stack
    • lifo
    • push
    • pop
  • tree
    • 根节点root
    • 子节点children，除了根节点
    • 父节点parent，直系上一节点
    • 没有子节点的节点leaf
  • graph
  • 红黑树，红黑树的核心操作是高效的插入、删除和查找。红黑树通过旋转和重新着色来保持平衡。
  • 堆，一棵完全二叉树，某个节点的值总是不大于或不小于其父节点的值
    • |125

Note

C++ 有standard template library标准模板库，已经定义好了基础数据结构供使用。

15 图灵

Hint

计算机是否可以解决所有问题，什么问题可以用计算机解决？算法该如何定义？

图灵机：

由英国数学家艾伦·图灵（Alan Turing）在1936年提出。它被设计用来形式化地定义计算过程和可计算性问题。图灵机是理论计算机科学的基石之一，它通过非常简单的规则和操作，来模拟任意复杂的计算过程。

图灵机的组成部分

  1. 无限长的纸带：纸带分为一个个的方格，每个方格可以包含一个符号（通常为0或1）。纸带可以向左或向右移动，并且可以被读写。
  2. 读写头：读写头可以在纸带上移动，读取或写入符号，并根据当前符号和状态进行操作。
  3. 状态寄存器：存储图灵机的当前状态，图灵机有一组有限的状态。
  4. 状态转换规则表：也称为“程序”，定义了在某一状态下读到某个符号时，图灵机应该执行什么操作（例如写入新符号、移动读写头、转换到下一个状态）。

|250

图灵机的工作过程

图灵机通过以下步骤运行：

  1. 读写头读取当前纸带上的符号。
  2. 根据状态转换规则表，确定当前状态下读到这个符号后，应该写什么新符号、如何移动读写头（左或右），以及转移到哪个状态。
  3. 读写头执行上述操作，并重复这个过程，直到达到某个终止状态。

为什么要提出图灵机？

图灵机的提出主要是为了解决两个关键问题：

  1. 形式化定义算法和可计算性：

    • 在20世纪30年代，数学家们正在探讨“可计算性”和“算法”的定义问题。图灵机的设计为“什么是算法”提供了一个严格的数学模型，使得计算的概念可以被精确定义。
    • 图灵机可以帮助定义哪些问题是可以通过算法解决的，哪些问题是不可计算的。

  2. 证明与计算有关的理论：

    • 图灵机还被用来解决“停机问题”（Halting Problem），即给定一个程序和一个输入，是否能确定该程序最终是否会停止。图灵证明了一般情况下，这个问题是不可解的，从而揭示了计算的局限性。

图灵测试：

当计算机能够欺骗人类，使人将伪装好的计算机认定为人类的时候，称为智能intelligent。

==CAPTCHA全公开自动化图灵测试==，也可翻译为验证码:。a completely automated public turing test to tell computers and humans apart

计算机领域最高奖：图灵奖

Graph View

Backlinks