1037Life

4-附加册

Part 4

附加练习题

练习题

题目 1
灵梦和魔理沙打则,灵梦有$10$张Spell Card,想组一套卡组:$5$个$A$,$3$个$B$,$2$个$C$,那么灵梦在最终打则的时候会遇到几种情况?(考虑Spell Card刷新情况)

题目 2
夜雀烧烤摊一共有五种烤串,分别是小碎骨串、八目鳗串、白泽肉串、团子串和毛玉串.
一个盲盒里面有$10$串烤串:
(i)可以有多少种不同的盲盒?
(ii)若每个味道的团子都要出现一遍,可以有多少种不同的盲盒?

题目 3
寺子屋的运动会结束了,琪露诺、大妖精、露米娅和三月精都参加了运动会.慧音老师说有的人报了$100\mathrm$;有的人报了跳远;有的人报了$1000\mathrm$;有的人报了跳高……
(i) 构建一个函数模型,它是否是满射?是否是单射?
(ii) 这几个人的成绩一共有多少种可能的结果?

题目 4
恋、魔理沙、紫、永琳在剧院看戏,然后妹红和辉夜打架不小心把剧院给烧了.慌乱之中,她们四个随便戴上了一个帽子夺路而逃,却没有注意她们各自戴的帽子究竟是不是自己的.问她们四个戴上的帽子不是自己的的概率是多少?

题目 5
设$1\leqslant x,y \leqslant N$,$f(k)$表示最大公约数为$k$的有序数对$(x,y)$的个数,求$f(1)$到$f(N)$的值.(提示:由容斥原理可以得知,先找到所有以$k$为 公约数 的数对,再从中剔除所有以 的倍数为$k$公约数 的数对,余下的数对就是以$k$为 最大公约数的数对.即$f(k)=$以$k$为公约数的数对个数$-$以$k$的倍数为公约数 的数对个数.)

题目 6
夜雀食堂,小碎骨$5$元一串.现在有$2n$位幻想乡居民,其中$n$个有$10$元钞票,剩下$n$个有$5$元钞票,请问有多少种情况可以使得给十块钱的居民有钱找?(提示:可以转化成$2n$个元素入栈顺序问题)

题目 7
计算机程序中,语句对先前语句的依赖性可以用有向图表示.每个语句用一个顶点表示,如果在第一个顶点表示的语句执行完毕之前,第二个顶点表示的语句不能执行,则从一个顶点到第二个顶点存在一条边.
根据上述规则,用图表示算式$(a+3)\times4+5$.

题目 8
琪露诺、三妖精和大妖精她们在一块聊天,琪露诺说:“我能不能只和你们$4$个人的其中$3$个人做好朋友呢?”
琪露诺的假设能成立吗?

题目 9
请证明对于任意一个无向图,不同的点独立集的数量等于不同的点覆盖集的数量.

题目 10
永琳想设立若干个仓库,她想节约成本,有几种药不能放在一起,其他的可以放在一起,试建立图模型,找出仓库最少要建几个?

题目 11
(i)模仿之前的定义,给出边覆盖数和边独立数的定义.
(ii)证明:边独立数$+$边匹配数$=$顶点的个数.

题目 12
用Hungary算法法求出下面CP组合的最大匹配:

CP组合关系图

题目 13
给定一个无向图,请基于Dinic算法设计一个算法求出至少需要选出多少条互不相交也不自交的图上路
径,使得每个点都被覆盖.(提示:这里可以假设给你一个Dinic算法黑盒,扔进去一个二分图它就吐出来一个最大匹配.根据$G$构造一个新的图,使得新图的最大匹配等于原图的最小不相交路径覆盖,然后在新图上使用Dinic算法)

题目 14
一个有向图$G$中,一个边集被称为洋流,当且仅当这个边集由若干个(可能为$0$个)不相交的简单环组成,构造一个无向图$H$,使得 中完美匹配的数量和$G$中“洋流”的数量相等.(提示:数量相等一般可以考虑构造双射;要注意完美匹配选出来的边数量是一定的,但一个洋流可能一条边都没有,这时如何将空集双射到完美匹配;太一般的情况难以求解,可以以上一题为启发考虑$H$为二分图的情况)

Last Spell Card:上面的中,如果$G$是无向图如何构造?

题目 15
(Fibonacci数列通项)
迷途之家中,假设有一片区域的小猫总是雌雄成对出生,且不会死亡,不与其他区域的猫流通.一对小猫幼崽一年后长成一对成年猫,猫在成年后每年会产生一对幼崽.求第$n$年在这一区域有多少对小猫.(答案:$a_n=\dfrac}\left(\left(\dfrac}\right)n-\left(\dfrac{1-\sqrt{5}}{2}\right)n\right)$)

参考答案

题目 16
$\dfrac=2520$.

题目 17
(i) $C(10+5-1,5-1)=1001$.

(ii) $C(10+5-1-5,5-1)=126$.

题目 18
(i)我们设函数的定义域是那$6$位妖精,值域是四种项目,函数的映射关系是$A$的成绩是$B$,由于四种项目都会有人,所以说这个函数是满射,自然不可能是单射.

(ii)我们利用容斥定理进行分析,首先$6$位妖精随机分配成绩,可能性有$4^6$ 种,接着是仅有三种项目有人,有一种项目一个人都没有,情况有$3^6 \times 4$ 种,接着就是仅有项目有人,有两种项目一个人都没有,情况有$2^6 \times 6$ 种,接着就是仅有项目有人,有三种项目一个人都没有,有 $4$ 种情况,则根据容斥定理有$1560$种可能.

题目 19
$15$.

题目 20
$f(k)= \left\lfloor \dfrac \right\rfloor ^2 - \sum_^ f(i*k) $.

题目 21
$C(2n,n)-C(2n,n-1)$.

题目 22
略.

题目 23
不可能成立:

构建图模型$G(V,E)$其中边代表朋友关系,点代表人,每个人只和$3$个人做好朋友代表每个点的度为$3$,一共有$5$个人,度的总和为$15$,违反握手定则.

题目 24
因为任何一个点覆盖集的补集都是点独立集,一个点覆盖集可以推出一个点独立集所以说不同的点独立集的数量等于不同的点覆盖集的数量.

题目 25
构建图模型$G(V,E)$其中边代表药品不能放在一块,点代表药品,极大独立点集的是可以放在一起的.

题目 26
(i)边覆盖数:最小的边覆盖所含的边数称为边覆盖数.

边独立数(也称匹配数):最大匹配的边数称为边独立数或匹配数.

(ii)设最大匹配数为$m$,总顶点数为$n$为了使边数最少,又因为一条边最多能干掉两个点,所以尽量用边干掉两个点.也就是取有匹配的那些边,当然这些边是越多越好,那就是最大匹配了,所以先用最大匹配数目的边干掉大多数点.剩下的解决没有被匹配的点,就只能一条边干掉一个点了,设这些数目为$a$,显然,$2m+a=n$,而最小边覆盖$=m+a$,所以最小边覆盖$=(2m+a)-m=n-m$.

题目 27
略.

题目 28
构造一个$2n$个点的二分图,设左边的点集是$1,n$,右边点集$n+1,2n$,对原图中的每一条边 $(x,y)$在新图中加入$(x,n+y)$.

题目 29
构造一个$2n$个点的二分图,设左边的点集是$1,n$,右边点集$n+1,2n$,对原图中的每一条边 $(x,y)$在新图中加入$(x,n+y)$.并对所有的$i \in 1,n$,加入边$(i,i+n)$.

LSC:略.

题目 30
现在写出式子$a_n=a_+a_$,并且有$a_0=0,a_1=1$.

则有$F(x)=xF(x)+x^2F(x)-a_0x+a_1x+a_0$,解得:
$$F(x)=\frac$$
这个时候可以拆成:拆的方法就是令分母$=0$,求出来两个解$x_1,x_2$,然后表示成$\dfrac+\dfrac$,利用待定系数法求出$A$和$B$.因为Taylor展开,我们可以把这个封闭形式转化成一般形式.
$$ \frac=\sum_x^n \frac}\left( \left(\frac}\right)n-\left(\frac{1-\sqrt{5}}{2}\right)n \right) $$
这个时候可以知道$a_n=\dfrac}\left( \left(\dfrac}\right)n-\left(\dfrac{1-\sqrt{5}}{2}\right)n \right)$.

恭喜你完成了所有内容的学习!下面是一些附加的章节,这些章节简单介绍了三个分支的一些基础内容,如果您有更加重要的事,可以不看。

附加章节

Antimage的人工智能入门介绍

给有志于研究人工智能的同学的一个小讲座,如果不感兴趣,可以不看。

基础知识

数学

数学是人工智能的基石,这里主要聚焦与人工智能高度相关的数学分支以供参考。

书籍我只推荐一个《Mathematics for Machine
Learning》,这本书并没有讲很高深的数学,但是吃透了这本书,可以说做AI的数学底子是有了。

机器学习

首先我想讨论一下我眼中的机器学习,机器学习绝对不是简简单单调个库,使用Python完成一个回归或者分类任务就够了,这些过程仅仅只能说明你进行了机器学习的应用,并不能说明你是在真正的学习机器学习。大家都说机器学习和深度学习是黑箱,我认为,了解黑箱的原理、探究黑箱的优化路径、制作出更优秀的黑箱,不失为deep
learning的一个美妙的学习方式。有点扯远了,这里我们先谈机器学习。自己总结不如借用一句精辟的话,机器学习是使用算法解析数据,从中学习,然后对世界上的某件事情做出决定或预测'',第一句话就框定了我们机器学习的核心:数据'',可能你已经听说过``数据和特征决定机器学习的上限,模型和算法只是在逼近这个上限'',没错,数据的清洗和特征工程是机器学习的一个重要且不可或缺的步骤,试想,一堆杂乱的数据,没有经过特征加工,再厉害的模型和算法,或许也难逃出过拟合的魔爪。

数据清洗,特征工程

因此,你可能需要先了解数据清洗和特征工程的流程;

内容:了解数据清洗的常见场景,理解特征工程的意义,掌握特征工程的常用方法,并付诸实践。

推荐学习方式:

了解:推荐博客https://www.mygreatlearning.com/blog/feature-extraction-in-image-processing/

学习:学习机器学习一定不要错过Kaggle,上面有大量各种场景的机器学习/深度学习应用任务,你可以先查看高分选手的代码,掌握数据处理等Pretreatment的方法,然后考虑在自己的任务中应该怎么做并总结经验。此外,并不推荐大家阅读《Python数据分析基础》等书籍,最好的学习方式是上手和总结。由于这是引导性的文章,所以具体方法就不做赘述,下文亦然。

模型选择

第二部分需要分两个部分来讲,一个是认识并学习各种模型,一个是如何选择模型;

Part1:机器学习模型学习:推荐周志华老师的《机器学习》,江湖人称``西瓜书'',配合《机器学习理论导引》,了解模型原理,动笔完成推导;

实践:同样,Kaggle,阿里天池,此外,推荐参加数学建模竞赛,数学建模竞赛可以用上很多机器学习方法以及优化算法,此外,更重要的是数模竞赛中会有各种背景的问题,可以锻炼针对不同处境下问题的解决能力,既能增长自己的技能树,还能拿奖状,何乐不为。

Part2: 如何选择模型:
推荐两个博客,一个是https://www.projectpro.io/article/common-machine-learning-algorithms-for-beginners/202
,这篇博客分析了主流模型,并且给出了适用背景,适合初学了解;

一个是https://towardsdatascience.com/considerations-when-choosing-a-machine-learning-model-aa31f52c27f3,这篇博客从多种角度介绍了模型需要考虑的要点。

此外,最重要的还是多写代码,根据问题类型、模型特点以及实际表现来进行选择。

参数调整

如何在选择好的模型上达到更佳的效果,这大概就是调参的意义,调参其实并不好讲,因为要说常用方法,也并不多,深入一点,需要你对模型的参数有非常深刻的理解,知道某参数的变动大概会影响模型的哪些表现,我觉得调参达到最优效果只有两个因素,经验和时间。

常见的最佳参数搜索方法可以参考该链接:https://programs.wiki/wiki/summary-of-four-parameter-adjustment-methods-in-machine-learning.html

给出了代码示例,可以针对自己的任务进行实践。

深度学习

深度学习的目的是为了能够学习数据的更多本来的规律,最终能让机器拥有类似于人的思考和解决问题的能力。而深度学习里最具有表征意义的就是神经网络,倘若没有神经网络的相关学习经验,你可以这么考虑神经网络的功能并理解它的流程,我们将神经网络简化为一个分类器或者回归器,对于输入数据,经过神经网络内部的传播通路,得到一个输出,在前馈神经网络中,各神经元分层排列,接受前一层的输入,通过数学运算得到输出结果并传递给下一层,最终得到输出结果,以分类任务为例,他可能得到一个表示归属不同类别的概率向量(\vec l),
然而在训练集上这个结果会与真实结果产生差距,不同任务不同背景下会用不同的方式来表征这个``差距'',称为损失函数,然后计算这个损失函数相对于神经网络中各种参数的梯度来进行反向传播,找到使这个损失函数降低的参数修改方法,从而逐步降低损失。

有关深度学习的学习资料众多,这里推荐几个比较好的社区:

https://towardsdatascience.com/

https://machinelearningmastery.com/

https://medium.com/

问答网站:

https://stackoverflow.com/

https://jp.quora.com/

其他学习资料分方向推荐,课程我私心是推荐Stanford University
AI课程全套的,我自己的使用方法是观看课程,完成纸质作业和Colab编程作业,如果对某方向非常感兴趣了,就从该领域的经典论文开始看,如果论文有开源代码,就配合代码进行学习,然后从难度和重要程度等方面精心选择1~2篇进行复现,如果你打算进一步挖掘该领域的奥秘,你可以联系本校或者保研意向学校相关方向的老师,请老师让你加入相关课题组,一般学长学姐会让你先看相关小方向的文献,如何能在课题组中贡献自己的代码并总结一些跑实验的经验就更好了,最佳的结果是你跟着课题组有了Paper产出,即使没有Paper产出或者因为事务繁忙放弃了,这也能成为你的科研经历,写入你的推免简历。

下面对较为火热和我比较了解的方向进行简要介绍和资料分享。

计算机视觉

计算机视觉是研究让机器如何``看''的科学,它的目的是实现代替人眼进行目标的检测、识别等的机器视觉。主要有模式识别,图像分类,图像分割,图像增强,图像生成,风格迁移(风格化)等方向。

推荐课程:Stanford University CS231n, CAP5415 – Computer Vision

经典论文收录:Classic computer vision papers

CV方向相关国际学术会议和期刊:

会议:CVPR, ICCV, ECCV, AAAI, ICML, NeurIPS, ICPR

期刊:IJCV, TPAMI, TIP, PR

自然语言处理

自然语言处理是融合计算机、数学和语言学于一身的科学,它训练机器具有人一样处理和表达语言的能力,主要包括机器翻译、文本分类、阅读理解、问答系统、舆情监测、语音识别、信息提取和因果推断等方向。

推荐课程:Stanford University CS224n

推荐书籍:自动化所宗成庆老师的《统计自然语言处理》

经典论文收录:https://github.com/mhagiwara/100-nlp-papers

NLP方向相关国际学术会议和期刊:

会议:ACL, EMNLP, NACAL, AAAI, ICLR, COLING,

期刊:Computational Linguistics(CL),TACL

图机器学习

图学习是近几年一个比较热门的研究方向,图机器学习以由结点和连接边构成的网络作为数据,通过学习图结构数据来挖掘图上特征和内在模式,在图上,你可以执行node、edge和graph级别的分类任务,或者是missing
edge的预测任务等等,进一步地,图机器学习在知识图谱、推荐系统和社交网络等领域都有广泛的应用。

推荐课程:Stanford University CS224W

经典论文收录:https://github.com/thunlp/GNNPapers

会议:ICML,NeurIPS, ECCV, CVPR, ICLR, IJCAI, AAAI

如果你学习图机器学习,并且有了CS224W的理论基础,那么可以访问Stanford大学的Open Graph Benchmark网站,自己动手用GCN、GraphSAGE、GAT等模型实现一些图上任务,算是一个非常不错的入门GNN的方式。

对抗样本

相较于前面介绍的领域,对抗样本(Adversarial
Example)是贯穿深度学习各种领域的研究方向,对抗样本的思想在于为数据集添加轻微的扰动,从而使得表现优秀的模型输出产生较大的误差,从而挖掘模型尚未学习到的特征,进而通过对抗训练来增进模型的鲁棒性。

对抗样本生成任务自Goodfellow在视觉领域中提出以来就受到了很大的关注,它使得人们对于深度学习模型的安全性产生了诸多思考,同时通过对模型的攻击也让人们对于模型的理解更加深入。而在视觉领域中,由于图像数据的连续性特点,使得其扰动大小能够被精确度量,因此视觉领域的对抗样本生成技术发展较快,反观文本领域,由于文本数据的离散化特性以及语言本身的高度复杂性,使得扰动大小难以衡量,且文本模型本身鲁棒性要高于视觉相关模型,这些都增加了文本对抗本身的难度。

目前,对抗攻击的方式根据掌握信息的程度分为黑盒攻击和白盒攻击,黑盒攻击方法对于模型的参数一无所知,仅仅依靠修改输入并得到反馈输出来进行侦测,而白盒攻击则主要依赖于所期望指向的错误输出对于模型内部参数的梯度来进行攻击,是了解模型内部结构的攻击方式,对于对抗攻击,清华大学thunlp组总结了各个领域的对抗攻击的有代表性的论文,可以针对自己的情况挑选阅读。链接如下:

thunlp/NLP-THU: NLP Course Material & QA (github.com)

由于本人知识广度和深度限制,对于不曾了解和学习的领域不敢擅自定义和指教,如果真的对人工智能感兴趣,那么在按这个路线学习的过程中,你一定会自发地发现自己所感兴趣的领域,并投入其中,收获颇丰。

Deiky的硬件知识介绍

硬件设计基础

注:这部分导论主要查阅了CSDN博主“队长-Leader”的文章。

硬件设计,可以说是包罗万象,它涉及到非常庞大的知识量,一个电路错一点小地方,都有可能导致整个系统不能工作。
本文主要只介绍初级理论篇(电路理论,模拟电路,数字电路)和中级理论篇(信号与系统)。当然在此基础上,高等数学、线性代数、复变函数和大学物理等这些基础课要过关,根基扎实。

就电路理论而言,其实电路基础的理论并不难,但是有些抽象的东西,是暂时不能很好地理解,比如说受控源,所以学完模电还要再回过头来再看一遍。模拟电子技术是电子专业的核心基础课,同时还可以配合Multisim仿真软件加深理解。如果说电路基础、高数当中的答案都是明确、唯一的,那么模电的答案将是不明确、多样化的,需要在实践中权衡取舍,一定要把以前的思维转变过来,不然后面没法学。这门课全部都是重点,但是学完它,除了抄书上的电路,你仍然什么都做不了,因为还需要其它方面的知识一起用才可以。数字电子技术相对于模电来说,要简单很多很多。它把三级管搭成各种门电路、触发器,以便于直接把数学知识运用起来,同时它也是FPGA的先修课,是硬件工程师向算法工程师(跟计算机的算法有很大区别)转变的基础。这门课全部都是重点,但是要真正掌握它,还是得学FPGA才可以。

中级理论篇首先需要依赖更高阶的数学基础(复变函数)。这门课跟高数的微积分一样,是一种数学工具。复数信号是物理不可实现的,但是为什么需要复数?诚然,正弦波(包括余弦,下同)有振幅、频率和相位三要素,如何在一个图上面表示振幅与频率的关系或者相位与频率的关系(方便观察分析才需要这样弄)?这就需要用到复数了,其中$j$(因为电流的符号是$i$,所以才换成$j$,以防混淆)表示的就是方向,对应着极坐标的向量。我们可以把复数转成模和辐角的形式,想象一下,模就是时钟的秒针,而辐角就是秒针转动的角度,秒针转一圈就是个圆,而把这个圆的各点按照出现的时间先后,重新描绘在直角坐标系中,就是一个正弦波。这就意味着,用复数可以表示一个正弦波的三要素,振幅就是模(秒针的长短),相位就是秒针转动的角度,频率就是秒针转动的快慢。想一下,如果用实数来表示正弦波的三要素,是不是很麻烦?信号与系统主要介绍如何利用数学建模去描述电路,就是这门课要研究的内容。什么是信号?LED灯的亮灭、喇叭发出的声音、天线感应的电磁波等,有实际用途的信息载体(包括声、光、电、热等)都是信号。什么是系统?就是处理信息载体的东西(包括放大器、传动装置等)。系统是一种更为抽象的概念,可大可小,小到一个三极管,大到一个无线收发装置,这些都要根据实际需求来确定,不能一概而论。这门课都是重点。当然中级理论还包括高频电子线路、单片机、自动控制原理等等,就不一一介绍了。

电路理论

电路理论课程以分析电路中的电磁现象,研究电路的基本规律及电路的分析方法为主要内容,全面系统地介绍了电路分析的基本原理和基本分析方法。电路理论是当代电工科学技术的重要理论基础之一,它有两个部分组成,电路分析和电路综合。
电路分析研究的直接对象是电路模型,是由实际电路抽象出来的。核心内容有电路模型及其两类约束、等效和替代、线性叠加、选择合适电路变量建立电路方程等。电阻电路是指除电源之外,仅包含有电阻元件的电路,而动态电路则是含有电容、电感等储能动态元件的电路,由于动态元件的特性方程当中含有微分与积分形式,因而动态电路主要采用微分方程进行描述,其中方程的阶数通常取决于动态元件个数。电路分析当中的动态又称为暂态,指电路从一个稳态变化至另一个稳态的中间过渡过程。而稳态也被称为静态,指电路当中的电压、电流等参数达到一个稳定状态,如果其它参数不发生变化,就会一直以该状态运行。无论是分析简单电路,还是分析复杂电路,通常都会遵循如下一系列步骤:1.确定分析目标 2.建立电路模型 3.计算目标变量 4.选择分析方法 5.校验所得结果。

Part 1

一些概念

基本定律

Part 2

电阻电路等效变换

小结

Part 3

电路定理

Part 4

正弦稳态电路的功率

有功功率与无功功率是非常重要的概念,必须深刻理解其物理含义:无源网络吸收的瞬时功率 = 恒为正的消耗功率 + 均值为零的交换功率。电阻吸收的瞬时功率恒大于零,属于消耗功率;
电感、电容吸收的瞬时功率依照正弦变化,属于交换功率;
有功功率等于吸收功率的平均值;无功功率是交换功率的幅值;
为了体现电感、电容的互补性,通常约定电感吸收无功功率,电容发出无功功率。

在无功功率、有功功率概念的基础之上,扩展出了视在功率、功率因数、复功率以及复功率守恒的概念。但是,有功/无功功率才是正弦稳态概念的核心,需要在深刻理解两者概念的基础之上,熟练掌握复功率、视在功率、功率因数与有功/无功功率的关系,并且理解各种功率守恒的意义。

模拟电子技术

学习导论

模拟电子技术(简称模电)是电子、电气、自动化、计算机等相关专业的专业课程,模电和数电是做电路设计相关工作必须掌握的专业知识,模电相对来说确实比较难,比数电要难一些。 模电是一门研究半导体二极管、半导体三极管和场效应管为关键电子器件,包括功率放大电路、运算放大电路、反馈放大电路、信号运算与处理电路、信号产生电路、电源稳压电路等的学科。

模电学习上启电路(电路分析更复杂),下承通信电子线路,要懂得一些管子的知识,像常见的三级管了:NPN,PNP,CMOS管等,了解他们的伏安特性。理解放大原理,常用的放大倍数计算的公式,会画电路的微变电路,弄清楚输入电阻和输出电阻。再一部分就是基本的放大电路:射级放大,集电极放大,基级放大。对电路的分析,知道放大是放大的什么。

很多学生学习模电时感觉很难,模电之所以难,是因为模拟电路形式多种多样,千变万化,而且很多参数计算分析复杂。当然,难和易是相对的,只要自己努力、用心去学,我相信都可以学得好。模电入门阶段一定要弄清楚PN结的结构原理,以及电流形成过程,三极管的电流走向与分配关系等,入门理顺了,后面的学习相对会轻松一些。

后面章节的集成运放、比较器也是必须要掌握的,运放和比较器在电路设计中很常用,一定要熟悉最基本的几种运放电路模型(反相比例放大、同相比例放大、加法器、减法器、差分放大等),会应用运放“虚断”与“虚短”两个重要特性分析运放电路。

学习模电要多看、多思考,课后最好到图书馆结合基本参考书认真复习。课余时间最好多动手实践,多参加一些电子项目设计,比如电子设计竞赛,那是非常锻炼人的竞赛项目,参加电子设计竞赛,特别锻炼人,可以从中学到很多东西。

基本知识

需要掌握的基本知识(非全部):

  1. 直流通路三原则:
  2. 交流电压源短路,交流电流源开路;
  3. 大电容视为开路;
  4. 大电感视为短路。
  5. MOSFET:截止区、饱和区、可变电阻区的判断;
  6. BJT:截止区、放大区、饱和区的判断;
  7. 转移特性曲线、传输特性曲线的理解;
  8. 直流负载线的理解,判断截止失真和饱和失真;
  9. 静态工作点分析、小信号模型分析
  10. 各种放大组态的分析以及多级放大电路分析。多级放大电路的分析思路:
  11. 前一级的输出电阻是后一级的电源内阻;
  12. 后一级的输入电阻是前一级的负载;
  13. 前一级的输出电压后一级的输入电压;
  14. 整体的增益是各级增益的乘积。
  15. 差分放大电路主要概念:
  16. 差模输入(单出、双出、输入电阻);
  17. 共模输入(单出、双出、输入电阻);
  18. 不对称输入;
  19. 带有源负载的差分放大器。
  20. 反馈技巧:
  21. 判断组态;
  22. 计算增益、反馈系数(注意是谁比谁)、闭环电压增益;
  23. 负反馈电路的设计、连接;
  24. 误差分析(失调电压、失调电流)。

数字电子技术

学习导论

数字电子技术(简称数电),是一项与电子计算机相伴相生的科学技术,它是指借助一定的设备将各种信息,包括:图、文、声、像等,转化为电子计算机能识别的 二进制数字 “0”和“1”后进行运算、加工、存储、传送、传播、还原的技术。 主要内容包括数制与逻辑基础、门电路、组合逻辑电路、触发器、时序逻辑电路、脉冲的产生与整形、存储器和可编程逻辑器件、模拟量和数字量的转换等。

模拟电路主要处理模拟信号,不随时间变化。时间域和值域上均是连续的信号,如语音信号。而数字信号则相反,是变化的。数字信号的处理包括信号的采样,信号的量化,信号的编码。我们来举个例子,如果说想从远方传过来一段由小变大的声音,用调幅,模拟信号进行传输(相应的应采用模拟电路),那么在传输过程中的信号的幅度就会越来越大,因为它是在用电信号的幅度特性来模拟声音的强弱特性。但如果采用数字信号传输,就要采用一种编码,每一级声音大小对应一种编码,在声音输入端,每采一次样,就将对应的编码传输出去。与模电相比,数电电路抗干扰能力强,数字信号易存储。联系在于:摸拟电路是为数字电路供给电源而又完成执行机构的执行;在模拟电路和数字电路中,信号的表达方式不同。对模拟信号能够执行的操作,例如放大,滤波,限幅等,都可以对数字信号进行操作。由此可以看出,所有的数字电路从根本上来说都是模拟电路,其基本电学原理,都与模拟电路相同。

基本知识

  1. 逻辑代数与硬件描述语言基础
  2. 组合逻辑电路

逻辑图的分析方法和步骤:
3. 根据逻辑电路图逐级标出表达式,最后写出总的函数表达式
4. 根据函数表达式列出真值表
5. 根据真值表进行功能判断(加减乘除、挑选、奇偶校验等)

根据功能设计逻辑图:
6. 根据要求确定输入、输出变量,然后列出符合要求的真值表
7. 根据真值表得到相对简单的逻辑表达式
8. 根据逻辑表达式画出逻辑电路图
9. 时序逻辑电路

同步电路的分析与设计
10. 分析:1.根据电路列出各逻辑方程组列出转换表或状态表 2.画出状态图和时序图 3.得到电路的逻辑功能
11. 设计:1.根据逻辑功能的需求 2.推导原始状态图或原始状态表 3.确定激励方程组和输出方程组画出逻辑图
12. 检查电路自启动以及输出信号是否正确

设计异步电路的波形图:1.列出各逻辑方程组 2.列出转换表、画出状态图 3.画出波形图
13. 其他知识点(非全部)
14. 逻辑门电路:CMOS集成电路——超大、甚大规模集成电路;TTL集成电路——中大规模集成电路(已淘汰)
15. 锁存器和触发器:状态图、特性表、特性方程;各种触发器的功能和作用

信号与线性系统

信号与系统是很多基础课的基础课,诸如通信原理,数字信号处理,语音信号处理,数字图像处理,自适应滤波器理论,这些课想学会都必须以信号与系统学好为前提。信号与系统的应用不止这些,和香农的信息理论挂钩,它还可以用于信息处理(声音,图像),模式识别,智能控制等领域。如果说,计算机专业的课程是数据表达的逻辑模型,那么信号与系统建立的就是更底层的,代表了某种物理意义的数学模型。信号与系统更是作为广大院校IT类专业考研的必考科目。因此本科目知识体量非常庞大,难以速成。笔者囿于水平,在基本章节介绍的基础上又以问答方式提炼收集了一些重要概念,希冀起到抛砖引玉的作用,能激发大家自己去探索学习的欲望。

注:章节顺序安排以奥本海姆的书的顺序排布(强烈推荐此书)。

信号与系统简介

消息是信号传递的内容,信号是消息的物理载体(电,光,热等),数学上的体现就是函数,信息是消息中所包含的不确定性。所谓信号处理就是对表示物理量的函数进行处理,调制解调,变频,滤波等对函数的操作都算是信号处理。信息获取、变换、存储、传输、交换都离不开以信号为载体。信息处理主要位于系统的顶层,比如目标检测,人体跟踪都是在进行信息处理,就是对信号中的信息利用的过程。

  1. 信号的能量与功率

能量计算式:
$$
\begin
&E=\int_{+\infty}|x(t)| \mathrm \
&E=\sum_{+\infty}|x[n]|
\end

$$

当上述积分式和无穷级数不绝对收敛时,我们认为信号的能量是无穷的,有限能量的信号通常称为能量信号。

功率计算式:
$$
\begin
P=\left(\frac \int_{T}|x(t)| \mathrm\right) \
P=\left(\frac \sum_{N}|x[n]|\right)
\end

$$

可以看到,能量信号在无穷区间上的平均功率必然为零,有限功率的信号记做功率信号。

在信号与系统涉及的范围内,我们认为周期信号均是功率信号,而非周期信号按幅度和持续时间是否无限可分为三类,持续时间有限的都是能量信号,持续时间无限而幅度有限的信号是功率信号。

在电路理论已经初步接触过冲激响应。冲激响应怎么理解?冲激响应是系统在单位冲激信号的作用下而引起的零状态响应。一个信号可以分解为不同时延的冲激信号的叠加,这样一个信号在经过一个系统处理之后就可以看做是很多不同时延的冲击信号经过了这个系统,这样可以大大简化我们对系统响应的计算!冲激信号实际上是一个理论模型,并不能实际存在,表示在瞬间激发出无穷大的脉冲。

因果系统就是输出不会超前如输入,稳定系统就是输入有限输出也有限的系统,线性系统当输入为输入的线性组合时,输出为对应输出的线性组合。时不变系统指的是输出与输入作用时刻无关的系统。
2. LTI系统

整个LTI系统实际上就是在讲卷积。卷积法的原理是将信号分解为冲击信号之和,然后借助系统的冲击响应求解系统对任意激励信号的零状态响应。

什么是零状态响应、零输入响应和完全响应?,在研究微分方程和差分方程的系统时,分清此二者非常重要。

零状态响应:是指我们的系统初始状态为零,仅有外部激励作用而产生的响应。从电路上看就是电路的储能元器件没有初始储能,仅有外部输入而产生的输出。零输入响应:是指系统没有输入仅有初始状态而产生的响应。完全响应就是上面两者的综合,系统有外部激励同时也有初始状态而产生响应。

线性时不变系统的特性?

(Linear Time—Invariant)叠加性和均匀性,时不变特性,微分特性。
3. 周期信号的傅里叶级数

课本是用了两章分别讲连续和离散的傅里叶,事实上它们几乎相同,反而是傅里叶级数和傅里叶变换之间的区别需要重点掌握,因此本文还是将连续和离散放在一起说,把级数和变换拆开。这一章要背的并不多,因为下一章的傅里叶变换会包括本章的内容,这里就重点理解为什么要引入傅里叶变换和感受这个过程即可。傅里叶变换与傅里叶级数关系在于:傅里叶变换是在傅里叶级数正交函数展开的基础上发展而产生的,这一方面的问题也被称为傅里叶分析。在分析周期信号时,可以用傅里叶级数也可以用傅里叶变换,傅里叶级数就相当于傅里叶变换的一种特殊表现形式。

吉伯斯现象了解一下即可。
4. 非周期信号的傅里叶变换

上节提到的傅里叶级数仅仅只能对周期信号进行分析,事实上很多信号都是非周期的.随着信号周期的增大,离散的谱线会越来越密集。我们就想到一种可能,非周期信号可以理解为周期无穷大的信号,而T增大到无穷时谱线会密集到成为为连续函数,事实上这确实是正确的,也就是说,我们通过增大周期来逼近非周期信号,最后取极限得到最终非周期信号的结果。

周期非周期,连续离散,时域频域的关系:
5. 时域周期必定频域离散(周期信号的傅里叶级数);
6. 时域非周期必定频域连续(非周期信号的傅里叶变换);
7. 时域离散必定频域周期(离散信号的变换有2π周期);
8. 时域连续必定频域非周期(连续信号的变换都是无限区间无周期的);
课本上的相关、能量谱、功率谱是随机信号的重点,小波变换是高级DSP的重点,DFT和圆周卷积是DSP的重点,这些可以都先不看。

抽样定理 —— 为了从抽样信号中回复原连续信号,需要什么条件?

首先模拟信号(时间幅值都连续)、抽样信号(时间离散、幅值连续)、数字信号(时间幅值均离散)。最低抽样频率为$2f_m$。但为什么正弦波无法利用频率的2倍进行采样?答:角度一:在载频处发生了频谱混叠。角度二:相当于用正弦波对冲激串进行调制,只改变了冲激串的幅度,所以无法反推出原信号
9. 频率响应

全通函数和最小相移函数:全通函数的极点零点左右对称,成镜像。全通网络可以保证不改变信号的幅度频域特性,只改变相位频域特性;最小相移函数零点仅位于左半平面。

影响频率分辨率的因素有哪些?
答:两种定义:1.区分两个谱峰的能力,用来评判不同算法性能;2.频谱最小的频率间隔。
影响因素:1.信号有效长度N。N越大,频率分辨率越高。2.所加的窗函数。不同的窗函数有不同的主瓣宽度。(简而言之:和信号截断的时刻以及方式有关)
频率分辨率的理解:不改变频谱形状的变化都不能改变物理频率分辨率。(补零,有效时间T不变,所以不改变频率分辨率)
10. 拉普拉斯变换

当复指数不再限于纯虚数时,即$s=\sigma+jω$时,就由傅里叶变换变成了拉普拉斯变换,也就是说傅里叶变换是拉普拉斯变换的一个特殊情况。

那么为什么要引申到拉普拉斯变换呢,这是因为狄利克雷条件的绝对可积几乎只有衰减信号才能满足,而引入拉普拉斯变换之后,复数$s$的实部$\sigma$乘在信号上可能会使原本不绝对可积的信号满足条件从而可以变换,扩大了变换的适用范围。

拉氏变换的优点及傅氏变换的区别:拉氏变换将微分与积分运算转换成了乘法和除法运算,把微分方程转换成了代数方程,计算起来方便;拉氏变换对于处理指数函数,超越函数以及由不连续点的函数有很大便利。拉氏变换与傅氏变换的基本区别:傅氏变换是将时域信号转换到频域或者进行相反的变换,时域变量或者频域变量都是实数;拉氏变换是将时域信号转换到复频域或者进行相反变换,时域变量是实数,但是复频域变量是复数。简单来说,傅氏变换建立的是时域和频域的关系,而拉氏变换建立的是时域和复频域的关系。

双边拉氏变换的优点:信号不必局限在$t>0$的范围内,双边拉氏变换与傅里叶变换的联系更紧密,准确来说,双边拉氏变换是广义的傅里叶变换。当然,由于实际中的信号都是在$t>0$时才出现,因此下面的单边拉普拉斯变换式更加常用。

注意:拉氏变换的收敛域非常重要,同一个拉普拉斯变换$X(s)$,收敛域不同,其对应的时域函数$x(t)$就不同。
收敛域满足如下几条规则
11. 收敛域必然是平行于虚轴的带状区域
12. 若X(s)有理则收敛域不包括任何极点
13. 若x(t)有限时长或绝对可积,则在整个s平面上收敛
14. 右边信号(t从某一值延伸到正无穷)的收敛域为最右极点的右侧;左边信号(t从某一值延伸到负无穷)的收敛域为最左极点的左侧;双边信号收敛域不延伸到无穷,而是被某两个极点限制。
15. Z变换

与连续傅里叶变换扩展为拉普拉斯变换类似,离散的也可以扩展为Z变换,其意义和拉普拉斯变换差不多。
与离散时间傅里叶变换的关系。显然当$z=e^$时Z变换成为傅里叶变换,也就是$z$平面上半径为1的单位圆,也就是说,相比于拉普拉斯变换是在纯虚数的基础上添加了实部,Z变换是在单位模值复数的基础上乘了倍。
注意:收敛域同样非常重要,也会导致时域函数不同。

什么是特征函数?(联系线代学的知识:什么是特征值,特征向量)
答:特征函数其实有两种定义。一般指的是在《信号与系统》中所学的那个定义,即特征函数通过一个线性系统,输出为某一常数乘以该特征函数,该常数称作特征值。对于傅里叶变换,拉式变换,Z变换而言,它们的特征函数就是变换的基。

回顾与展望

看完上面的章节,你对基础的硬件知识有了一定的了解,然后硬件时需要集成的,下面给出了推荐的学习路径和学习知识。

  1. 按顺序,了解上面四节的知识,如果您学有余力,可以考虑在大二上学期结束的时候全部了解,当然,大二下学习再了解也不迟。

  2. 学习基本的软件知识,对于上层操控硬件的软件,了解C语言和汇编语言的语法就足够了。

  3. 在大三的时候选择一块单片机尝试去进行开发,对单片机进行控制可以帮助你更好地组合之前的电路知识,并了解集成电路的特性和结构。

在了解了基础的知识之后,你可以尝试阅读相关的书籍增进了解。

相关书籍:

  1. 基础理论知识:
  2. 电路分析基础(李瀚荪),这本书是教材,对于底子薄的同学,还是建议先看看的,主要是一些电路分析的定理、转换方式等。
  3. 像微机原理、线性电子电路、非线性电子电路、高频电子线路这些教材都建议看看。
  4. 模拟电路设计:
  5. 教材推荐《模拟电子技术基础》(华成英)。
  6. 模拟电路相比较数字电路,有点晦涩难懂,除了国内的教材外,也推荐读一读国外的一些书籍,如《晶体管电路设计》(铃木雅臣),《你好,放大器》(杨建国)。
  7. 数字电路设计:
  8. 《数字电子技术基础》(第六版,阎石),数字电路基础是电子专业必修课,高校教材内容也都是大差不差的,也可以看华成英的第五版。
  9. 如果是走FPGA/CPLD路线,需要学Verilog语言,可以看《Verilog数字系统设计教程》(夏宇闻)。
  10. 电源设计:《精通开关电源设计》(Sanjaya Maniktala著,王健强等译)。

附加数学知识

对于这一部分,仅供参考阅读,可以暂时先不阅读

凸优化

若你对人工智能(尤其是机器学习、深度学习)感兴趣,凸优化是核心理论工具之一——它不仅为模型训练(如线性回归、支持向量机)提供高效求解框架,也为有限状态机的性能优化(如状态转移代价最小化)提供数学支撑,是连接理论与工程落地的关键桥梁。

凸优化问题的基本形式

凸优化的核心是“目标函数为凸函数”且“约束条件构成凸集”,其标准形式清晰区分了约束类型,便于后续转化与求解:
$$
\begin
\min_ F(x) \quad &\text \
\text \quad &\begin
f_i(x) \leq 0 \quad (i=1,2,\dots,m) \quad \text \
A\mathbf + \mathbf = 0 \quad \text
\end
\end
$$

在计算机科学中,该形式广泛应用:例如机器学习中“最小化模型预测误差”需满足“参数非负”(不等式约束),控制领域“最小化系统能耗”需满足“状态方程”(等式约束),凸性保证了找到的局部最优解即为全局最优解,避免工程落地中的“最优值陷阱”。

拉格朗日乘子法:等式约束的求解核心

拉格朗日乘子法是解决“含等式约束优化问题”的经典工具,即便未系统学习凸优化,也常通过微积分课程接触其思想——核心是将“约束条件融入目标函数”,转化为无约束优化问题。

以二元函数为例:求$f(x,y)$在等式约束$g(x,y)=0$下的极值,可构造拉格朗日函数:
$$
\mathcal(x,y,\lambda) = f(x,y) + \lambda \cdot g(x,y)
$$

其中$\lambda$为拉格朗日乘子,用于“权衡约束与目标的重要性”。求解时只需对$x,y,\lambda$分别求偏导并令其为0,解方程组即可得到极值点:
$$
\frac} = 0,\quad \frac} = 0,\quad \frac} = 0
$$

在计算机领域,该方法是线性回归、PCA(主成分分析)等模型求解的基础——例如PCA中“最大化方差”需满足“投影方向单位化”的等式约束,正是通过拉格朗日乘子法推导得到特征值分解的求解路径。

KKT条件与对偶问题:不等式约束的泛化与简化

拉格朗日乘子法仅适用于等式约束,而实际问题(如支持向量机的软间隔约束、神经网络的参数正则化)常含不等式约束,KKT(Karush-Kuhn-Tucker)条件正是其泛化,通过“引入带符号的KKT乘子”处理不等式约束。

  1. KKT条件的核心思想
    对于含不等式约束$g_i(x) \leq 0$($i=1,\dots,m$)和等式约束$h_j(x)=0$($j=1,\dots,n$)的优化问题,KKT乘子需满足“互补松弛性”:
    $$
    \alpha_i \geq 0,\quad \alpha_i \cdot g_i(x) = 0 \quad (i=1,\dots,m)
    $$

其物理意义是:若约束$g_i(x) < 0$(未激活),则乘子$\alpha_i=0$(约束不影响目标);若约束$g_i(x)=0$(激活,即极值点在约束边界),则$\alpha_i > 0$(约束起作用)。

此时构造的拉格朗日函数为:
$$
\mathcal(x,\alpha,\beta) = F(x) + \sum_^m \alpha_i g_i(x) + \sum_^n \beta_j h_j(x)
$$

完整KKT条件包含5个部分(目标函数梯度为0、等式约束满足、不等式约束满足、乘子非负、互补松弛),是“凸优化问题极小点的必要条件”——即极小点必满足KKT条件,若目标函数凸且约束为凸集,则KKT条件也是充分条件。

2.对偶问题:简化求解的关键技巧

将原始优化问题转化为“对偶问题”,是凸优化中降低求解难度的核心思路——尤其当原始问题变量维度高(如深度学习模型的百万级参数)时,对偶问题可能因变量更少而更易计算。

对偶问题的构造逻辑是:先对拉格朗日函数$\mathcal(x,\alpha,\beta)$关于$x$求极小值(固定$\alpha,\beta$),得到“对偶函数”$G(\alpha,\beta) = \min_x \mathcal(x,\alpha,\beta)$;再对$G(\alpha,\beta)$关于$\alpha,\beta$求极大值(满足$\alpha \geq 0$),即:
$$
\max_ G(\alpha,\beta) \quad \text \quad \alpha_i \geq 0 \quad (i=1,\dots,m)
$$

关键性质是“弱对偶性”:对偶问题的最优值$\leq$原始问题的最优值;若满足KKT条件,則“强对偶性”成立(两者最优值相等)。在计算机科学中,支持向量机(SVM)正是通过对偶问题将“高维特征空间的分类问题”转化为“低维的对偶变量求解”,避免了高维计算的复杂度。

信息论:数据处理与模型设计的理论基石

信息论由香农(Claude Shannon)创立,核心是“量化信息的不确定性与传递效率”,如今已成为机器学习、数据压缩、通信协议设计的核心理论工具——例如决策树的特征选择、熵编码(如Huffman编码)、深度学习的交叉熵损失函数,均源于信息论的基本思想。

信息熵:衡量不确定性的核心指标

信息熵(Information Entropy)用于量化“随机变量的不确定性”——不确定性越高,熵越大;若结果确定(如必然事件),熵为0。

对于样本集合$S$,若其划分为$k$个类别,第$k$类的概率为$p_k$(满足$\sum_^K p_k = 1$),则信息熵定义为:
$$
H(S) = -\sum_^K p_k \log_2 p_k
$$

对数以2为底时,熵的单位为“比特(bit)”。在计算机领域,信息熵是决策树(如ID3算法)选择特征的核心依据——例如判断“是否使用‘年龄’特征划分数据集”,需先计算数据集的初始熵,再对比划分后的熵减幅,熵减越多说明该特征对降低不确定性越有效。

信息增益与增益率:特征选择的量化标准

信息增益(Information Gain)是“原始数据集熵”与“按某特征划分后的条件熵”的差值,用于衡量“该特征降低不确定性的能力”。

设按特征$A$将数据集$S$划分为$v$个子集$A_1,A_2,\dots,A_v$,则特征$A$的条件熵(划分后的平均熵)为:
$$
H(S|A) = \sum_^v \frac H(A_i)
$$

其中$\frac$是子集$A_i$的样本占比。信息增益定义为:
$$
Gain(A) = H(S) - H(S|A)
$$

增益率(Gain Ratio)则是为解决“信息增益偏向多取值特征”的问题(如“身份证号”特征划分后熵极低,但无实际意义),引入“特征自身的熵”进行归一化:
$$
GainRatio(A) = \frac
$$

其中$H_A(S) = -\sum_^v \frac \log_2 \frac$是特征$A$的取值熵。C4.5算法正是用增益率替代信息增益,避免了决策树过度拟合“多取值噪声特征”。

基尼指数:分类纯度的另一度量

基尼指数(Gini Index)是衡量“数据集分类纯度”的另一指标,与信息熵作用类似,但计算更简洁(无需对数运算),是CART决策树的特征选择依据。

对于含$n$个类别的数据集$S$,第$k$类的概率为$p_k$,基尼指数定义为:
$$
Gini(S) = 1 - \sum_^n p_k^2
$$

其物理意义是“随机抽取两个样本,类别不同的概率”——基尼指数越小,数据集纯度越高。在工程实现中,基尼指数的计算效率高于信息熵,因此CART树(可处理分类与回归问题)更常采用其作为分裂准则,降低决策树训练的时间复杂度。

数值分析:计算机求解连续优化问题的工程方法

数值分析是“用离散化方法求解连续数学问题”的学科,核心是设计高效、稳定的算法,解决“无法通过解析法(如求导解方程)得到精确解”的工程问题——在计算机科学中,机器学习的模型训练(如神经网络的参数更新)、科学计算(如流体模拟)、信号处理(如滤波)均依赖数值分析算法,其中梯度下降与牛顿法是最基础、最常用的两种优化算法。

梯度下降法:机器学习的“基石优化器”

梯度下降是求解“无约束连续优化问题”的迭代算法,尤其适合高维问题(如深度学习的千万级参数优化),核心思想是“沿梯度反方向迭代,逐步逼近极小值”,因其原理直观、计算量小,成为机器学习中应用最广泛的优化方法。

(1)梯度的定义与物理意义

对于$n$元函数$F(\mathbf)$($\mathbf = (x_1,x_2,\dots,x_n)^T$),梯度是由各偏导数构成的向量:
$$
\nabla F(\mathbf) = \left( \frac, \frac, \dots, \frac \right)^T
$$

梯度的物理意义是“函数值增长最快的方向”,因此“沿梯度反方向($-\nabla F(\mathbf)$)移动”,能最快降低函数值,这正是梯度下降的核心逻辑——可类比“爬山找谷底”:每次沿当前位置最陡的下坡方向走一步,逐步抵达谷底。

(2)梯度下降的迭代公式

设迭代步长(学习率)为$\alpha$(控制每次移动的距离,需人工或自适应调整),则第$t+1$次迭代的参数更新公式为:
$$
\mathbf_ = \mathbf_t - \alpha \cdot \nabla F(\mathbf_t)
$$

学习率$\alpha$的选择至关重要:$\alpha$过大会导致迭代震荡(无法收敛),$\alpha$过小则收敛过慢(训练耗时)。现代优化器(如Adam、SGD+Momentum)均通过“自适应调整学习率”优化这一问题。

(3)梯度下降的变体与工程应用

根据“每次迭代使用的样本量”,梯度下降可分为三类,适配不同的工程场景:

批量梯度下降(BGD):每次用全部样本计算梯度,收敛稳定但数据量大时(如百万级样本)计算缓慢,适合小数据集;

随机梯度下降(SGD):每次用1个样本计算梯度,计算快但震荡大,适合大规模数据集的快速迭代;

小批量梯度下降(MBGD):每次用$b$个样本(如$b=32,64$)计算梯度,平衡收敛稳定性与计算效率,是深度学习训练的主流选择(如PyTorch、TensorFlow的默认优化器输入为“批次样本”)。

梯度下降的核心问题是“易陷入局部极小值”(如非凸函数的损失曲面存在多个谷底),工程中常通过“多组初始值迭代”“加入动量(Momentum)模拟惯性”等方法缓解,确保模型收敛到较优解。

牛顿法:二阶优化的高效工具

牛顿法(Newton's Method)是“利用二阶导数(Hessian矩阵)加速收敛”的优化算法,核心是“用二次函数近似目标函数的局部曲面”,迭代步数远少于梯度下降(一阶算法),但计算复杂度更高,适合中低维问题(如逻辑回归、支持向量机)。

(1)牛顿法求解方程的原始形式

牛顿法最初用于求解“非线性方程$f(x)=0$”,核心是“用切线近似函数曲线”,迭代公式为:
$$
x_ = x_t - \frac
$$

例如解方程$x^2 - 3 = 0$(即求$\sqrt$的近似值):取初始值$x_0=2$,计算$f(2)=1$、$f'(2)=4$,则$x_1=2 - 1/4=1.75$;再迭代一次得$x_2 \approx 1.732$,已接近真实值,收敛速度远快于梯度下降。

(2)牛顿法用于优化问题的扩展

若将牛顿法用于“最小化目标函数$F(\mathbf)$”,则需转化为“求解梯度为0的方程”(因极值点满足$\nabla F(\mathbf)=0$)。此时用二阶泰勒展开近似$\nabla F(\mathbf)$,可得迭代公式:
$$
\mathbf_ = \mathbf_t - \left( \nabla^2 F(\mathbf_t) \right)^ \cdot \nabla F(\mathbf_t)
$$

其中$\nabla^2 F(\mathbf_t)$是$F(\mathbf)$在$\mathbf_t$处的Hessian矩阵($n \times n$矩阵,元素为$\frac$),$\left( \nabla^2 F(\mathbf_t) \right)^$是Hessian矩阵的逆。

(3)牛顿法的工程权衡

牛顿法的优势是“收敛快”(二阶收敛),但劣势也明显:Hessian矩阵的计算与求逆复杂度为$O(n^3)$,当$n$较大(如$n>1000$)时,计算成本极高——因此牛顿法更适合中低维优化问题(如逻辑回归的参数求解),而高维问题(如深度学习)仍以梯度下降及其变体为主。工程中常通过“拟牛顿法(如BFGS、L-BFGS)”近似Hessian矩阵的逆,在收敛速度与计算成本间取得平衡。

形式语言与自动机理论

形式语言与自动机理论是计算机科学的理论基础,研究符号串的集合(语言)及其识别模型(自动机),为编译原理、程序设计语言、人工智能等领域提供理论支撑。

基本概念

定义:字母表与字符串

  • 字母表($\Sigma$):非空有限符号集合,如$\Sigma = {0,1}$或$\Sigma = {a,b,c}$。
  • 字符串:字母表中符号的有限序列,如$\Sigma = {0,1}$时,$0110$是合法字符串。
  • 空串($\varepsilon$):不含任何符号的字符串。
  • 字符串长度:所含符号的个数,记为$|w|$,如$|0110|=4$,$|\varepsilon|=0$。

定义:语言
给定字母表$\Sigma$,语言$L$是$\Sigma$上所有字符串构成集合的子集,即$L \subseteq \Sigma*$,其中$\Sigma*$表示$\Sigma$上所有字符串(包括空串)的集合。

Chomsky文法体系

Chomsky将文法分为四类,对应不同表达能力的语言,构成层次结构:

  1. 0型文法(无限制文法)
    产生式形式:$\alpha \to \beta$,其中$\alpha, \beta$为字符串且$\alpha \neq \varepsilon$。
    对应语言:递归可枚举语言,由图灵机识别。
  2. 1型文法(上下文有关文法)
    产生式形式:$\alpha A \beta \to \alpha \gamma \beta$,其中$A$为非终结符,$\gamma \neq \varepsilon$。
    特点:推导中符号长度不减少,对应线性有界自动机。
  3. 2型文法(上下文无关文法)
    产生式形式:$A \to \gamma$,其中$A$为非终结符,$\gamma$为字符串。
    应用:多数程序设计语言的语法定义,由下推自动机识别。
  4. 3型文法(正则文法)
    产生式形式:$A \to aB$或$A \to a$(右线性),其中$A,B$为非终结符,$a$为终结符。
    对应语言:正则语言,由有限自动机识别,应用于词法分析、文本匹配。

自动机模型

自动机是识别语言的抽象计算模型,核心是状态转换机制:

  1. 有限自动机(FA)
    由状态集、输入字母表、转换函数、起始状态和接受状态集组成,分两类:
  2. 确定有限自动机(DFA):每个状态对每个输入符号有唯一转换。
  3. 非确定有限自动机(NFA):允许状态转换的不确定性(含$\varepsilon$-转换)。
    功能:识别正则语言,应用于正则表达式匹配、词法分析器设计。
  4. 下推自动机(PDA)
    在有限自动机基础上增加栈存储,用于处理上下文无关文法,是语法分析的理论模型。
  5. 图灵机(TM)
    由无限纸带、读写头和状态控制器组成,是计算理论的基础模型,可模拟任意算法过程,对应0型文法。

应用领域

形式语言与自动机理论是计算机科学的基石,具体应用包括: