通过计算机科学应用理解矩阵编码：基础与实践

5星 · 超过95%的资源需积分: 31 31 浏览量更新于2024-07-21 5 收藏 8.56MB PDF 举报

"《编码矩阵：通过计算机科学应用理解线性代数》是一本由Philip N. Klein编著的教材，针对著名在线课程设计，旨在通过实践案例将线性代数的基本概念与计算机科学相结合。该书以其丰富的应用实例和配套的在线资源，如coddingthematrix.com网站，提供数据、示例和自动评分功能，帮助读者深入理解和掌握线性代数。第1章"函数与数学与计算基础"是教学的起点，首先介绍了集合术语和符号表示，以及它们在计算机科学中的运用。作者区分了函数、过程和计算问题，强调了函数的核心概念，如给定域和值域。书中详细解释了函数的构成，包括基本的函数形式，如身份函数和复合函数，以及它们的结合律。此外，函数逆的存在及其与可逆函数复合的关系也是这一部分的重点。在第2节“概率”中，作者引导读者探讨概率分布的概念，如何通过概率加法来描述事件的可能性，以及如何将随机输入与函数结合起来。"完美保密"的概念在此处被用来阐述在某些安全通信协议中的应用，进一步展示了理论知识在实际情境中的实用性。本书不仅涵盖了线性代数的基础理论，还通过编程和算法应用将其生动化，适合计算机科学专业的学生、教师以及对线性代数有实际需求的工程师和技术人员使用。由于其实用性和互动性强的特点，它在亚马逊同类书籍中销量名列前茅，是学习者提升线性代数技能的优质资源。"

CONTENTS xiii

12.14Probl em s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607

13 The Lin ear Program 612

13.1 The diet problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612

13.2 Formulating the diet problem as a linear program . . . . . . . . . . . . . . . . . . 613

13.3 The origins of linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . 614

13.3.1 Ter mi n ol ogy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615

13.3.2 Linear programming in diﬀerent forms . . . . . . . . . . . . . . . . . . . . 615

13.3.3 Integer linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . 616

13.4 Geometry of linear programming: polyhedra and vertices . . . . . . . . . . . . . 616

13.5 There is an optimal solution that is a vertex of the polyhedron . . . . . . . . . . 620

13.6 An enumerative algori t h m for linear programming . . . . . . . . . . . . . . . . . 620

13.7 Introduction to linear-programm i ng duality . . . . . . . . . . . . . . . . . . . . . 621

13.8 The simplex algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623

13.8.1 Ter mi n at i on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624

13.8.2 Representing the current solution . . . . . . . . . . . . . . . . . . . . . . . 624

13.8.3 A pivot step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625

13.8.4 Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627

13.9 Finding a vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630

13.10Game theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632

13.11Formulation as a linear program . . . . . . . . . . . . . . . . . . . . . . . . . . . 635

13.12Nonzero- su m games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636

13.13Lab: Learning through linear programming ...................... 636

13.13.1 Reading in the training data .......................... 637

13.13.2 Setting up the linear program ......................... 638

13.13.3 Main constraints ................................ 639

13.13.4 Nonnegativity constraints ........................... 640

13.13.5 The matrix A .................................. 640

13.13.6 The right- hand side vector b ......................... 640

13.13.7 The objective function vector c ........................ 641

13.13.8 Putting i t together ............................... 641

13.13.9 Finding a vertex ................................ 641

13.13.10Solving the linear program ........................... 641

13.13.11Using the result ................................. 641

13.14Compres se d sensin g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642

13.14.1 More quickly acquiring an MRI image . . . . . . . . . . . . . . . . . . . . 642

13.14.2 Computation to the r esc ue . . . . . . . . . . . . . . . . . . . . . . . . . . 643

13.14.3 Onwards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644

13.15Revie w quest ion s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644

13.16Probl em s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644

Int roducti on

Tourist on Fif ty-Seventh Street,

Manhattan: “Pardon me—could you tell

me how to get to Carnegie Hall?”

Native New Yorker: “Prac ti c e, pract ic e! ”

There’s a scene in the movie The Matrix in which Neo is strapped in a chair and Morpheus

inserts into a machine what looks like a seventies-era videotape cartridge. As the tape plays,

knowledge of how to ﬁght streams into Neo’s brain. After a very short time, he has become an

expert.

I would be delighted if I could strap my students into chairs and quickly stream knowledge

of linear algebra into their brain, but brains don’t learn that way. The input device is rarely the

bottleneck. Students need lots of pract i ce—b u t what kind of practice?

No doubt students need to practice t h e basic numerical cal cu lat i ons , such as matrix-matrix

multiplication, that underlie elementary linear algebra and that seem to ﬁll all their time in

traditional cookbook-style courses on linear algebra. No doubt students need to ﬁnd proofs and

counterexamples to exercise their understanding of the abstract concepts of which linear algebra

is cons t ru ct e d.

However , they also need practi ce in using li ne ar algebra to thin k about problems in oth er

domains, and in actually using linear-algebra computations to address these problems. These

are t h e skills they most need from a linear-algebra class when they go on to study other topics

such as graphics an d machine learning. This book is aimed at students of computer science; such

students are best served by seeing application s from their ﬁeld because these are the applications

that w il l be most meaningful for them.

Moreover, a linear-algebra inst r uc t or whose pupils are students of computer science has a

special advantage: her students are com pu t at ion al l y sop h is t i cat ed . They have a learning modal-

ity that most students don’t—they can learn t hr ou gh reading, writing, debugging, and using

computer programs.

For example, there are several ways of writing a program for matrix -vector or matrix-matrix

multiplication, each providing its own kernel of insight into the meaning of the operation—and

the experience of writing such programs is more eﬀective in conveying this meaning and cementing

the relat i on sh ip s between the operations than spending the equivalent time carrying out hand

calculations.

Computational sophistication also helps students in the more abstract, mathematical asp e ct s

xiv

CONTENTS xv

of linear algebra. Acquaintance with object-oriented programming helps a student grasp the

notion of a ﬁeld—a set of values together with operations on them. Acquaintance with subtyping

prepares a student to understand that some vector space s ar e inner product spaces. Familiarity

with loops or recursion helps a student understan d procedural proofs, e.g. of the existence of a

basis or an orthogonal basis.

Computational thinki ng is the term suggested by Jeannette Wing, former head of the National

Science Foundation’s directorate on Computer and Information Science and Engineering, to refer

to t he skills and conc ep t s that a student of computer science can bring to bear. For this book,

computational thinking is the road t o master in g elementary linear algebra.

Companion website

The companion website is at codingthematrix.com. There you will ﬁnd, in digital form, the

data, e x ampl e s, and support code you need to solve the problems given in the book.

Intended audience

This book is accessible to a student who is an experienced programmer. Most students who take

my course have had at least two semesters of introduc t ory comp u t er sci en ce , or have previously

learned programming on their own. In addition, it is desirable that the student has has some

exposure (in prior semesters or concurrently) in proof techniques such as are studied in a Discrete

Math c our se .

The student’s prior programming experi en ce can be in pr et ty much any programming lan-

guage; this book uses Python, and the ﬁ r st two l ab s are devoted to bringing the student up to

speed in Python programming. Moreover, th e programs we write in this book are not particularly

sophisticated. For exampl e , we provide stencil cod e t h at obviates the need for the student to

have studied object-orie nted programmin g.

Some sections of the text, marked with

, provide supplementary mathematical material but

are not cruci al for the reader’s understandi n g.

Labs

An important p art of the book is the labs. For each chapter, there i s a l ab ass ign me nt in whi ch

the student is expecte d to wri t e small pr ogr ams and use some modules we provide, generally

to carry out a task or series of tasks related to an appl ic at i on of the concepts recently covered

or about to be covered. Doi ng the labs “keeps it real”, grounding the student’s study of linear

algebra in getting something done, somethi ng meaningful in it s own ri ght but also illustrat i ve of

the con ce pt s .

In my course, there is a lab sect i on each week, a two-hour per i od in which the students carry

out the lab assignment. Course staﬀ are available during this period, not to supervise but to assist

when necessary. The goal is to help the students move through the lab assignment eﬃc i ently, and

to get them unstuck when they encounter obstacles. The students ar e expected to have prepared

by reviewing the previous week’s course material and reading through the lab assignment.

Most students experience the labs as the most fun part of the course—it is where the y

discover the power of t he knowledge they are acquiring to help th em accomplish somethin g that

CONTENTS xvi

has meani n g in the world of computer science.

Programming language

The book uses Python, not a programming language with built-in support for vectors and matri-

ces. This gives students the opportunity to build vectors and matrices out of the data structures

that Python does provide. Using their own implementations of vector and matrix provides trans-

parency. Python does provide complex numbers, sets, lists (sequences), and dictionaries (which

we use for representing functions). In addition, Python provides comprehensions, expressions

that create sets, lists, or dictionaries using a simple and powerful syntax that resembles the

mathematical notat i on for deﬁning sets. Using this syntax, many of the procedures we write

require only a singl e line of code.

Students are not expected to k n ow Python at the beginning; the ﬁrst two labs form an

introduction to Python, and the examples throughout the text reinforce the ideas.

Vector and Matrix representations

The traditional concrete representation for a vector is as a sequence of ﬁeld elements. This book

uses that representation but also uses another, especially in Python programs: a vector as a

function mapping a ﬁnite set D to a ﬁeld . Similarly, the traditional representation for a matrix

is as a two-dimensional array or grid of ﬁeld elements. We use this representation but also use

another: a matrix as a funct i on from the Cartesian product R × C of two ﬁnite sets to a ﬁeld.

These more ge ne ral representations allow the vectors and matrices to be more directly con-

nected to the ap pli c at ion . For example, it is traditional in information retrieval to represent a

document as a vector in which, for each word, the vector speciﬁes the number of occurences of

the word in the document. In this book, we deﬁne such a vector as a function from the domain

D of English words to the set of real numbers. Another example: when representing, say, a

1024×768 black-and-white image as a vector, we deﬁne the vector as a function from the domain

D = {1,...,1024}×{1,..,768} to the real numbers. The funct i on speciﬁes, for each pixel (i, j),

the i mage intensity of that pixel.

From the programmer’s perspective, i t is certainly more convenient to direct l y index vectors

by strings (in the case of words) or tuples (in t h e case of pixels). However, a more important

advantage is this: having to choose a domain D for vectors gets us thinking ab ou t the appl i cat i on

from t he vector perspective.

Another advantage is analogou s to that of type-checki ng in programs or unit-checki n g in

physical calculati ons . For an R ×C matrix A, the mat r i x- vector product Ax is only legal if x is

a C-vector; the matrix-matrix product AB is only legal if C is the set of row-labels of B.These

constraints further reinforce the meanings of the operations.

Finally, allowing arbitrary ﬁn i te sets (not just sequences of consecutive integers) to label the

elements helps make it clear that the order of elements in a vector or matrix is not always (or

even often) signiﬁcant.

剩余688页未读，继续阅读

麓山阿土

粉丝: 3
资源: 11

通过计算机科学应用理解矩阵编码：基础与实践

【2018新书】写给计算机科学的概率统计（Probability and Statistics for Computer Science）

Coding the Matrix: Linear Algebra through Applications to Computer Science

Coding the Matrix全部课程讲义

JNA调用jerasure库中的jerasure_matrix_decode()方法示例代码

jerasure库中的int jerasure_matrix_decode(int k, int m, int w, int *matrix, int row_k_ones, int *erasures, char **data_ptrs, char **coding_ptrs, int size); 方法作用是什么

Error[Pe007]: unrecognized token E:\HOD_ALPS_ASPICE\04_Software\05_Coding\01_SrcCode\NIO_ALPS_Z20K118\Source\APP\AMSG\CanMsg.c 296

ValueError: path '/Users/jonathanraiman/Desktop/Coding/python_packages/glove/glove/glove_inner.cpp' cannot be absolute [end of output]

line_coding如何设置波特率 2400

解释这段代码jpg_obj = jpeg_read(name_cover); jpg_obj.optimize_coding = is_optimized; dct = jpg_obj.coef_arrays{1,1};

最新资源

jerasure库中的int jerasure_matrix_decode(int k, int m, int w, int matrix, int row_k_ones, int erasures, char data_ptrs, char coding_ptrs, int size); 方法作用是什么