USACO讲义合集
上古时期USACO编程讲义，可用于编程或ACM基础学习，分享交流需要上传，侵删。
Theory Of Computation
网络资源，仅为分享。
Introduction to Theory of Computation
Contents
Preface vi
1 Introduction 1
1.1 Purpose and motivation . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Complexity theory . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Computability theory . . . . . . . . . . . . . . . . . . . 2
1.1.3 Automata theory . . . . . . . . . . . . . . . . . . . . . 3
1.1.4 This course . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Mathematical preliminaries . . . . . . . . . . . . . . . . . . . 4
1.3 Proof techniques . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Direct proofs . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.2 Constructive proofs . . . . . . . . . . . . . . . . . . . . 9
1.3.3 Nonconstructive proofs . . . . . . . . . . . . . . . . . . 10
1.3.4 Proofs by contradiction . . . . . . . . . . . . . . . . . . 11
1.3.5 The pigeon hole principle . . . . . . . . . . . . . . . . . 12
1.3.6 Proofs by induction . . . . . . . . . . . . . . . . . . . . 13
1.3.7 More examples of proofs . . . . . . . . . . . . . . . . . 15
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 Finite Automata and Regular Languages 21
2.1 An example: Controling a toll gate . . . . . . . . . . . . . . . 21
2.2 Deterministic finite automata . . . . . . . . . . . . . . . . . . 23
2.2.1 A first example of a finite automaton . . . . . . . . . . 26
2.2.2 A second example of a finite automaton . . . . . . . . 28
2.2.3 A third example of a finite automaton . . . . . . . . . 29
2.3 Regular operations . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4 Nondeterministic finite automata . . . . . . . . . .
JW-Computer-Principles-Design-Verilog
verilog设计讲义 JW-Computer-Principles-Design-Verilog.pdf JW-Computer-Principles-Design-Verilog.pdf JW-Computer-Principles-Design-Verilog.pdf
信息技术与课程整合理论考核15套
9.信息技术对阅读能力的新要求是______。
A. 电子化的阅读能力和快速阅读的能力
B. 超文本的阅读能力和信息筛选的能力
C. 电子化的阅读能力和信息理解的能力
D. 非线性的阅读能力和有感情阅读的能力(1分）
正确答案:A
10.WebQuest是美国圣地亚哥州立大学的______等人于1995年开发的一种课程计划。
A. 杜威
B. 布鲁纳
C. 斯金纳
最小生成树算法及其应用
最小生成树是图论中的经典问题,也是一个重要部分，一般书上往往只介绍求最小生成树的算法，而忽略了更精彩的算法应用部分。本文将对最小生成树算法及其应用作全面的分析说明，使大家对此有更加深刻的认识。本文分三部分：一、基础篇，主要介绍基础概念、求最小生成树的一般算法和常用算法。二、应用篇，具体问题具体分析，侧重于思考和证明的过程。三、总结
算法设计沙龙---几何算法套餐
你了解几何吗？你了解几何算法吗？我们的沙龙将带领你进入几何的世界，进入计算机处理几何问题的领域。先请你思考以下几个问题，试试看你能否解决？
一、判断点在多边形中的位置
已知点P的X、Y坐标和一个N边形A1A2…An。判断点P在N边形的内部,外部或边上。
输入：
第1行输入N；
第2行至第N+1行输入N边形各点的X、Y坐标
解题训练 蛇形矩阵.doc
WORD 一个简单题：
输入正方形数字矩阵边长 a，，如样例所示规律，输出矩阵（不要求对齐，每行每个数分别用一个空格格开）。
样例：
输入： 4
输出：
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4
输入： 5
输出：
13 14 15 16 1
12 23 24 17 2
11 22 25 18 3
10 21 20 19 4
9 8 7 6 5
输入： 6
输出：
16 17 18 19 20 1
15 30 31 32 21 2
14 29 36 33 22 3
13 28 35 34 23 4
RSS订阅
226
