程序理论_计算机基础理论_计算机类_最新资料_得益网

Programming Languages: Application and Interpretation

2008-11-05 06:56:12

This book is the primary text for Brown University’s course cs173. This course is intended for junior and
senior (3rd and 4th year) undergraduates, as well as beginning graduate students. In practice, the course
enrollment includes some outstanding sophomores as well as advanced graduate students.
The course and book are my attempt to synthesize two conflicting traditions of teaching programming
languages: through interpreters and by survey. I believe interpreters are a superior framework for understanding,
but surveying languages makes them more tangible, resulting in bottom-up learning. In an ideal
world, we would have time enough to oer both courses and, the survey course, being rid of the need to
teach programming language principles, would show students how to really use dierent languages powerfully:
“in anger”, as Phil Wadler would say. This book is a compromise wherein every feature is either
explicitly or implicitly driven by experience, with use preceding implementation.
Design Principles
? Concepts like design, elegance and artistic sensibility are rarely manifest in computer science courses;
in the name of not being judgmental, we may be running the risk of depriving our students of judgment
itself. We should reverse this trend. Students must understand that artificial objects have their
own aesthetic; the student must learn to debate the tradeos that lead to an aesthetic. Programming
languages are some of the most thoroughly designed artifacts in computer science. Therefore, the
study of programming languages oers a microcosm to study design itself.
? The best means we have to lead students to knowledge is through questions, not answers. The best
education prepares them to assess new data by confronting it with questions, processing the responses,
and iterating until they have formed a mental model of it. This book is therefore structured more like
a discussion than a presentation. It leads the reader down wrong paths (so don’t blindly copy code
from it!). It allows readers to get comfortable with mistaken assumptions before breaking them down
systematically.
? The programming languages course is one of the few places in the curriculum where we can tease
out and correct our students’ misconceptions about this material. They are often misled on topics
such as eciency and correctness. Therefore, material on compilation, type systems and memory
management should directly confront their biases. For instance, a presentation of garbage collection
that does not also discuss the trade-os with manual memory management will fail to address the
prejudices students bear.
iii
iv PREFACE
Background and Prerequisite
This book assumes that students are comfortable reasoning informally about loop invariants, have modest
mathematical maturity, and are familiar with the existence of the Halting Problem. At Brown, they have all
been exposed to Java but not necessarily to any other languages (such as Scheme).
Supplementary Material
There is some material I use in my course that isn’t (currently) in this book:
preparation in Scheme For the first week, I oer supplementary sessions that teach students Scheme. The
material from these sessions is available from my course Web pages. In addition, I recommend the
use of a simple introduction to Scheme, such as the early sections of The Little Schemer or of How to
Design Programs.
garbage collection I have provided only limited notes on garbage collection because I feel no need to oer
my own alternative to Paul Wilson’s classic survey, Uniprocessor Garbage Collection Techniques. I
recommend choosing sections from this survey, depending on student maturity, as a supplement to
this text.
model checking I supplement the discussion of types with a presentation on model checking, to show
students that it is possible to go past the fixed set of theorems of traditional type systems to systems
that permit developers to state theorems of interest. I have a pre-prepared talk on this topic, and would
be happy to share those slides.
Web programming Before plunging into continuations, I discuss Web programming APIs and demonstrate
how they mask important control operators. I have a pre-prepared talk on this topic, and would
be happy to share those slides. I also wrap up the section on continuations with a presentation on
programming in the PLT Scheme Web server, which natively supports continuations.
articles on design I hand out a variety of articles on the topic of design. I’ve found Dan Ingalls’s dissection
of Smalltalk, Richard Gabriel’s on Lisp, and Paul Graham’s on both programming and design the
most useful.
logic programming The notes on logic programming are the least complete. Students are already familiar
with unification from type inference by the time I arrive at logic programming. Therefore, I focus on
the implementation of backtracking. I devote one lecture to the use of unification, the implications
of the occurs-check, depth-first versus breadth-first search, and tabling. In another lecture, I present
the implementation of backtracking through continuations. Concretely, I use the presentation in Dorai
Sitaram’s Teach Yourself Scheme in Fixnum Days. This presentation consolidates two prior topics,
continuations and macros.
I also have material on programming in Haskell (written by Greg Cooper) and on the lambda calculus
(transcribed by Don Blaheta) that I will incorporate in a future version of this text.
v
Exercises
In addition to several exercises sprinkled throughout the book (under the banner of “Puzzles”), there are
numerous homework exercises and exams available from my course’s Web pages (where hyeari is one of
2000, 2001, 2002 and 2003):
http://www.cs.brown.edu/courses/cs173/hyeari/

微软公司内部所有工程师的必读之书 I. M. Wright's Hard Code

2008-10-29 08:48:25

Copyright
Reader Acclaim for I. M. Wright's "Hard Code" Column
Foreword
Introduction
Chapter 1. Project Mismanagement
June 1, 2001: "Dev schedules, flying pigs, and other fantasies"
October 1, 2001: "Pushing the envelopes: Continued contention over dev schedules"
May 1, 2002: "Are we having fun yet? The joy of triage."
December 1, 2004: "Marching to death"
October 1, 2005: "To tell the truth"
Chapter 2. Process Improvement, Sans Magic
September 2, 2002: "Six Sigma? Oh please!"
October 1, 2004: "Lean: More than good pastrami"
April 1, 2005: "Customer dissatisfaction"
March 1, 2006: "The Agile bullet"
Chapter 3. Inefficiency Eradicated
July 1, 2001: "Late specs: Fact of life or genetic defect?"
June 1, 2002: "Idle hands"
June 1, 2004: "The day we met"
July 1, 2006: "Stop writing specs, co-located feature crews"
February 1, 2007: "Bad specs: Who is to blame?"
Chapter 4. Cross Disciplines
April 1, 2002: "The modern odd couple? Dev and Test"
July 1, 2004: "Feeling testy—The role of testers"
May 1, 2005: "Fuzzy logic—The liberal arts"
November 1, 2005: "Undisciplined—What's so special about specialization?"
Chapter 5. Software Quality—More Than a Dream
March 1, 2002: "Are you secure about your security?"
November 1, 2002: "Where's the beef? Why we need quality"
April 1, 2004: "A software odyssey—From craft to engineering"
July 1, 2005: "Review this—Inspections"
October 1, 2006: "Bold predictions of quality"
Chapter 6. Software Design If We Have Time
September 1, 2001: "A tragedy of error handling"
February 1, 2002: "Too many cooks spoil the broth—Sole authority"
May 1, 2004: "Resolved by design"
February 1, 2006: "The other side of quality—Designers and architects"
August 1, 2006: "Blessed isolation—Better design"
Chapter 7. Adventures in Career Development
December 1, 2001: "When the journey is the destination"
October 1, 2002: "Life isn't fair—The review curve"
November 1, 2006: "Roles on the career stage"
May 1, 2007: "Get yourself connected"
Chapter 8. Personal Bug Fixing
December 1, 2002: "My way or the highway—Negotiation"
February 1, 2005: "Better learn life balance"
June 1, 2005: "Time enough"
August 1, 2005: "Controlling your boss for fun and profit"
April 1, 2006: "You talking to me? Basic communication"
March 1, 2007: "More than open and honest"
Chapter 9. Being a Manager, and Yet Not Evil Incarnate
February 1, 2003: "More than a number—Productivity"
September 1, 2004: "Out of the interview loop"
November 1, 2004: "The toughest job—Poor performers"
September 1, 2005: "Go with the flow—Retention and turnover"
December 1, 2005: "I can manage"
May 1, 2006: "Beyond comparison—Dysfunctional teams"
Chapter 10. Microsoft, You Gotta Love It
November 1, 2001: "How I learned to stop worrying and love reorgs"
March 1, 2005: "Is your PUM a bum?"
September 1, 2006: "It's good to be the King of Windows"
December 1, 2006: "Google: Serious threat or poor spelling?"
April 1, 2007: "Mid-life crisis"
Glossary
About the Author
Index

LOGIC IN COMPUTER SCIENCE： MODELLING AND REASONING ABOUT SYSTEMS，SECOND EDITON

2008-10-23 22:05:21

数理逻辑是计算机科学的基础之一，在模型与系统的规约与验证等方面有着广泛的应用。随着当今软硬件产品(电路、程序和通信协议等)日趋复杂，数理逻辑已经成为越来越多设计开发人员的日常工具。
本书适合作为高等院校计算机及相关专业的数理逻辑／形式化方法课程教材，涵盖了命题逻辑、谓词逻辑、模态逻辑与Agent、二元决策图、模型检查和程序验证等内容。与传统数理逻辑教科书相比，它的主要特色就是紧紧围绕软硬件规约和验证这一主题，反映了计算机科学中数理逻辑的新发展和实际需要。第2版新增了可满足性(SAT)算法、紧致性理论和Lowenheim-Skolem定理，并介绍了Alloy语言和NuSMV工具。
本书自出版以来受到广泛好评，已经被包括美国普林斯顿大学、卡内基—梅隆大学、英国剑桥大学、德国汉堡大学、加拿大多伦多大学、荷兰Vrije大学、印度理工学院在内的多个国家几十所高校采纳为教材。

计算机软件技术基础

2008-10-14 22:46:05

【内容简介】
　　本教材用较短的篇幅、通俗的语言，全面系统地介绍了计算机软件技术的基础知识。全书分为6章：概述、数据结构与算法、操作系统、数据库系统、计算机网络、软件工程。每章既有基本原理的叙述又有常用实例的介绍，各章后均附有习题。
　　本教材以培养应用型人才为目标，适合于高等学校非计算机专业使用，亦可作为从事计算机应用的广大工程技术人员和管理人员的自学教程。
【下载说明】
　　本资料为《计算机软件技术基础》一书PDF格式的高清晰电子版，推荐使用Adobe Reader 7.0或兼容阅读工具打开！
【图书目录】
第1章概述
　1.1 计算机软件的发展
　1.2 微型计算机常用软件
　本章小结
　习题
第2章数据结构与算法
　2.1 数据结构的概述
　2.2 线性表
　2.3 栈和队列
　2.4 数组
　2.5 树与二叉树
　2.6 图
　2.7 查找
　2.8 排序
　本章小结
　习题
第3章操作系统
　3.1 操作系统的概述
　3.2 处理器管理
　3.3 存储管理
　3.4 设备管理
　3.5 文件管理
　本章小结
　习题
第4章数据库系统
　4.1 数据库的基本概念
　4.2 关系代数
　4.3 数据库设计
　4.4 关系数据库语言SQL
　4.5 数据完整性及安全性
　本章小结
　习题
第5章计算机网络
　5.1 计算机网络概述
　5.2 Intemet基本技术与应用
　5.3 计算机网络的安全
　本章小结
　习题
第6章软件工程
　6.1 软件工程概述
　6.2 软件开发方法
　6.3 软件开发工具
　6.4 软件测试与调试
　6.5 软件维护
　本章小结
　习题
参考文献

ProgammingChallenges

2008-09-18 17:31:21

There are many distinct pleasures associated with computer programming. Craftsmanship
has its quiet rewards, the satisfaction that comes from building a useful object and
making it work. Excitement arrives with the flash of insight that cracks a previously
intractable problem. The spiritual quest for elegance can turn the hacker into an artist.
There are pleasures in parsimony, in squeezing the last drop of performance out of clever
algorithms and tight coding.
The games, puzzles, and challenges of problems from international programming competitions
are a great way to experience these pleasures while improving your algorithmic
and coding skills. This book contains over 100 problems that have appeared in previous
programming contests, along with discussions of the theory and ideas necessary to attack
them. Instant online grading for all of these problems is available from two WWW
robot judging sites. Combining this book with a judge gives an exciting new way to
challenge and improve your programming skills.
This book can be used for self-study, for teaching innovative courses in algorithms
and programming, and in training for international competition.

计算机算法引论——设计与分析技术

2008-09-03 21:36:46

本书是一本面向计算机、软件工程和网络工程专业及相关专业的本科生(高年级)和研究生教材，根据国内外计算机技术的最新发展，讲述计算机算法的各种设计策略，包括分治技术、贪心技术、动态规划技术、回溯和分支限界技术等；介绍算法分析技术、算法的时间和空间复杂度分析方法，包括最坏情况和平均情况的分析等；讨论各类经典和应用问题的算法，包括排序算法、搜索算法、字符串匹配算法、图论算法、调度算法、组合优化算法、数论算法等。并在计算复杂性理论的基础上，引入近似算法、概率算法等最新内容。
目录
1 绪论
1. 1 交通信号灯问题
1. 1. 1 问题
1. 1. 2 实例
1. 1. 3 图着色问题
1. 1. 4 算法设计讨论
1. 1. 5 讨论
1. 2 什么是算法
1. 2. 1 算法
1. 2. 2 算法与问题
1. 2. 3 算法与程序
1. 3 算法的评估
1. 3. 1 正确性
1. 3. 2 时间代价
1. 3. 3 空间代价
1. 3. 4 最优性
1. 4 算法理论的基本概念
1. 4. 1 摹本操作
1. 4. 2 问题实例长度
1. 4. 3 复杂度的渐进性质
1. 4. 4 最坏情形和最好情形
1. 4. 5 平均情形和算法的期望复杂度
1. 4. 6 复杂度函数的表示
* 1. 5 算法的研究与Moore定律
* 1. 6 MAXMIN问题
1. 6. 1 平凡算法
1. 6. 2 改进一
1. 6. 3 改进二
1. 6. 4 改进三
1. 6. 5 讨论
习题1
2 排序算法与算法的分析技术
2. 1 排序问题
2. 2 O(n )阶的排序算法
2. 2. 1 选择排序
2. 2. 2 插入排序
2. 2. 3 起泡排序
2. 3 基于相邻元比较的排序算法和希尔排序
2. 3. 1 插入排序的最优性
2. 3. 2 希尔排序
2. 4 O(nlogn)阶的排序算法
2. 4. 1 快速排序算法
2. 4. 2 合并排序算法
2. 4. 3 堆排序算法
2. 5 比较排序算法的时间复杂度下界
2. 5. 1 判定树模型
2. 5. 2 最坏情形
2. 5. 3 平均情形
2. 6 排序算法的有关研究
习题2
3 分治技术
3. 1 分治策略的思想
3. 2 大整数乘法
3. 3 矩阵相乘的Strassen算法
3. 3. 1 问题
3. 3. 2 分治
3. 3. 3 Strassen的分治方法
3. 3. 4 Strassen算法的描述
3. 3. 5 讨论
3. 4 选择问题的线性算法
3. 4. 1 问题
3. 4. 2 简单算法
3. 4. 3 O(n)阶选择算法的思路
3. 4. 4 选择算法
3. 4. 5 选择算法Select的分析
3. 4. 6 讨论
习题3
4 数据集合上的搜索算法
4. 1 动态数据集与抽象数据类型
4. 2 二叉搜索树
4. 2. 1 二叉搜索树
4. 2. 2 查询的实现
4. 2. 3 插入与删除操作
4. 3 随机二叉搜索树
4. 4 红黑树
4. 4. 1 红黑树的性质
4. 4. 2 RB树的插入与删除算法
4. 4. 3 关于RB树的几点讨论
4. 5 2—3—4树
4. 5. 1 2—3—4树及其实例
4. 5. 2 2—3—4树上的查询操作算法
4. 5. 3 2—3—4树的构造过程
4. 5. 4 2—3—4树的性能分析
4. 5. 5 有关2—3—4树的几点讨论
4. 6 Hash技术
4. 6. 1 Hash算法的基本思想与一般模型
4. 6, 2 Hash函数的设计
4. 6. 3 解决冲突的策略
4. 6. 4 Hash算法的优劣分析
4. 6. 5 Hash技术的几种新发展
习题4
5 贪心技术
5. 1 贪心策略的思想
5. 1. 1 付款问题
5. 1. 2 铺砖问题
5. 1. 3 贪心算法的基本思想
5. 2 背包问题
5. 3 Huffman编码
5. 4 多机调度问题的近似解法
5. 5 单源最短路径的Dijkstra算法
习题5
6 字符串匹配
6. 1 字符串匹配问题
6. 2 KMP算法
6. 2. 1 KMP算法的思路
6. 2. 2 KMP算法
6. 2. 3 KMP算法的正确性
6. 2. 4 KMP算法的分析
6. 2. 5 有关KMP算法的讨论
6. 3 BM算法
6. 3. 1 BM算法的两种处理思路
6. 3. 2 BM算法的时间复杂度分析
6. 3. 3 对BM算法的进一步讨论
6. 4 RK算法
6. 4. 1 RK算法的思路
6. 4. 2 RK算法的描述
6. 4. 3 RK算法的分析与讨论
习题6
7 动态规划
7. 1 动态规划的基本原理
7. 1. 1 Fibonacci数的计算
7. 1. 2 矩阵连乘的顺序问题
7. 1. 3 动态规划算法的基本条件
7. 2 最优二分搜索树
7. 2. 1 最优二分搜索树问题
7. 2. 2 动态规划算法的思路
7. 2. 3 OBST算法
7. 2. 4 OBST算法的复杂度分析
7. 2. 5 讨论
7. 3 近似串匹配问题
7. 3. 1 近似串匹配问题的描述
7. 3. 2 动态规划算法的思路
7. 3. 3 动态规划算法
7. 3. 4 算法的复杂度分析与实例
7. 3. 5 讨论
习题7
8 回溯与分枝限界技术
8. 1 回溯和分枝限界的基本思想
8. 1. 1 八皇后问题
8. 1. 2 子集合问题
8. 1. 3 回溯与分枝限界算法的基本思路
8. 2 0—1背包问题的回溯算法
8. 2. 1 0—1背包问题
8. 2. 2 回溯策略的解题思路
8. 2. 3 0—1背包问题的回溯算法
8. 2. 4 算法的复杂度分析
8. 2. 5 一个运行实例
8. 3 无向图的团集问题
8. 3. 1 团集问题
8. 3. 2 解题思路
8. 3. 3 团集问题的回溯算法
8. 3. 4 算法Max Clique()的分析与讨论
8. 4 旅行商问题的回溯算法
8. 4. 1 旅行商问题
8. 4. 2 旅行商问题的回溯算法
8. 5 分枝限界算法思路的特征
8. 5. 1 0—1背包问题的分枝限界策略
8. 5. 2 分枝限界算法的优点和缺点
8. 5. 3 用分枝限界算法解旅行商问题的一个实例
习题8
9 计算机难解问题与NP—完全性问题
9. 1 一些难解问题
9. 1. 1 图着色问题
9. 1. 2 0—1背包问题
9. 1. 3 子集合问题
9. 1. 4 装箱问题
9. 1. 5 作业调度问题
9. 1. 6 可满足性问题
9. 1. 7 图的团集问题
9. 1. 8 Hamiltonian回路问题与Hamiltonian路径问题
9. 1. 9 旅行商问题
9. 2 多项式界与P类问题
9. 2. 1 多项式(时间)界
9. 2. 2 问题求解与判定问题
9. 2. 3 P类
9. 3 不确定算法与NP类
9. 3. 1 问题求解与验证
9. 3. 2 非确定算法与NP类
9. 4 问题的多项式归约和NP—完全性
9. 4. 1 多项式归约
9. 4. 2 NP—完全性
9. 4. 3 Cook定理
9. 5 与NP—完全问题相关的理论问题与实际问题
9. 5. 1 理论可计算性与实际可计算性
9. 5. 2 “P=NP”问题
9. 5. 3 NP—完全问题的计算处理
习题9
10 近似算法
10. 1 近似算法的思想与基本概念
10. 1. 1 顶点覆盖问题的近??算法
10. 1. 2 顶点覆盖问题的近似算法a VertexCover()
10. 1. 3 近似算法a VertexCover()的复杂度分析
10. 1. 4 算法a VertexCover()的近似度分析
10. 2 装箱问题的近似算法
10. 2. 1 装箱问题
10. 2. 2 装箱问题的近似策略的讨论
10. 2. 3 装箱问题的FF策略近似算法
10. 2. 4 bpFFD算法的复杂度
10. 2. 5 近似算法bqFFD()解的最优性分析
10. 2. 6 讨论
10. 3 旅行商问题的近似算法
10. 3. 1 最近邻点策略
10. 3. 2 最短链接策略
10. 3. 3 满足三角不等式的旅行商问题
10. 3. 4 几点讨论
习题10
11 数论算法及其在计算机安全系统中的应用
11. 1 RSA公钥密码系统
11. 1. 1 数据加密的历史及现状
11. 1. 2 公钥密码系统
11. 1. 3 RSA公钥密码系统
11. 1. 4 公钥密码系统的数字签名功能
11. 1. 5 公钥密码系统与计算机网络安全
11. 1. 6 RSA公钥密码系统的主要技术问题
11. 2 判素问题的概率算法
11. 2. 1 判素问题
11. 2. 2 输入长度和算术计算的时间代价
11. 2. 3 基于数论的素数判别概率算法
11. 3 大素数的获得和Miller—Rabin算法的应用
11. 3. 1 素数的稠密性
11. 3. 2 Miller-Rabin测试算法的时间代价
11. 3. 3 Miller-Rabin算法判定素数的正确性
11. 4 加密解密算法
11. 5 大整数分解与RSA系统的安全性
11. 5. 1 整数的因子分解问题
11. 5. 2 Pollard的rho启发式算法
习题11
附录A 递归方程(递归不等式)的求解判定方法
附录B 实际性能最佳的排序算法的设计
附录C 计算模型
附录D Cook定理
附录E 若干数论知识
附录F 算法索引
主要参考文献

编译原理考点精要与解题指导

2008-06-16 17:36:49

本书针对课程内容的重点和难点，选取多年来各类教材以及各高校、科研院所考研试题中有代表性的题目进行了分析解答，力求从发现问题考点、理清解题思路、掌握基本方法等方面对学习者给予帮助。
　　本书以编译原理教学大纲为指导，针对考研的特点进行内容安排，全书共分8章，内容包括：编译程序概述、文法和语言的形式定义、词法分析与有穷自动机、自上而下语法分析、自下而上语法分析、语法制导翻译和中间代码生成、运行阶段的存储组织与分配和代码优化。每一章具体内容分为考点精要、例题解析、自测题与参考答案3部分。本书的特点是概念准确，文字简洁明了，解题思路完整，极便于考研者短时间内掌握解题要点，提高考试成绩。本书不仅可作为研究生入学考试的复习参考书，也可作为计算机专业本科生的学习辅导书，对于参加其他相关考试的人员来说，也有一定的参考价值。
目录
第1章　编译程序概述　

1.1　考点精要　
1.1.1　程序设计语言的分类　
1.1.2　翻译程序　
1.1.3　编译方式　
1.1.4　解释方式与解释程序　
1.1.5　编译程序的工作过程　
1.1.6　编译程序的逻辑结构　
1.1.7　编译程序的构造
1.2　例题解析　
1.3　自测题及参考答案　

第2章　文法和语言的形式定义　

2.1　考点精要　
2.1.1　上下文无关文法　
2.1.2　文法描述的语言　
2.1.3　文法的分类　
2.1.4　语法树与二义性　
2.1.5　短语、简单短语与句柄　
2.1.6　文法的实用限制和文法变换　
2.2　例题解析　
2.3　自测题及参考答案　

第3章　词法分析与有穷自动机　

3.1　考点精要　
3.1.1　词法分析程序的任务　
3.1.2　词法分析方法　
3.1.3　状态转换图　
3.1.4　正规表达式　
3.1.5　有穷自动机　
3.1.6　由正规表达式构造确定的有穷自动机　
3.1.7　正规文法G到有穷自动机A的转换　
3.1.8　有穷自动机FA A到正规文法G的转换　
3.1.9　由有穷自动机到正规表达式的转换　
3.1.10　由正规文法到正规表达式的转换
3.1.11　词法分析程序的设计方法　
3.2　例题解析　
3.3　自测题及参考答案　

第4章　自上而下语法分析　

4.1　考点精要　
4.1.1　自上而下语法分析　
4.1.2　自上而下语法分析方法遇到的问题　
4.1.3　递归子程序法　
4.1.4　预测分析法(LL(1)方法)　
4.2　例题解析　
4.3　自测题及参考答案　

第5章　自下而上语法分析　

5.1　考点精要　
5.1.1　自下而上语法分析　
5.1.2　简单优先分析法　
5.1.3　算符优先分析法　
5.1.4　优先函数　
5.1.5　LR分析法　
5.2　例题解析　
5.3　自测题及参考答案　

第6章　语法制导翻译和中间代码生成　

6.1　考点精要　
6.1.1　语义分析　
6.1.2　语法制导翻译　
6.1.3　属性文法　
6.1.4　常见中间代码形式　
6.2　例题解析　
6.3　自测题及参考答案　

第7章　运行阶段的存储组织与分配　

7.1　考点精要　
7.1.1　基本思想　
7.1.2　过程的活动与活动记录　
7.1.3　静态存储分配　
7.1.4　动态存储分配　
7.1.5　简单的栈式存储分配　
7.1.6　嵌套结构语言的栈式动态存储分配方案　
7.1.7　堆式存储分配　
7.1.8　参数的传递方式及其实现　
7.2　例题解析　
7.3　自测题及参考答案　

第8章　代码优化　

8.1　考点精要　
8.1.1　程序的优化　
8.1.2　代码优化的种类　
8.1.3　基???块内的优化　
8.1.4　循环优化　
8.2　例题解析　
8.3　自测题及参考答案　

参考文献

Parallel and Distributed Logic Programming: Towards the Design of a Framework for the Next Generatio

2008-05-27 14:55:55

Product Description

Synopsis
The book "Parallel and Distributed Logic Programming" provides a clear introduction to parallel and distributed approach to logic programming. It examines the existing models of distributed logic programming, analyses the pros and cons of these models, and proposes an alternative framework for distributed logic programming using extended Petri nets. The hardwired realization of the Petri net based framework is presented in detail. Principles of mapping of a logic program on to the proposed framework are also outlined. Finally, the book attempts to explore the scope of Petri net models in designing deductive database machines of the next generation

Contents

1 An Introduction to Logic Programming.....................................................1
2 Parallel and Distributed Models for Logic Programming —A Review........................................................................................................57
3 The Petri NetModel— A New Approach ............................................. 107
4 Realization of a Parallel Architecture for the Petri Net Model ............. 177
5 Parsing and Task Assignment on to the Proposed
Parallel Architecture............................................................................... 211
6 Logic Programming in Database Applications ...................................... 229
Appendix A: Simulation of the Proposed Modular Architecture ................ 259
Appendix B: Open-ended Problems for Dissertation Works ....................... 271
Index..............................................................................................................285
About the Authors.........................................................................................289

Design.Patterns.Explained.A.New.Perspective.on.Object.Oriented.Design

2008-04-20 15:47:32

Leverage the quality and productivity benefits of patternswithout the complexity! Design Patterns Explained, Second Edition is the field's simplest, clearest, most practical introduction to patterns. Using dozens of updated Java examples, it shows programmers and architects exactly how to use patterns to design, develop, and deliver software far more effectively.

You'll start with a complete overview of the fundamental principles of patterns, and the role of object-oriented analysis and design in contemporary software development. Then, using easy-to-understand sample code, Alan Shalloway and James Trott illuminate dozens of today's most useful patterns: their underlying concepts, advantages, tradeoffs, implementation techniques, and pitfalls to avoid. Many patterns are accompanied by UML diagrams.

Building on their best-selling First Edition, Shalloway and Trott have thoroughly updated this book to reflect new software design trends, patterns, and implementation techniques. Reflecting extensive reader feedback, they have deepened and clarified coverage throughout, and reorganized content for even greater ease of understanding. New and revamped coverage in this edition includes

Better ways to start "thinking in patterns"

How design patterns can facilitate agile development using eXtreme Programming and other methods

How to use commonality and variability analysis to design application architectures

The key role of testing into a patterns-driven development process

How to use factories to instantiate and manage objects more effectively

The Object-Pool Patterna new pattern not identified by the "Gang of Four"

New study/practice questions at the end of every chapter

Gentle yet thorough, this book assumes no patterns experience whatsoever. It's the ideal "first book" on patterns, and a perfect complement to Gamma's classic Design Patterns. If you're a programmer or architect who wants the clearest possible understanding of design patternsor if you've struggled to make them work for youread this book.

Praise for Design Patterns Explained, Second Edition:
The Software Patterns Series
Titles in the series:
Preface
From Object Orientation to Patterns to True Object Orientation
From Artificial Intelligence to Patterns to True Object Orientation
A Note About Conventions Used in This Book
Feedback
New in the Second Edition
Acknowledgments
Part I. An Introduction to Object-Oriented Software Development
Chapter 1. The Object-Oriented Paradigm
Overview
Before the Object-Oriented Paradigm: Functional Decomposition
The Problem of Requirements
Dealing with Changes: Using Functional Decomposition
Dealing with Changing Requirements
The Object-Oriented Paradigm
Object-Oriented Programming in Action
Special Object Methods
Summary
Review Questions
Chapter 2. The UMLThe Unified Modeling Language
Overview
What Is the UML?
Why Use the UML?
The Class Diagram
Interaction Diagrams
Summary
Review Questions
Part II. The Limitations of Traditional Object-Oriented Design
Chapter 3. A Problem That Cries Out for Flexible Code
Overview
Extracting Information from a CAD/CAM System
Understand the Vocabulary
Describe the Problem
The Essential Challenges and Approaches
Summary
Review Questions
Chapter 4. A Standard Object-Oriented Solution
Overview
Solving with Special Cases
Summary
Review Questions
Part III. Design Patterns
Chapter 5. An Introduction to Design Patterns
Overview
Design Patterns Arose from Architecture and Anthropology
Moving from Architectural to Software Design Patterns
Why Study Design Patterns?
Other Advantages of Studying Design Patterns
Summary
Review Questions
Chapter 6. The Facade Pattern
Overview
Introducing the Facade Pattern
Learning the Facade Pattern
Field Notes: The Facade Pattern
Relating the Facade Pattern to the CAD/CAM Problem
Summary
Review Questions
Chapter 7. The Adapter Pattern
Overview
Introducing the Adapter Pattern
Learning the Adapter Pattern
Field Notes: The Adapter Pattern
Relating the Adapter Pattern to the CAD/CAM Problem
Summary
Review Questions
Chapter 8. Expanding Our Horizons
Overview
Objects: The Traditional View and the New View
Encapsulation: The Traditional View and the New View
Find What Is Varying and Encapsulate It
Commonality and Variability Analysis and Abstract Classes
The Qualities of Agile Coding
Summary
Review Questions
Chapter 9. The Strategy Pattern
Overview
An Approach to Handling New Requirements
The International E-Commerce System Case Study: Initial Requirements
Handling New Requirements
The Strategy Pattern
Field Notes: Using the Strategy Pattern
Summary
Review Questions
Chapter 10. The Bridge Pattern
Overview
Introducing the Bridge Pattern
Learning the Bridge Pattern: An Example
An Observation About Using Design Patterns
Learning the Bridge Pattern: Deriving It
The Bridge Pattern in Retrospect
Field Notes: Using the Bridge Pattern
Summary
Review Questions
Chapter 11. The Abstract Factory Pattern
Overview
Introducing the Abstract Factory Pattern
Learning the Abstract Factory Pattern: An Example
Learning the Abstract Factory Pattern: Implementing It
Field Notes: The Abstract Factory Pattern
Relating the Abstract Factory Pattern to the CAD/CAM Problem
Summary
Review Questions
Part IV. Putting It All Together: Thinking in Patterns
Chapter 12. How Do Experts Design?
Overview
Building by Adding Distinctions
Summary
Review Questions
Chapter 13. Solving the CAD/CAM Problem with Patterns
Overview
Review of the CAD/CAM Problem
Thinking in Patterns
Thinking in Patterns: Step 1
Thinking in Patterns: Step 2a
Thinking in Patterns: Step 2b
Thinking in Patterns: Step 2c
Thinking in Patterns: Steps 2a and 2b Repeated (Facade)
Thinking in Patterns: Steps 2a and 2b Repeated (Adapter)
Thinking in Patterns: Steps 2a and 2b Repeated (Abstract Factory)
Thinking in Patterns: Step 3
Comparison with the Previous Solution
Summary
Review Questions
Part V. Toward a New Paradigm of Design
Chapter 14. The Principles and Strategies of Design Patterns
Overview
The Open-Closed Principle
The Principle of Designing from Context
The Principle of Encapsulating Variation
Abstract Classes vs. Interfaces
The Principle of Healthy Skepticism
Summary
Review Questions
Chapter 15. Commonality and Variability Analysis
Overview
Commonality and Variability Analysis and Application Design
Solving the CAD/CAM Problem with CVA
Summary
Review Questions
Chapter 16. The Analysis Matrix
Overview
In the Real World: Variations
The International E-Commerce System Case Study: Handling Variation
Field Notes
Summary
Review Questions
Chapter 17. The Decorator Pattern
Overview
A Little More Detail
The Decorator Pattern
Applying the Decorator Pattern to the Case Study
Another Example: Input/Output
Field Notes: Using the Decorator Pattern
The Essence of the Decorator Pattern
Summary
Review Questions
Part VI. Other Values of Patterns
Chapter 18. The Observer Pattern
Overview
Categories of Patterns
More Requirements for the International E-Commerce Case Study
The Observer Pattern
Applying the Observer to the Case Study
Field Notes: Using the Observer Pattern
Summary
Review Questions
Chapter 19. The Template Method Pattern
Overview
More Requirements for the International E-Commerce Case Study
The Template Method Pattern
Applying the Template Method to the International E-Commerce Case Study
Using the Template Method Pattern to Reduce Redundancy
Field Notes: Using the Template Method Pattern
Summary
Review Questions
Part VII. Factories
Chapter 20. Lessons from Design Patterns: Factories
Overview
Factories
The Universal Context Revisited
Factories Follow Our Guidelines
Limiting the Vectors of Change
Another Way to Think About It
Different Roles of Factories
Field Notes
Summary
Review Questions
Chapter 21. The Singleton Pattern and the Double-Checked Locking Pattern
Overview
Introducing the Singleton Pattern
Applying the Singleton Pattern to the Case Study
A Variant: The Double-Checked Locking Pattern
Reflections
Field Notes: Using the Singleton and Double-Checked Locking Patterns
Summary
Review Questions
Chapter 22. The Object Pool Pattern
Overview
A Problem Requiring the Management of Objects
The Object Pool Pattern
Observation: Factories Can Do Much More Than Instantiation
Summary
Review Questions
Chapter 23. The Factory Method Pattern
Overview
More Requirements for the Case Study
The Factory Method Pattern
Factory Method Pattern and Object-Oriented Languages
Field Notes: Using the Factory Method Pattern
Summary
Review Questions
Chapter 24. Summary of Factories
Overview
Steps in the Software Process
Parallels in Factories and XP Practices
Scaling Systems
Part VIII. Endings and Beginnings
Chapter 25. Design Patterns Reviewed: A Summation and a Beginning
Overview
A Summary of Object-Oriented Principles
How Design Patterns Encapsulate Implementations
Commonality and Variability Analysis and Design Patterns
Decomposing a Problem Domain into Responsibilities
Patterns and Contextual Design
Relationships Within a Pattern
Design Patterns and Agile Coding Practices
Field Notes
Summary
Review Questions
Chapter 26. Bibliography
Design Patterns Explained: The Web Site Companion
Recommended Reading
Recommended Reading for Java Programmers
Recommended Reading for C++ Programmers
Recommended Reading for COBOL Programmers
Recommended Reading on eXtreme Programming
Recommended Reading on General Programming
Personal Favorites
Index

编码奥秘

2008-04-15 10:12:40

本书用大量的篇幅讲述了与计算机原理相关的条种编码方法，
并通过数字逻辑电路(包括逻辑与开关，逻辑门电路与触发器，
二进制加法器等)以及存储器、微处理器的形式、组织及发展阐述了编码的实现。
此外，本书还涉及到计算机系统、操作系统、编程语言等的产生及发展，
甚至对计算机图形化的相关技术也给了一个全面的描述。
阅读本书，相信您会从它图文并茂的编排组织，
通俗风趣的语言文字、简练丰富的背景知识中体会到作者超凡的智慧和深邃的学问。
本书定会带你去畅游计算机内部世界并和你共同去探索编码的奥秘。
本书适合各种技术背景的人阅读，并可作为高等院校计算机或非计算机专业的教材使用

目录

译者序

译者简介

第1章电筒密谈

第2章编码与组合

第3章布莱叶盲文与二元编码

第4章手电筒剖析

第5章绕过拐弯的通信

第6章发报机与转发器

第7章十进制记数法

第8章其他进位制记数法

第9章二进制数

第10章逻辑与开关

第11章逻辑门电路

第12章二进制加法机

第13章如何实现减法

第14章反馈与触发器

第15章字节与十六进制

第16章存储器组织

第17章自动操作

第18章从算盘到芯片

第19章两种典型的微处理器

第20章 ASCII 码与字符映射

第21章总线连接

第22章操作系统

第23章定点数和浮点数

第24章高级语言和低级语言

第25章图形化革命

国外计算机科学教材系列现代编译器的Java实现（第二版）

2008-04-01 23:59:55

【原书名】 Modern Compiler Implementation in Java,Second Edition
【原出版社】 Cambridge University Press
【作者】（美）Andrew W.Appel
【译者】陈明
【丛书名】国外计算机科学教材系列
【出版社】电子工业出版社【书号】 7121002701
【出版日期】 2004 年9月【开本】 16开【页码】 350 【版次】2-1

【内容简介】
本书是一本编译技术的教程，其特点是注重实现。从学习编译器的结构来掌握理论，并通过编程技术将编译理论融合于实践中。本书主要内容分为两部分，第一部分为编译基础（第1章至第12章），主要包括：词法分析、语法分析、抽象语法、语义分析、活动记录、翻译成中间代码、基本块和轨迹、指令选择、活性分析、寄存器分配、使之成为整体。第二部分为高级课题（第13章至第21章），主要包括：无用信息收集、面向对象语言、函数式编程语言、多态类型、数据流分析、循环优化、静态单赋值表、流水线和调度、分级存储器体系等。
本书可作为高等院校编译技术课程的教材、教师参考书以及编译技术研究人员的参考资料。

本书介绍了编译器的各个方面，包括词法分析，语法分析，抽象语法，语义行为，中间表示，通过树匹配选择指令，数据流分析，用色图法实现寄存器分配，运行时间系统。本书还讲述了通用的编译器实现技术，包括代码生成、寄存器分配以及大多数书籍未涉及的函数式编程语言和面向对象语言，并用实际的Java类详细说明了编译器各模块间的接口。本书的第一部分——编译器基础，适合作为第一学期编译器设计的入门课程。本书的第二部分ˉ一高级课题，包括面向对象语言和函数式语言的编译技术，无用信息收集，循环优化，静态单赋值表，指令调度以及高速缓冲存储器的分级优化，则适合作为第二学期的课程。本书第二版新增了关于Java和面向对象编程等概念，例如访问模型。本书的一大特色是利用Java子集重新实现了一个编译器项目。该项目包括前端和后端阶段，因此学生可以在一个学期内实现一个完整的编译器。

【作者介绍】
Andrew W.Appel
昔林斯顿大学计算机科学系教授，从事关于编译器、函数式编程语言、运行时间系统和无用信息收集、类型系统、计算机安全等方面的研究，并发表了多篇相关的论文；他还是“Compiling with Continuations”一书的作者，以及New Jersey项目ML标准的奠基者和设计者。由于“在编程语言和编译器领域的重大研究贡献”，以及他为ACM会刊“ACM Transactions on Programming Languages and Systems”所做的工作，1998年，Appel被选为ACM的会士。

【目录信息】
第一部分编译基础

第1章概述

1.1 模块及接口
1.1.1 阶段的描述
1.2 工具和软件
1.3 树型语言的数据结构
程序设计：直线程序解释器
习题

第2章词法分析

2.1 词法记号
2.2 正则表达式
2.3 有限自动机
2.3.1 识别最长的匹配
2.4 非确定有限自动机
2.4.1 正规文法转换为NFA
2.4.2 NFA转换为DFA
2.5 词法分析生成器
2.5.1 JAVACC
2.5.2 SableCC
程序设计：词法分析
进一步阅读
习题

第3章语法分析

3.1 上下文无关文法
3.1.1 推导
3.1.2 分析树
3.1.3 二义性文法
3.1.4 文件结束符
3.2 预测分析
3.2.1 FIRST和FOLLOW集
3.2.2 构造一个预测分析器
3.2.3 消除左递归
3.2.4 左因子
3.2.5 出错恢复
3.3 LR???析
3.3.1 LR分析器
3.3.2 LR(0)分析器生成器
3.3.3 SLR分析器生成器
3.3.4 LR(1)项目和LR(1)分析表
3.3.5 LALR(1)分析表
3.3.6 文法类型的层次结构
3.3.7 二义性文法的LR分析
3.4 使用分析器生成器
3.4.1 JAVACC
3.4.2 SableCC
3.4.3 算符优先分析法
3.4.4 语法和语义
3.5 出错恢复
3.5.1 用error符号恢复
3.5.2 全局出错修复
程序设计：实现分析器
进一步阅读
习题

第4章抽象语法

4.1 语义分析
4.1.1递归下降
4.1.2 自动生成分析器
4.2 抽象分析树
4.2.1位置
4.3 访问者
4.3.1 MiniJava的抽象语法
程序设计：抽象语法
进一步阅读
习题

第5章语义分析

5.1 符号表
5.1.1 多重符号表
5.1.2 高效率的命令符号表
5.1.3 高效率的功能符号表
5.1.4 符号
5.2 MiniJava的类型检查
5.2.1 错误处理
程序设计：类型检查
习题

第6章活动纪录

6.1 堆栈帧
6.1.1 帧指针
6.1.2 寄存器
6.1.3 参数传递
6.1.4 返回地址
6.1.5 常驻帧变量
6.1.6 静态连接
6.2 MiniJava语言编译器中的帧
6.2.1 帧的表示
6.2.2 局部变量
6.2.3 临时(局部)变量和标号
6.2.4 静态连接的管理
程序设计：帧
进一步阅读
习题

第7章翻译成中间代码

7.1 中间树
7.2 树的翻译
7.2.1 表达式的类型
7.2.2 简单变量
7.2.3 数组变量
7.2.4 结构化的L-值
7.2.5 下标和域选择
7.2.6 关于安全性
7.2.7 算术运算
7.2.8 条件
7.2.9 字符串
7.2.10 记录和数组的创建
7.2.11 while循环
7.2.12 for循环
7.2.13 函数调用
7.2.14 静态连接
7.3 声明
7.3.1 变量定义
7.3.2 函数定义
7.3.3 段
7.3.4 类和对象
程序设计：翻译为树
习题

第8章基本块和轨迹

8.1 规范树
8.1.1 ESEO的翻译
8.1.2 常用重写规则
8.1.3 将CALL移至顶部
8.1.4 语句的线性表
8.2 时间条件分支
8.2.1 基本块
8.2.2 轨迹
8.2.3 完成
8.2.4 最佳轨迹
进一步阅读
习题

第9章指令选择

9.1指令选择的算法
9.1.1 maximal munch算法
9.1.2 动态编程
9.1.3 树的文法规则
9.1.4 快速匹配
9.1.5表示算法的效率
9.2 CISC机
9.3 MiniJava编译器中的指令选择
9.3.1 抽象的汇编语言指令
9.3.2 生成汇编指令
9.3.3 过程调用
9.3.4 如果不存在帧指针
程序设计：指令选择
进一步阅读
习题

第10章活性分析

10.1 数据流的解
10.1.1 活性的计算
10.1.2 集合的表示
10.1.3 时间复杂度
10.1.4 最少的确定点
10.1.5 静态与动态活性
10.1.6 干扰图
10.2 MiniJava编译器中的活性分析
10.2.1 图
10.2.2 控制流图
10.2.3 活性分析
程序设计：构造流图
程序设计：活性
习题

第11章寄存器分配

11.1 简化着色
11.1.1 举例
11.2结合
11.2.1 溢出
11.3 预着色节点
11.3.1 机器寄存器临时变量的复制
11.3.2 调用保存寄存器和被调用保存寄存器
11.3.3 预着色节点的例子
11.4 图着色实现
11.4.1 数据结构
11.4.2 不变量
11.4.3 程序代码
11.5 树的寄存器分配
程序设计：图着色
进一步阅读
习题

第12章使之成为整体

程序设计进入/退出过程
程序设计：使程序运行
第二部分高级课题

第13章无用信息收集

13.1 标记一清除收集机制
13.2 引用计数
13.3 复制收集
13.4 世代收集
13.5 增量收集
13.6 Baker算法
13.7 编译器接口
13.7.1 快速分配
13.7.2 数据分布描述
13.7.3 派生指针
程序设计：描述符
程序设计：无用信息收集
进一步阅读
习题

第14章面向对象语言

14.1 类扩展
14.2 数据字段的单继承
14.2.1 方法
14.3 多继承
14.4 类成员测试
14.5 私有字段成员和方法
14.6 无类语言
14.7 优化面向对象程序
程序设计：带类扩展的MiniJava
进一步阅读
习题

第15章函数式编程语言

15.1 一种简单的函数式语言
15.2 闭包
15.2.1 堆分配激活记录
15.3 恒变量
15.3.1 基于连续的I/O
15.3.2 语言变换
15.3.3 纯函数式语言的优化
15.4 内部扩展
15.5 闭包转换
15.6 有效尾部递归
15.7 惰性评估
15.7.1 按名调用评估
15.7.2 按需调用
15.7.3 一个惰性程序的计算
15.7.4 推高不变量
15.7.5 惰性函数式程序的优化
15.7.6 严格性分析
进一步阅读
程序设计：编译函数式语言
习题

第16章多态类型

16.1 参数多态
16.2 多态类型检查
16.3 多态程序的翻译
16.3.1 指针、整型和包装
16.4 静态重载的解决方法
进一步阅读
习题

第17章数据流分析

17.1 流分析的中间表示
17.1.1 四元组
17.2 多种的数据流分析
17.2.1 到达定义
17.2.2 可用表达式
17.2.3 到达表达式
17.2.4 活性分析
17.3 使用数据流分析的变换
17.3.1 公用子表达式消除
17.3.2 常量传播
17.3.3 复制传播
17.3.4 死代码消除
17.4 加快数据流分析
17.4.1 位向量
17.4.2 基本块
17.4.3 节点排序
17.4.4 use-def和def-use链
17.4.5 work-list算法
17.4.6 增量式数据流分析
17.5 别名分析
17.5.1 基于类型的别名分析
17.5.2 基于流的别名分析
17.5.3 使用may-alias信息
17.5.4 严格纯函数式语言中的别名分析
进一步阅读
习题

第18章循环优化

18.1 必经节点
18.1.1 寻找必经节点的算法
18.1.2 直接必经节点
18.1.3 循环
18.1.4 循环前置首部
18.2 循环不变量的计算
18.2.1 提升
18.3 归纳变量
18.3.1 归纳变量检查
18.3.2 强度削减
18.3.3 消除
18.3.4 重写比较
18.4 数组边界检查
18.5 循环展开
进一步阅读
习题

第19章静态单赋值表

19.1 转化为SSA表
19.1.1 插入∮-function的准则
19.1.2 必经前端
19.1.3 插入∮-function
19.1.4 变量重命名
19.1.5 边分离
19.2 必经节点树的有效计算
19.2.1 深度优先生成(spanning)树
19.2.2 半必经节点
19.2.3 Lengauer-Tarjan算法
19.3 采用SSA优化算法
19.3.1 消除死代码
19.3.2 简单常量传播
19.3.3 条件常量复制
19.3.4 保存必经性质
19.4 数组，指针和存储
19.4.1 存储相关
19.5 控制相关图
19.5.1 积极的死代码消除
19.6 从SSA表后的转换
19.6.1 关于SSA的活性的分析
19.7 函数式中介表
进一步阅读
习题

第20章流水线和调度

20.1 不受资源限制的循环调度
20.2 资源限制循环流水线
20.2.1 模调度
20.2.2 发现最小启动间隔
20.2.3 其他控制流
20.2.4 编译器应该调度指令吗
20.3 分支预测
20.3.1 静态转移预测
20.3.2 编译器应该预测分支转移吗?
进一步阅读
习题

第21章分级存储器体系

21.1 高速缓冲存储器结构
21.2 cache块的排列
21.2.1 指令cache的对齐
21.3 预取指令
21.4 循环交换
21.5 分块
21.6 无用信息收集和分级存储器体系
进一步阅读
习题

附录 MiniJava语言参考手册

参考文献

编译器与编译器生成器（C++版）Compilers and Compiler Generators:an introduction with C++

2008-03-23 23:12:49

The book starts with a fairly simple overview of the translation process, of the constituent parts of a compiler, and of the concepts of porting and bootstrapping compilers. This is followed by a chapter
on machine architecture and machine emulation, as later case studies make extensive use of code generation for emulated machines, a very common strategy in introductory courses. The next chapter introduces the student to the notions of regular expressions, grammars, BNF and EBNF, and the value of being able to specify languages concisely and accurately.
Two chapters follow that discuss simple features of assembler language, accompanied by the development of an assembler/interpreter system which allows not only for very simple assembly, but also for conditional assembly, macro-assembly, error detection, and so on. Complete code for such an assembler is presented in a highly modularized form, but with deliberate scope left for extensions, ranging from the trivial to the extensive.
Three chapters follow on formal syntax theory, parsing, and the manual construction of scanners and parsers. The usual classifications of grammars and restrictions on practical grammars are discussed in some detail. The material on parsing is kept to a fairly simple level, but with a thorough discussion of the necessary conditions for LL(1) parsing. The parsing method treated in most detail is the method of recursive descent, as is found in many Pascal compilers; LR parsing is only briefly discussed.
The next chapter is on syntax directed translation, and stresses to the reader the importance and usefulness of being able to start from a context-free grammar, adding attributes and actions that allow for the manual or mechanical construction of a program that will handle the system that it defines. Obvious applications come from the field of translators, but applications in other areas such as simple database design are also used and suggested.
The next two chapters give a thorough introduction to the use of Coco/R, a compiler generator based on L- attributed grammars. Besides a discussion of Cocol, the specification language for this tool, several in-depth case studies are presented, and the reader is given some indication of how parser generators are themselves constructed.
The next two chapters discuss the construction of a recursive descent compiler for a simple Pascal-like source language, using both hand-crafted and machine-generated techniques. The compiler produces pseudo-code for a hypothetical stack-based computer (for which an interpreter was developed in an earlier chapter). "On the fly" code generation is discussed, as well as the use of intermediate tree construction.
The last chapters extend the simple language (and its compiler) to allow for procedures and functions, demonstrate the usual stack-frame approach to storage management, and go on to discuss the implementation of simple concurrent programming. At all times the student can see how these are handled by the compiler/interpreter system, which slowly grows in complexity and usefulness until the final product enables the development of quite sophisticated programs.
The text abounds with suggestions for further exploration, and includes references to more advanced texts where these can be followed up. Wherever it seems appropriate the opportunity is taken to make the reader more aware of the strong and weak points in topical imperative languages. Examples are drawn from several languages, such as Pascal, Modula-2, Oberon, C, C++, Edison and Ada.

编译程序设计：理论、工具与实例（Java版）Compiler Design:Theory, Tools, and Examples(Java Edition)

2008-03-23 22:54:47

This book is a revision of earlier editions that were written for Pascal and C++
based curricula. As many computer science departments have moved to Java as the
primary language in the undergraduate curriculum, I have produced this edition to
accommodate those departments. This book is not intended to be strictly an object-
oriented approach to compiler design. Though most Java compilers compile to an
intermediate form known as Byte Code, the approach taken here is a more traditional one
in which we compile to native code for a particular machine.
The most essential prerequisites for this book are courses in Java application
programming, Data Structures, Assembly Language or Computer Architecture, and
possibly Programming Languages. If the student has not studied formal languages and
automata, this book includes introductory sections on these theoretic topics, but in this
case it is not likely that all seven chapters will be covered in a one semester course.
Students who have studied the theory will be able to skip the preliminary sections (2.0,
3.0, 4.0) without loss of continuity.
The concepts of compiler design are applied to a case study which is an imple-
mentation of a subset of Java which I call Decaf. Chapters 2, 4, 5, and 6 include a
section devoted to explaining how the relevant part of the Decaf compiler is designed.
This public domain software is presented in full in the appendices and is available on the Internet. Students can benefit by enhancing or changing the Decaf compiler provided.
Chapters 6 and 7 focus on the back end of the compiler (code generation and
optimization). Here I rely on a fictitious computer, called Mini, as the target machine. I use a fictitious machine for three reasons: (1) I can design it for simplicity so that the compiler design concepts are not obscured by architectural requirements, (2) It is available to anyone who has a C compiler (the Mini simulator, written in C, is available also), and (3) the teacher or student can modify the Mini machine to suit his/her tastes.

Chapter 7 includes only a brief description of optimization techniques since
there is not enough time in a one semester course to delve into these topics, and becau-se these are typically studied in more detail at the graduate level.
To use the software that accompanies this book, you will need access to the
world wide web. The source files can be accessed at
http://www.rowan.edu/~bergmann/books/decaf
These are plain text files which can be saved from your internet browser. Additional
description of these files can be found in Appendix B.
I wish to acknowledge the people who participated in the design of this book.
The reviewers of the original Pascal version – James E. Miller of Transylvania Unive-rsity, Jeffrey C. Chang of Garner-Webb University, Stephen J. Allan of Utah State
University, Karsten Henckell of the New College of USF, and Keith Olson of Montana
Technical College – all took the time to read through various versions of the manuscri-pt of the original edition and provided many helpful suggestions. My students in the
Compiler Design course here at Rowan University also played an important role in
testing the original version and subsequent versions of this book. Support in the form of time and equipment was provided by the administration of Rowan University.
The pages of this book were composed entirely by me using Adobe Pagemaker,
and diagrams were drawn with Microsoft Excel and Powerpoint. Finally, I am most grateful to my wife Sue for being so understanding during the time that I spent working on this project.

Seth D. Bergmann
bergmann@rowan.edu

编译原理习题精选与解析

2008-03-21 02:50:13

本书为十五国家级规划教材《编译原理》的配套用书。全书从主教材的习题和作者近年来所设计的各种试题中，精选出180道题目进行分析与解答，融入作者多年讲授这门课程的经验和体会。为便于结合教学使用，全书各章的名称和主教材一致，并对难度较大的题目标注星号。同时，为方便读者准备研究生入学考试，凡是作者曾用于研究生入学考试的题目，都在前面加注“考研题”三个字。本书的习题涉及面广、灵活性强、机械性和重复性少，对学习编译原理课程很有帮助。本书可供本科生、自学考试考生和其他人员学习编译原理和技术的参考，也是研究生入学考试的一本有用的复习参考书。

【目录信息】
第1章编译器概述.
第2章词法分析
第3章语法分析
第4章语法制导的翻译
第5章类型检查
第6章运行时存储空间的组织和管理
第7章中间代码生成..
第8章代码生成
第9章代码优化
第10章编译系统和运行系统
第11章面向对象语言的编译
第12章函数式语言的编译...

Foundations of Multithreaded Parallel and Distributed Programming

2008-03-20 09:03:04

Book Description
Foundations of Multithreaded, Parallel, and Distributed Programming covers-and then applies-the core concepts and techniques needed for an introductory course in this topic. The book emphasizes the practice and application of parallel systems, using real-world examples throughout.

Greg Andrews teaches the fundamental concepts of multithreaded, parallel and distributed computing and relates them to the implementation and performance processes. He presents the appropriate breadth of topics and supports these discussions with an emphasis on performance.

Book Info
Covers the unifying core concepts that programmers using these methods should know. Case studies are used to demonstrate applications of the most important languages and software libraries, including Pthreads, Java, Linda, CSP, MPI, Ada, SR, OpenMP, and High Performance Fortran. Softcover. DLC: Parallel programming (Computer science).

Exposing Cryptovirology

2008-03-16 11:07:38

Contents
Foreword xiii
Acknowledgments xix
Introduction xxi
1 Through Hacker’s Eyes 1
2 Cryptovirology 33
3 Tools for Security and Insecurity 51
3.1 Sources of Entropy . . . . . . . . . . . . . . . . . . . . . . 53
3.2 Entropy Extraction via Hashing . . . . . . . . . . . . . . . 54
3.3 Unbiasing a Biased Coin . . . . . . . . . . . . . . . . . . . 57
3.3.1 Von Neumann’s Coin Flipping Algorithm . . . . . . 57
3.3.2 Iterating Neumann’s Algorithm . . . . . . . . . . . 59
3.3.3 Heuristic Bias Matching . . . . . . . . . . . . . . . 60
3.4 Combining Weak Sources of Entropy . . . . . . . . . . . . 62
3.5 Pseudorandom Number Generators . . . . . . . . . . . . . 66
3.5.1 Heuristic Pseudorandom Number Generation . . . . 66
3.5.2 PRNGs Based on Reduction Arguments . . . . . . 67
3.6 Uniform Sampling . . . . . . . . . . . . . . . . . . . . . . . 68
3.7 Random Permutation Generation . . . . . . . . . . . . . . 71
3.7.1 Shuffling Cards by Repeated Sampling . . . . . . . 71
3.7.2 Shuffling Cards Using Trotter-Johnson . . . . . . . 73
3.8 Sound Approach to Random Number Generation and Use 76
3.9 RNGs Are the Beating Heart of System Security . . . . . . 77
3.10 Cryptovirology Benefits from General Advances . . . . . . 78
3.10.1 Strong Crypto Yields Strong Cryptoviruses . . . . . 78
3.10.2 Mix Networks and Cryptovirus Extortion . . . . . . 80

3.11 Anonymizing Program Propagation . . . . . . . . . . . . . 85
4 The Two Faces of Anonymity 89
4.1 Anonymity in a Digital Age . . . . . . . . . . . . . . . . . 89
4.1.1 From Free Elections to the Unabomber . . . . . . . 90
4.1.2 Electronic Money and Anonymous Payments . . . . 90
4.1.3 Anonymous Assassination Lotteries . . . . . . . . . 92
4.1.4 Kidnapping and Perfect Crimes . . . . . . . . . . . 93
4.1.5 Conducting Criminal Operations with Mixes . . . . 94
4.2 Deniable Password Snatching . . . . . . . . . . . . . . . . 97
4.2.1 Password Snatching and Security by Obscurity . . . 97
4.2.2 Solving the Problem Using Cryptovirology . . . . . 98
4.2.3 Zero-Knowledge Proofs to the Rescue . . . . . . . . 100
4.2.4 Improving the Attack Using ElGamal . . . . . . . . 101
5 Cryptocounters 103
5.1 Overview of Cryptocounters . . . . . . . . . . . . . . . . . 104
5.2 Implementing Cryptocounters . . . . . . . . . . . . . . . . 105
5.2.1 A Simple Counter Based on ElGamal . . . . . . . . 105
5.2.2 Drawback to the ElGamal Solution . . . . . . . . . 106
5.2.3 Cryptocounter Based on Squaring . . . . . . . . . . 107
5.2.4 The Paillier Encryption Algorithm . . . . . . . . . 108
5.2.5 A Simple Counter Based on Paillier . . . . . . . . . 111
5.3 Other Approaches to Cryptocounters . . . . . . . . . . . . 111
6 Computationally Secure Information Stealing 113
6.1 Using Viruses to Steal Information . . . . . . . . . . . . . 114
6.2 Private Information Retrieval . . . . . . . . . . . . . . . . 115
6.2.1 PIR Based on the Phi-Hiding Problem . . . . . . . 117
6.2.2 Security of the Phi-Hiding PIR . . . . . . . . . . . 120
6.2.3 Application of the Phi-Hiding Technique . . . . . . 122
6.3 A Variant of the Phi-Hiding Scheme . . . . . . . . . . . . . 122
6.4 Tagged Private Information Retrieval . . . . . . . . . . . . 126
6.5 Secure Information Stealing Malware . . . . . . . . . . . . 131
6.6 Deniable Password Snatching Based on Phi-Hiding . . . . 132
6.6.1 Improved Password-Snatching Algorithm . . . . . . 133
6.6.2 Questionable Encryptions . . . . . . . . . . . . . . 134
6.6.3 Deniable Encryptions . . . . . . . . . . . . . . . . . 139
6.7 Malware Loaders . . . . . . . . . . . . . . . . . . . . . . . 140
6.8 Cryptographic Computing . . . . . . . . . . . . . . . . . . 141

7 Non-Zero Sum Games and Survivable Malware 147
7.1 Survivable Malware . . . . . . . . . . . . . . . . . . . . . . 148
7.2 Elements of Game Theory . . . . . . . . . . . . . . . . . . 150
7.3 Attacking a Brokerage Firm . . . . . . . . . . . . . . . . . 151
7.3.1 Assumptions for the Attack . . . . . . . . . . . . . 152
7.3.2 The Distributed Cryptoviral Attack . . . . . . . . . 153
7.3.3 Security of the Attack . . . . . . . . . . . . . . . . 158
7.3.4 Utility of the Attack . . . . . . . . . . . . . . . . . 159
7.4 Other Two-Player Game Attacks . . . . . . . . . . . . . . 161
7.4.1 Key Search via Facehuggers . . . . . . . . . . . . . 161
7.4.2 Catalyzing Conflict Among Hosts . . . . . . . . . . 167
7.5 Future Possibilities . . . . . . . . . . . . . . . . . . . . . . 167
8 Coping with Malicious Software 171
8.1 Undecidability of Virus Detection . . . . . . . . . . . . . . 171
8.2 Virus Identification and Obfuscation . . . . . . . . . . . . 172
8.2.1 Virus String Matching . . . . . . . . . . . . . . . . 173
8.2.2 Polymorphic Viruses . . . . . . . . . . . . . . . . . 176
8.3 Heuristic Virus Detection . . . . . . . . . . . . . . . . . . . 182
8.3.1 Detecting Code Abnormalities . . . . . . . . . . . . 182
8.3.2 Detecting Abnormal Program Behavior . . . . . . . 183
8.3.3 Detecting Cryptographic Code . . . . . . . . . . . . 191
8.4 Change Detection . . . . . . . . . . . . . . . . . . . . . . . 197
8.4.1 Integrity Self-Checks . . . . . . . . . . . . . . . . . 197
8.4.2 Program Inoculation . . . . . . . . . . . . . . . . . 198
8.4.3 Kernel Based Signature Verification . . . . . . . . . 199
9 The Nature of Trojan Horses 201
9.1 Text Editor Trojan Horse . . . . . . . . . . . . . . . . . . 202
9.2 Salami Slicing Attacks . . . . . . . . . . . . . . . . . . . . 202
9.3 Thompson’s Password Snatcher . . . . . . . . . . . . . . . 203
9.4 The Subtle Nature of Trojan Horses . . . . . . . . . . . . . 206
9.4.1 Bugs May In Fact Be Trojans . . . . . . . . . . . . 208
9.4.2 RNG Biasing Trojan Horse . . . . . . . . . . . . . . 208
10 Subliminal Channels 211
10.1 Brief History of Subliminal Channels . . . . . . . . . . . . 212
10.2 The Difference Between a Subliminal and a Covert Channel 214
10.3 The Prisoner’s Problem of Gustavus Simmons . . . . . . . 215
10.4 Subliminal Channels New and Old . . . . . . . . . . . . . 216

10.4.1 The Legendre Channel of Gus Simmons . . . . . . 217
10.4.2 The Oracle Channel . . . . . . . . . . . . . . . . . 220
10.4.3 Subliminal Card Marking . . . . . . . . . . . . . . 222
10.4.4 The Newton Channel . . . . . . . . . . . . . . . . . 223
10.4.5 Subliminal Channel in Composites . . . . . . . . . 224
10.5 The Impact of Subliminal Channels on Key Escrow . . . . 226
11 SETUP Attack on Factoring Based Key Generation 229
11.1 Honest Composite Key Generation . . . . . . . . . . . . . 231
11.2 Weak Backdoor Attacks on Composite Key Generation . . 232
11.2.1 Using a Fixed Prime . . . . . . . . . . . . . . . . . 233
11.2.2 Using a Pseudorandom Function . . . . . . . . . . 234
11.2.3 Using a Pseudorandom Generator . . . . . . . . . . 236
11.3 Probabilistic Bias Removal Method . . . . . . . . . . . . . 239
11.4 Secretly Embedded Trapdoors . . . . . . . . . . . . . . . . 241
11.5 Key Generation SETUP Attack . . . . . . . . . . . . . . . 244
11.6 Security of the SETUP Attack . . . . . . . . . . . . . . . . 249
11.6.1 Indistinguishability of Outputs . . . . . . . . . . . 249
11.6.2 Confidentiality of Outputs . . . . . . . . . . . . . . 252
11.7 Detecting the Attack in Code Reviews . . . . . . . . . . . 256
11.8 Countering the SETUP Attack . . . . . . . . . . . . . . . 259
11.9 Thinking Outside the Box . . . . . . . . . . . . . . . . . . 261
11.10 The Isaac Newton Institute Lecture . . . . . . . . . . . . 262
12 SETUP Attacks on Discrete-Log Cryptosystems 265
12.1 The Discrete-Log SETUP Primitive . . . . . . . . . . . . . 266
12.2 Diffie-Hellman SETUP Attack . . . . . . . . . . . . . . . . 268
12.3 Security of the Diffie-Hellman SETUP Attack . . . . . . . 270
12.3.1 Indistinguishability of Outputs . . . . . . . . . . . 270
12.3.2 Confidentiality of Outputs . . . . . . . . . . . . . . 271
12.4 Intuition Behind the Attack . . . . . . . . . . . . . . . . . 275
12.5 Kleptogram Attack Methodology . . . . . . . . . . . . . . 276
12.6 PKCS SETUP Attacks . . . . . . . . . . . . . . . . . . . . 277
12.6.1 ElGamal PKCS SETUP Attack . . . . . . . . . . . 277
12.6.2 Cramer-Shoup PKCS SETUP Attack . . . . . . . . 279
12.7 SETUP Attacks on Digital Signature Algorithms . . . . . 280
12.7.1 SETUP in the ElGamal Signature Algorithm . . . . 281
12.7.2 SETUP in the Pointcheval-Stern Algorithm . . . . 282
12.7.3 SETUP in DSA . . . . . . . . . . . . . . . . . . . . 283

12.7.4 SETUP in the Schnorr Signature Algorithm . . . . 284
12.8 Rogue Use of DSA for Encryption . . . . . . . . . . . . . . 285
12.9 Other Work in Kleptography . . . . . . . . . . . . . . . . . 286
12.10 Should You Trust Your Smart Card? . . . . . . . . . . . . 288
Appendix A: Computer Virus Basics 295
A.1 Origins of Malicious Software . . . . . . . . . . . . . . . . 295
A.2 Trojans, Viruses, and Worms: What Is the Difference? . . 297
A.3 A Simple DOS COM Infector . . . . . . . . . . . . . . . . 299
A.4 Viruses Don’t Have to Gain Control Before the Host . . . 303
Appendix B: Notation and Other Background Information 307
B.1 Notation Used Throughout the Book . . . . . . . . . . . . 307
B.2 Basic Facts from Number Theory and Algorithmics . . . . 309
B.3 Intractability: Malware’s Biggest Ally . . . . . . . . . . . . 312
B.3.1 The Factoring Problem . . . . . . . . . . . . . . . . 313
B.3.2 The eth Roots Problem . . . . . . . . . . . . . . . . 314
B.3.3 The Composite Residuosity Problem . . . . . . . . 314
B.3.4 The Decision Composite Residuosity Problem . . . 315
B.3.5 The Quadratic Residuosity Problem . . . . . . . . . 315
B.3.6 The Phi-Hiding Problem . . . . . . . . . . . . . . . 315
B.3.7 The Phi-Sampling Problem . . . . . . . . . . . . . 317
B.3.8 The Discrete Logarithm Problem . . . . . . . . . . 318
B.3.9 The Computational Diffie-Hellman Problem . . . . 318
B.3.10 The Decision Diffie-Hellman Problem . . . . . . . . 318
B.4 Random Oracles and Functions . . . . . . . . . . . . . . . 319
Appendix C: Public Key Cryptography in a Nutshell 321
C.1 Overview of Cryptography . . . . . . . . . . . . . . . . . . 321
C.1.1 Classical Cryptography . . . . . . . . . . . . . . . . 322
C.1.2 The Diffie-Hellman Key Exchange . . . . . . . . . . 324
C.1.3 Public Key Cryptography . . . . . . . . . . . . . . 325
C.1.4 Attacks on Cryptosystems . . . . . . . . . . . . . . 326
C.1.5 The Rabin Encryption Algorithm . . . . . . . . . . 330
C.1.6 The Rabin Signature Algorithm . . . . . . . . . . . 331
C.1.7 The RSA Encryption Algorithm . . . . . . . . . . . 332
C.1.8 The RSA Signature Algorithm . . . . . . . . . . . . 334
C.1.9 The Goldwasser-Micali Algorithm . . . . . . . . . . 335
C.1.10 Public Key Infrastructures . . . . . . . . . . . . . . 336
C.2 Discrete-Log Based Cryptosystems . . . . . . . . . . . . . 337

C.2.1 The ElGamal Encryption Algorithm . . . . . . . . 338
C.2.2 Security of ElGamal . . . . . . . . . . . . . . . . . 338
C.2.3 The Cramer-Shoup Encryption Algorithm . . . . . 340
C.2.4 The ElGamal Signature Algorithm . . . . . . . . . 342
C.2.5 The Pointcheval-Stern Signature Algorithm . . . . 343
C.2.6 The Schnorr Signature Algorithm . . . . . . . . . . 344
C.2.7 The Digital Signature Algorithm (DSA) . . . . . . 345
Glossary 347
References 357
Index 387

The Transform and Data Compression Handbook

2008-03-15 09:24:12

1 Karhunen-LoèveTransform
1.1 Introduction
1.2 DataDecorrelation
1.2.1 Calculation oftheKLT
1.3 PerformanceofTransforms
1.3.1 Information Theory
1.3.2 Quantization
1.3.3 Truncation Error
1.3.4 Block Size
1.4 Examples
1.4.1 Calculation ofKLT
1.4.2 Quantization and Encoding
1.4.3 Generalization
1.4.4 Markov-1 Solution
1.4.5 MedicalImaging
1.4.6 ColorImages
1.5 Summary
References
2 TheDiscreteFourierTransform
2.1 Introduction
2.2 TheDFTMatrix
2.3 AnExample
2.4 DFT FrequencyAnalysis
2.5 SelectedPropertiesoftheDFT
2.5.1 Symmetry Properties
2.6 Real-Valued DFT-Based Transforms
2.7 TheFastFourierTransform
2.8 TheDFT in Coding Applications
2.9 TheDFT andFilterBanks
2.9.1 Cosine-Modulated Filter Banks
2.9.2 Complex DFT-Based Filter Banks

2.10 Conclusion
2.11 FFT Web sites
References
3 ComparametricTransformsforTransmittingEyeTapVideowithPicture
TransferProtocol(PTP)
3.1 Introduction: WearableCybernetics
3.1.1 Historical Overviewof WearComp
3.1.2 EyeTap Video
3.2 TheEdgertonian Image Sequence
3.2.1 Edgertonian versus Nyquist Thinking
3.2.2 FramesversusRows,Columns,and Pixels
3.3 PictureTransfer Protocol (PTP)
3.4 BestCaseImaging and Fear of Functionality
3.5 Comparametric ImageSequenceAnalysis
3.5.1 Camera, Eye, or Head Motion: Common Assumptions and
Terminology
3.5.2 VideoOrbits
3.6 Framework: Comparameter Estimation and Optical Flow
3.6.1 Feature-Based Methods
3.6.2 FeaturelessMethodsBased on Generalized Cross-Correlation
3.6.3 FeaturelessMethodsBasedon Spatio-Temporal Derivatives
3.7 MultiscaleProjective Flow Comparameter Estimation
3.7.1 FourPointMethodforRelatingApproximateModeltoExact
Model
3.7.2 Overviewof the New ProjectiveFlow Algorithm
3.7.3 MultiscaleRepetitiveImplementation
3.7.4 Exploiting Commutativity for Parameter Estimation
3.8 Performance/Applications
3.8.1 A Paradigm Reversal in ResolutionEnhancement
3.8.2 Increasing Resolutionin the “Pixel Sense”
3.9 Summary
3.10 Acknowledgements
References
4 DiscreteCosineand SineTransforms
4.1 Introduction
4.2 TheFamily of DCTsand DSTs
4.2.1 Definitionsof DCTs and DSTs
4.2.2 Mathematical Properties
4.2.3 Relationsto theKLT
4.3 A Unified FastComputationof DCTsand DSTs
4.3.1 Definitionsof Even-Odd Matrices
4.3.2 DCT-II/DST-II and DCT-III/DST-III Computation
4.3.3 DCT-I and DST-I Computation

4.3.4 DCT-IV/DST-IV Computation
4.3.5 Implementation of the Unified Fast Computation of DCTs
andDSTs
4.4 The2-DDCT/DST Universal Computational Structure
4.4.1 TheFastDirect2-D DCT/DSTComputation
4.4.2 Implementationofthe Direct 2-DDCT/DST Computation
4.5 DCT andDataCompression
4.5.1 DCT-Based ImageCompression/Decompression
4.5.2 DataStructuresforCompression/Decompression
4.5.3 Setting theQuantization Table
4.5.4 StandardHuffman Coding/Decoding Tables
4.5.5 Compression ofOne Sub-ImageBlock
4.5.6 DecompressionofOne Sub-Image Block
4.5.7 ImageCompression/Decompression
4.5.8 Compression ofColor Images
4.5.9 ResultsofImageCompression
4.6 Summary
References
5 Lapped TransformsforImageCompression
5.1 Introduction
5.1.1 Notation
5.1.2 BriefHistory
5.1.3 Block Transforms
5.1.4 Factorization ofDiscrete Transforms
5.1.5 DiscreteMIMOLinear Systems
5.1.6 BlockTransform as aMIMO System
5.2 Lapped Transforms
5.2.1 OrthogonalLapped Transforms
5.2.2 NonorthogonalLappedTransforms
5.3 LTsasMIMOSystems
5.4 Factorization ofLapped Transforms
5.5 HierarchicalConnectionofLTs: An Introduction
5.5.1 Time-Frequency Diagram
5.5.2 Tree-Structured Hierarchical LappedTransforms
5.5.3 Variable-Length LTs
5.6 PracticalSymmetricLTs
5.6.1 TheLappedOrthogonal Transform: LOT
5.6.2 TheLapped Bi-Orthogonal Transform: LBT
5.6.3 TheGeneralized LOT: GenLOT
5.6.4 TheGeneralFactorization: GLBT
5.7 TheFastLappedTransform: FLT
5.8 Modulated LTs
5.9 Finite-Length Signals
5.9.1 OverallTransform

5.9.2 Recovering Distorted Samples
5.9.3 SymmetricExtensions
5.10 Design Issuesfor Compression
5.11 Transform-Based Image Compression Systems
5.11.1 JPEG
5.11.2 Embedded Zerotree Coding
5.11.3 OtherCoders
5.12 PerformanceAnalysis
5.12.1 JPEG
5.12.2 Embedded Zerotree Coding
5.13 Conclusions
References
6 Wavelet-Based Image Compression
6.1 Introduction
6.2 DyadicWavelet Transform
6.2.1 Two-Channel Perfect-Reconstruction Filter Bank
6.2.2 Dyadic WaveletTransform,Multiresolution Representation
6.2.3 Wavelet Smoothness
6.3 Wavelet-Based ImageCompression
6.3.1 Lossy Compression
6.3.2 EZW Algorithm
6.3.3 SPIHTAlgorithm
6.3.4 WDRAlgorithm
6.3.5 ASWDR Algorithm
6.3.6 LosslessCompression
6.3.7 ColorImages
6.3.8 OtherCompression Algorithms
6.3.9 Ringing Artifacts and Postprocessing Algorithms
References
7 Fractal-BasedImageand Video Compression
7.1 Introduction
7.2 BasicPropertiesof Fractalsand ImageCompression
7.3 ContractiveAffineTransforms,IteratedFunctionSystems,andImage
Generation
7.4 ImageCompression Directly Based on theIFS Theory
7.5 ImageCompression Based on IFS Library
7.6 ImageCompression Based on Partitioned IFS
7.6.1 ImagePartitions
7.6.2 Distortion Measure
7.6.3 AClassof DiscreteImage Transformation
7.6.4 Encodingand Decoding Procedures
7.6.5 Experimental Results
7.7 ImageCoding Using QuadtreePartitioned IFS(QPIFS)

7.7.1 RMS ToleranceSelection
7.7.2 ACompactStorage Scheme
7.7.3 ExperimentalResults
7.8 ImageCoding by Exploiting Scalability of Fractals
7.8.1 ImageSpatialSub-Sampling
7.8.2 Decoding to aLarger Image
7.8.3 ExperimentalResults
7.9 Video SequenceCompression using QuadtreePIFS
7.9.1 DefinitionsofTypes of Range Blocks
7.9.2 Encoding andDecoding Processes
7.9.3 StorageRequirements
7.9.4 ExperimentalResults
7.9.5 Discussion
7.10 OtherFractal-BasedImageCompression Techniques
7.10.1 Segmentation-Based Coding Using Fractal Dimension
7.10.2 Yardstick Coding
7.11 Conclusions
References
8 CompressionofWaveletTransformCoefficients
8.1 Introduction
8.2 Embedded CoefficientCoding
8.3 StatisticalContextModelingof Embedded Bit Stream
8.4 ContextDilution Problem
8.5 ContextFormation
8.6 ContextQuantization
8.7 Optimization ofContextQuantization
8.8 DynamicProgramming forMinimumConditional Entropy
8.9 FastAlgorithmsforHigh-Order Context Modeling
8.9.1 ContextFormation viaConvolution
8.9.2 SharedModeling Context for Signsand Textures
8.10 ExperimentalResults
8.10.1 Lossy Case
8.10.2 LosslessCase
8.11 Summary
References

The Data Compression Book

2008-03-15 09:13:06

Afterword
Why This Book Is For You

Chapter 1—Introduction to Data Compression

The Audience
Why C?
Which C?
Issues in Writing Portable C
Keeping Score
The Structure

Chapter 2—The Data-Compression Lexicon, with a History

The Two Kingdoms
Data Compression = Modeling + Coding
The Dawn Age
Coding
An Improvement
Modeling
Statistical Modeling
Dictionary Schemes
Ziv and Lempel
LZ77
LZ78
Lossy Compression
Programs to Know

Chapter 3—The Dawn Age: Minimum Redundancy Coding

The Shannon-Fano Algorithm
The Huffman Algorithm
Huffman in C
BITIO.C
A Reminder about Prototypes
MAIN-C.C AND MAIN-E.C
MAIN-C.C
ERRHAND.C
Into the Huffman Code
Counting the Symbols
Saving the Counts
Building the Tree
Using the Tree
The Compression Code
Putting It All Together
Performance

Chapter 4—A Significant Improvement: Adaptive Huffman Coding

Adaptive Coding
Updating the Huffman Tree
What Swapping Does

The Algorithm
An Enhancement
The Escape Code
The Overflow Problem
A Rescaling Bonus
The Code
Initialization of the Array
The Compress Main Program
The Expand Main Program
Encoding the Symbol
Updating the Tree
Decoding the Symbol
The Code

Chapter 5—Huffman One Better: Arithmetic Coding
Difficulties
Arithmetic Coding: A Step Forward
Practical Matters
A Complication
Decoding
Where’s the Beef?
The Code
The Compression Program
The Expansion Program
Initializing the Model
Reading the Model
Initializing the Encoder
The Encoding Process
Flushing the Encoder
The Decoding Process
Summary
Code

Chapter 6—Statistical Modeling

Higher-Order Modeling
Finite Context Modeling
Adaptive Modeling
A Simple Example
Using the Escape Code as a Fallback
Improvements
Highest-Order Modeling
Updating the Model
Escape Probabilities
Scoreboarding
Data Structures
The Finishing Touches: Tables –1 and –2
Model Flushing
Implementation
Conclusions
Enhancement
ARITH-N Listing

Chapter 7—Dictionary-Based Compression

An Example

Static vs. Adaptive
Adaptive Methods
A Representative Example
Israeli Roots
History
ARC: The Father of MS-DOS Dictionary Compression
Dictionary Compression: Where It Shows Up
Danger Ahead—Patents
Conclusion

Chapter 8—Sliding Window Compression

The Algorithm
Problems with LZ77
An Encoding Problem
LZSS Compression
Data Structures
A Balancing Act
Greedy vs. Best Possible
The Code
Constants and Macros
Global Variables
The Compression Code
Initialization
The Main Loop
The Exit Code
AddString()
DeleteString()
Binary Tree Support Routines
The Expansion Routine
Improvements
The Code

Chapter 9—LZ78 Compression

Can LZ77 Improve?
Enter LZ78
LZ78 Details
LZ78 Implementation
An Effective Variant
Decompression
The Catch
LZW Implementation
Tree Maintenance and Navigation
Compression
Decompression
The Code
Improvements
Patents

Chapter 10—Speech Compression

Digital Audio Concepts
Fundamentals
Sampling Variables
PC-Based Sound
Lossless Compression of Sound

Problems and Results
Lossy Compression
Silence Compression
Companding
Other Techniques

Chapter 11—Lossy Graphics Compression

Enter Compression
Statistical and Dictionary Compression Methods
Lossy Compression
Differential Modulation
Adaptive Coding
A Standard That Works: JPEG
JPEG Compression
The Discrete Cosine Transform
DCT Specifics
Why Bother?
Implementing the DCT
Matrix Multiplication
Continued Improvements
Output of the DCT
Quantization
Selecting a Quantization Matrix
Coding
The Zig-Zag Sequence
Entropy Encoding
What About Color?
The Sample Program
Input Format
The Code
Initialization
The Forward DCT Routine
WriteDCTData()
OutputCode()
File Expansion
ReadDCTData()
Input DCT Codes
The Inverse DCT
The Complete Code Listing
Support Programs
Some Compression Results

Chapter 12—An Archiving Package

CAR and CARMAN
The CARMAN Command Set
The CAR File
The Header
Storing the Header
The Header CRC
Command-Line Processing
Generating the File List
Opening the Archive Files
The Main Processing Loop
Skipping/Copying Input File

File Insertion
File Extraction
Cleanup
The Code

Chapter 13—Fractal Image Compression
A brief history of fractal image compression
What is an Iterated Function System?
Basic IFS mathematics
Image compression with Iterated Function Systems
Image compression with Partitioned Iterated Function Systems
Fractal image decoding
Resolution independence
The sample program
The main compression module
Initialization
Domain classification
Image partitioning
Finding optimal affine maps
The decompression module
The complete code listing
Some Compression Results
Patents
Bibliography
Appendix A
Appendix B
Glossary
Index

波谱原理与解析

2008-01-16 09:30:04

1.绪论
2.紫外线光谱法
3.红外和拉曼光谱
4.1H核磁共振
5.13C核磁共振与2维核磁共振
6.质谱法
7.综合解析
8.悬光光谱和圆2色光谱
9.X射线衍射法

编译程序构造原理和实现技术

2008-01-05 20:19:23

本书主要介绍过程式语言的编译程序构造原理和实现技术。本书共分10章，主要包括词法分析和语法分析的理论与技术，语义分析原理与技术，运行时的存储分配原则，动作文法和属性文法技术，中间代码生成、中间代码优化和目标代码生成，的原理与技术等。
本书的特点是概念清晰，层次分明，循序渐进，整体性强，便于教学，并反映当前的实用技术，适合作为高校计算机专业的教材，亦可作为有关专业人员进一步掌握编译程序构造原理与实现技术的参考书。

《算法设计与实验题解》(高清晰PDF)

2008-01-01 12:53:57

【下载说明】
这里提供给大家的是《算法设计与实验题解》一书的高清晰PDF格式电子书下载。

【内容提要】
本书是与普通高等教育“十一五”国家级规划教材《计算机算法设计与分析》（第2版）配套的辅助教材，对主教材中的全部习题做了解答或给出了解题思路提示，并对主教材的内容进行了扩展，有些主教材中无法讲述的较深入的主题以习题的形式展现出来。为了提高学生解决实际问题的能力，本书还将主教材中的许多习题改造成算法实现题，要求学生设计出算法并上机实现。作者还结合精品课程建设，进行了教材的立体化开发，包括主教材、辅助教材、实验与设计、电子课件和教学网站建设。本身附有光盘，包含各章算法实现题目、测试数据和答案。.
本书内容丰富，理论联系实际，可作为高等学校计算机科学与技术、软件工程、信息与计算科学等专业本科生和研究生学习计算机算法设计的辅助教材，也是工程技术人员的自学参考书。...

【前言摘要】
一些著名的计算机科学家在有关计算机科学教育的论述中认为，计算机科学是一种创造性思维活动，其教育必须面向设计。计算机算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。通过对计算机算法系统的学习与研究，理解和掌握算法设计的主要方法，培养对算法的计算复杂性进行正确分析的能力，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础，对从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者是非常重要和必不可少的。. 电子工业出版社出版的《计算机算法设计与分析》是普通高等教育“十一五”国家级规划教材，它是根据教育部高教司主持评审的《中国计.

【目录信息】
第1章算法概述
习题1-1 函数的渐近表达式
习题1-2 O（1）和O（2）的区别
习题1-4 按渐近阶排列表达式
习题1-5 算法效率
习题1-6 硬件效率
习题1-7 函数渐近阶
习题1-8 n！的阶
习题1-9 3n+1问题
习题1-10 平均情况下的计算时间复杂性
算法实现题1-1 统计数字问题
算法实现题1-2 字典序问题
算法实现题1-3 最多约数问题
算法实现题1-4 金币阵列问题
算法实现题1-5 最大间隙问题
第2章递归与分治策略
习题2-1 Hanoi塔问题的非递归算法
习题2-2 7个二分搜索算法
习题2-3 改写二分搜索算法
习题2-4 大整数乘法的O（mmlog（3/2）算法
习题2-5 5次n/3位整数的乘法
习题2-6 矩阵乘法
习题2-7 多项式乘积
习题2-8 不动点问题的O（logn）时间算法
习题2-9 主元素问题的线性时间法
习题2-10 无序集主元素问题的线性时间法
习题2-11 O（1）空间子数组换位算法
习题2-12 O（1）空间合并算法
习题2-13 n段合并排序算法
习题2-14 自然合并排序算法
习题2-15 最大值和最小值问题的最优算法
习题2-16 最大值和次大值问题的最优算法
习题2-17 整数集合排序
习题2-18 第k小元素问题的计算时间下界
习题2-19 非增序快速排序算法
习题2-20 随机化算法
习题2-21 随机化快速排序算法
习题2-22 随机排列算法
习题2-23 算法QuickSort中的尾递归
习题2-24 用栈模拟递归
习题2-25 算法Select中的元素划分
习题2-26 O（nlogn）时间快速排序算法
习题2-27 最按近中位数的k个数
习题2-28 X和Y的中位数
习题2-29 网络开关设计
习题2-32 带权中位数问题
习题2-34 构造Gray码的分治算法
习题2-35 网球循环赛日程表
习题2-36 二叉树T的前序、中序和后序序列
算法实现题2-1 输油管道问题（习题2-30）
算法实现题2-2 众数问题（习题2-31）
算法实现题2-3 邮局选址问题（习题2-32）
算法实现题2-4 马的Hamilton周游路线问题（习题2-33）
算法实现题2-5 半数集问题
算法实现题2-6 半数单集问题
算法实现题2-7 士兵部队问题
算法实现题2-8 有重复元素的排列问题
算法实现题2-9 排列的字典序问题
算法实现题2-10 集合划分问题
算法实现题2-11 集合划分问题
算法实现题2-12 双色Hanoi塔问题
算法实现题2-13 标准二维表问题
算法实现题2-14 整数因子分解问题
第3章动态规划
习题3-1 最长单调递增子序列
习题3-2 间长单调递增子序列的O（nlogn）算法
习题3-7 漂亮打印
习题3-11 整数线性规划问题
习题3-12 二维0-1 背包问题
习题3-14 Ackermann函数
习题3-17 最短行驶路线
习题3-19 最优旅行路线
算法实现题3-1 独立任务最优调度问题（习题3-3）
算法实现题3-2 最少硬币问题（习题3-4）
算法实现题3-3 序关系计数问题（习题3-5）
……
第4章贪心算法
第5章回溯法
第6章分支限界法
第7章概率算法
第8章线性规划与网络流
第9章 NP完全性理论与近似算法
参考文献

高性能计算之并行编程技术_MPI并行程序设计

2007-12-14 12:10:21

本书介绍目前最常见的并行程序――MPI并行程序设计方法，它适合高等院校计算机专业高年级本科生、非计算机专业研究生作为教材和教学参考书，也适合广大的并行计算(高性能计算)用户作为自学参考书。具有FORTRAN语言和C语言编程经验的人员都可以阅读并掌握本书的内容。书中首先介绍了并行程序设计基础，提供给读者进行并行程序设计所需要的基本知识；然后介绍MPI的基本功能，从简单的例子入手，告诉读者MPI程序设计的基本过程和框架，这一部分是具有C或FORTRAN串行程序设计经验的人员很容易理解和接受的；接下来介绍MPI程序设计的高级特征，这是已经掌握了MH基本程序设计的人员进一步编写简洁高效的MPI程序、使用各种高级和复杂的MPI功能所需要的；最后一部分介绍了MPI的最新发展和扩充MPI―2，其中包括三个部分，动态进程管理、远程存储访问和并行文件读写。本书包括了MPI―1的全部调用和MPI―2的关键扩充部分的调用，并附以大量的图表和示例性程序，对程序的关键部分给出了讲解或注释。读者若能将例子和对MPI调用的讲解结合起来学习，会取得更好的效果。本书的目的，不仅是教给读者如何去编写从简单到复杂的MPI并行程序，更重要的是，希望读者通过本书的学习，在以后解决问题的过程中能够树立并行求解的概念，使并行方法真正成为广大应用人员和程序开发员手中的重要工具。

Artificial Intelligence.A New Synthesis 英文版

2007-12-10 15:12:26

懂的都知道人工智能一本相当好的书，推荐看原版

正则表达式资料打包（正则全集）

2007-12-02 13:38:03

非常好的学习正则表达式的资料打包。该打包全集包括：

Mastering Regular Expressions(精通正则表达式) 3rd Edition 英文 CHM/PDF

正则表达式系统教程 CHM

表单验证Validator v1.0 基于正则表达式的例子 CHM

正则表达式参考文档 MHT

Codes and Curves

2007-11-21 22:44:58

Codes and Curves
These notes summarize a series of lectures I gave as part of the
IAS/PCMI Mentoring Program forWomen in Mathematics, held May
17-27, 1999 at the Institute for Advanced Study in Princeton, NJ
with funding from the National Science Foundation. The material
included is not original, but the exposition is new. The booklet [LG]
also contains an introduction to algebraic geometric coding theory,
but its intended audience is researchers specializing in either coding
theory or algebraic geometry and wanting to understand the connections
between the two subjects. These notes, on the other hand, are
designed for a general mathematical audience. In fact, the lectures
were originally designed for undergraduates.
I have tried to retain the conversational tone of the lectures, and
I hope that the reader will nd this monograph both accessible and
useful. Exercises are scattered throughout, and the reader is strongly
encouraged to work through them.
Judy L. Walker
Author address:
Department of Mathematics and Statistics, University
of Nebraska, Lincoln, NE 68588-0323
E-mail address: jwalker@math.unl.edu

Algorithmic Information Theory-Third Printing

2007-11-21 22:41:47

ALGORITHMIC INFORMATION THEORY, Third Printing
Chaitin, the inventor of algorithmic information theory, presents in this book the strongest possible version of G?del's incompleteness theorem, using an information theoretic approach based on the size of computer programs. One half of the book is concerned with studying the halting probability of a universal computer if its program is chosen by tossing a coin. The other half is concerned with encoding the halting probability as an algebraic equation in integers, a so-called exponential diophantine equation.

An exponential diophantine equation is explicitly constructed with the property that certain assertions are independent mathematical facts, that is, irreducible mathematical information that cannot be compressed into any finite set of axioms.

This is the first book on this subject and will be of interest to computer scientists, mathematicians, physicists and philosophers interested in the nature of randomness and in the limitations of the axiomatic method.

``Gregory Chaitin... has proved the ultimate in undecidability theorems..., that the logical structure of arithmetic can be random... The assumption that the formal structure of arithmetic is precise and regular turns out to have been a time-bomb, and Chaitin has just pushed the detonator.'' Ian Stewart in Nature

``No one, but no one, is exploring to greater depths the amazing insights and theorems that flow from G?del's work on undecidability than Gregory Chaitin. His exciting discoveries and speculations invade such areas as logic, induction, simplicity, the philosophy of mathematics and science, randomness, proof theory, chaos, information theory, computer complexity, diophantine analysis, and even the origin and evolution of life. If you haven't yet encountered his brilliant, clear, creative, wide-ranging mind, this is the book to read and absorb.'' Martin Gardner
Paperback: 190 pages
Publisher: Cambridge University Press; New Ed edition (December 2, 2004)
Language: English
ISBN-10: 0521616042
Product Dimensions: 9.6 x 7.4 x 0.6 inches
Shipping Weight: 13.4 ounces

现代计算机历史 A.History.of.Modern.Computing

2007-09-21 02:48:53

Bookmarks
A History of Modern Computing
A History of Modern Computing
Copyright
Dedication
Contents
Preface to the Second Edition
Acknowledgments
Introduction: Defining ???? Computer?ˉ?ˉ
The Computer Revolution and the History of Technology
Themes
1 The Advent of Commercial Computing, 1945–1956
The UNIVAC in Context
Punched Cards
The Card- Programmed Calculator
The Stored- Program Principle
John von Neumann?ˉs Role
The von Neumann Architecture and Its Significance
From ENIAC to UNIVAC: First Transformation 41
UNIVAC
The UNIVAC in Use
IBM?ˉs Response
Engineering Research Associates
The Drum Machines
CRC 102A
Later Drum Machines, 1953 ¨C 1956
LGP- 30
Bendix G- 15
IBM 650
Summary
2 Computing Comes of Age, 1956–1964
Core Memory
Honeywell, GE, RCA
GE
RCA
A Primer on Computer Architecture
Word Length
Register Structure
Number of addresses
Number of addresse
Floating- point Hardware
The Transistor
Philco
NCR, Burroughs
The Rise of IBM
Disk Storage In 1957 IBM
Disk Storage In 1957 IBM
Disk Storage In 1957 IB
Small Transistorized Machines
Conclusion
3 The Early History of Software, 1952–1968
Beginnings ( 1944 ¨C 1951)
UNIVAC Compilers ( 1952)
Laning and Zierler ( 1954)
Assemblers
SHARE ( 1955)
Sorting Data
FORTRAN ( 1957)
COBOL
Languages Versus Software
System Software
MAD
Computer Science
Other Events of 1968 and 1969
Donald E. Knuth
Structured Programming
Intellectual Property Issues
Software Engineering
Unbundling
Conclusion
4 From Mainframe to Minicomputer, 1959–1969
The Influence of the Federal Government
Massachusetts Blue Cross
NASA- Ames Research Center
The IRS
NASA?ˉs Manned Space Program
The Minicomputer
Architecture
The Digital Equipment Corporation
The PDP- 8
The DEC Culture
The MIT Culture
5 The ‘‘Go-Go’’ Years and the System/360, 1961–1975
IBM, the Seven Dwarfs, and the BUNCH
IBM System/ 360
System/ 360 and the Full Circle of Computing
Time- Sharing and System/ 360
The Period of Soaring Stocks
Leasing Companies
Compatible Mainframes
The Plug- Compatible Manufacturers
UNIVAC, SDS
Software Houses
The Fate of the BUNCH
Conclusion
6 The Chip and Its Impact, 1965–1975
The Invention of the Integrated Circuit
Commercial Impact of the Chip
Second- Generation Minicomputers
The Founding of Intel
The PDP- 11
Direct- Access Computing Triumphant
Computer Science Education
BASIC at Dartmouth
7 The Personal Computer, 1972–1977
Calculators and Corporate Personal Computer Projects
The Microprocessor
From Microprocessor to Personal Computer
Role of Hobbyists
Altair
Software: BASIC
System Software: The Final Piece of the Puzzle
End of the Pioneering Phase, 1977
8 Augmenting Human Intellect, 1975–1985
Digital Equipment Corporation
A Word about UNIX
IBM and the Classic Mainframe Culture
From ???? POTS?ˉ?ˉ to ???? OLTP?ˉ?ˉ
Viatron
Wang
Xerox PARC
Personal Computers: the Second Wave, 1977 ¨C 1985
APPLE II?ˉs Disk Drive and VisiCalc
IBM PC ( 1981)
MS- DOS
The PC and IBM
???? The Better is the Enemy of the Good?ˉ?ˉ
Macintosh ( 1984)
The Clones
9 Workstations, UNIX, and the Net, 1981–1995
UNIX: From New Jersey to California
The Ironies of UNIX
VAX Strategy
RISC
Networking I: Ethernet
Networking II: Internet
Networking III: the World Wide Web
Gopher, WAIS
World Wide Web, Mosaic
Conclusion
10 ‘‘Internet Time,’’ 1995–2001
Microsoft
The Macintosh Connection
Internet Explorer
Hotmail, UNIX
Dot. Com
The Acceptable Use Policy
Java
Search Engines, Portals
Tragedy of the Commons
GNU/ Linux
GNU
IBM
Conclusion
Conclusion: The Digitization of the World Picture
The Digitization of the World Picture
Notes
Preface
Introduction
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Conclusion
Bibliography
Index