Overview

Loading...

Do curso por Princeton University

Computer Science: Algorithms, Theory, and Machines

51 classificação

Princeton University

Computer Science: Algorithms, Theory, and Machines

51 classificação

This course introduces the broader discipline of computer science to people having basic familiarity with Java programming. It covers the second half of our book Computer Science: An Interdisciplinary Approach (the first half is covered in our Coursera course Computer Science: Programming with a Purpose, to be released in the fall of 2018). Our intent is to demystify computation and to build awareness about the substantial intellectual underpinnings and rich history of the field of computer science. First, we introduce classic algorithms along with scientific techniques for evaluating performance, in the context of modern applications. Next, we introduce classic theoretical models that allow us to address fundamental questions about computation, such as computability, universality, and intractability. We conclude with machine architecture (including machine-language programming and its relationship to coding in Java) and logic design (including a full CPU design built from the ground up). The course emphasizes the relationships between applications programming, the theory of computation, real computers, and the field's history and evolution, including the nature of the contributions of Boole, Shannon, Turing, von Neumann, and others.

Na lição

INTRODUCTION TO THE THEORY OF COMPUTING

The theory of computing helps us address fundamental questions about the nature of computation while at the same time helping us better understand the ways in which we interact with the computer. In this lecture, we introduce formal languages and abstract machines, focusing on simple models that are actually widely useful in practical applications.

Regular Expressions20:47

Applications12:59

Limitations9:44

Conheça os instrutores

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science
Kevin Wayne
Senior Lecturer
Computer Science

For the next several lectures,

we're going to talk about theoretical computer science.

In many scientific disciplines,

people working in the discipline maybe can dismiss theory as

something maybe not relevant to what they do daily.

For computer science that's not really true.

Theory is an integral part of our discipline and everyone should have

a basic understanding of the type

that we're going to talk about in the next couple of lectures.

We'll begin with a brief overview of the basic issues.

We're going to be talking about very fundamental questions relating to computation,

like what can a computer do or if we have

limited resources what can we do with a computer.

There's a very general approach that mathematicians and

computer scientists have used over the last five or six decades actually.

First of all, we don't want to talk about specific machines or problems.

We want to consider what's called abstract machines that have

very minimal capabilities and we'll see some examples of that in this lecture.

So, this is an example of a machine that we'll see at the end.

And we'll consider very general classes of problems.

So, the idea is to come up with the simplest machine

that shares the characteristics of the actual machines that we

use and the classes of problems that embody

the classes of problems that we care about and try to say general statements.

And the surprising outcome of this approach is,

that we're going to have sweeping and very relevant statements about all computers.

It's quite actually an amazing outcome that we'll get to in the next couple of lectures.

And it doesn't matter whether it's a supercomputer,

or a new laptop, or your phone,

or an old PC,

or an old mainframe,

or even one of the first computers.

All these computers share

the same basic properties that we'll be able to articulate really quite precisely.

So, in general there's a question of why study theory,

even Yogi Berra had a comment on it.

"In theory there's no difference between theory and practice.

In practice there is."

And we'll see that right away in this lecture.

Certainly for theoretical computer science,

we get a very deep understanding of computation that

actually is the foundation of all the modern computers that we use.

It really helps us understand

the natural world and there's philosophical implications as well.

In practice, there's all kinds of

practical tools that have evolved out of the theoretical studies.

So when you do web search,

you need the theory of pattern matching which is very related to

these basic computational questions circuits that we use to build

computers or compilers that we use to translate from one programming language to another.

Cryptography is based on theory,

data compression, and many,

many other fields have evolved from

the basic understanding that we get from theoretical studies.

So in this lecture, we're going to talk at both levels.

We'll talk a little bit about theoretical questions,

a little bit about practical questions and

end up with some basic questions about computation.

So, one thing we're going to talk about I already

mentioned is the idea of abstract machines.

So what an abstract machine is,

is really a mathematical model of computation.

Actually for the lecture,

we have kind of a graphical model that mimics what you might imagine a real machine.

So, there's different types of machines,

they have different capability.

Each machine is defined by very specific rules for taking input and producing output.

This lecture we're going to talk about the simplest kind of abstract machine called a

Deterministic Finite Automata and

that's pictured at the right and we'll look at details in a minute.

There's another idea called a formal language.

A formal language is just a set of strings.

Over on the right we have an example of a set of strings.

So, that's the set of English language palindromes saying,

does the thing read the same forward and backwards?

So, that's a specific rule that characterizes this set of strings;

reads the same forward and backwards.

And you could have many other and matching many other types

of rules if you can articulate

the rules then you're defining a set of strings as a formal language.

So, we're going to talk about a particular set of rules called regular expressions

today and those turn out to be very useful in many applications.

In this lecture, we're going to address

some basic questions related to these obstructions.

For example, we might want to know,

is a given string in the language defined by a given regular expression or not?

That already is an interesting question to approach.

And we might say, well,

if we had a computer could we answer this question?

In particular, could a simple computer like a DFA answer this question?

Already with these very simple models we come to

interesting questions with useful practical applications.

That's what most of this lecture is about.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play