Об этом курсе: 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.
Для кого этот курс: Learning to program is just a prerequisite for learning the fundamental precepts of computer science. This course is for people who know how to program and want a broad introduction to the discipline. It is based on the second half of our book Computer Science: An Interdisciplinary Approach.
Автор: Принстонский университет
Преподаватели: Robert Sedgewick, William O. Baker *39 Professor of Computer Science
Computer Science
Преподаватели: Kevin Wayne, Senior Lecturer
Computer Science
| Уровень | Intermediate |
| Выполнение | 10 weeks of study, 2-5 hours/week |
| Язык | English |
| Как пройти курс | Чтобы пройти курс, выполните все оцениваемые задания. |
| Оценки пользователей |
Программа курса
НЕДЕЛЯ 1
INFORMATION ABOUT LECTURES 1-10
This lesson provides information about the course Computer Science: Programming with a Purpose, which is the precursor to Computer Science: Algorithms, Theory, and Machines.
1 материал для самостоятельного изучения
- Reading: Information about Lectures 1-10
SORTING AND SEARCHING
We introduce and study classic algorithms for two fundamental problems, in the context of realistic applications. Our message is that efficient algorithms (binary search and mergesort, in this case) are a key ingredient in addressing computational problems with scalable solutions that can handle huge instances, and that the scientific method is essential in evaluating the effectiveness of such solutions.
5 видео, 3 материалов для самостоятельного изучения
- Reading: Getting Started
- Reading: Supplements for Lecture 11
- Видео: A typical client
- Видео: Binary search
- Видео: Insertion sort
- Видео: Mergesort
- Видео: Longest repeated substring
- Reading: Optional Enrichment on Sorting and Searching
- Discussion Prompt: Optional Enrichment on Sorting and Searching
Оцениваемый: Sorting and Searching
НЕДЕЛЯ 2
STACKS AND QUEUES
Our introduction to data structures is a careful look at the fundamental stack and queue abstractions, including performance specifications. Then we introduce the concept of linked structures and focus on their utility in developing simple, safe, clear, and efficient implementations of stacks and queues.
5 видео, 2 материалов для самостоятельного изучения
- Reading: Supplements for Lecture 12
- Видео: APIs
- Видео: Clients
- Видео: Strawman implementations
- Видео: Linked lists
- Видео: Implementations
- Reading: Optional Enrichment on Stacks and Queues
- Discussion Prompt: Optional Enrichment on Stacks and Queues
Оцениваемый: Stacks and Queues
НЕДЕЛЯ 3
SYMBOL TABLES
The symbol table abstraction is one of the most important and useful programmer's tools, s we illustrate with several examples in this lecture. Extending the scientific approach of the previous two lectures, we introduce and study binary search trees, a classic data structure that supports efficient implementations of this abstraction.
5 видео, 2 материалов для самостоятельного изучения
- Reading: Supplements for Lecture 13
- Видео: APIs and clients
- Видео: A design challenge
- Видео: Binary search trees
- Видео: Implementation
- Видео: Analysis
- Reading: Optional Enrichment on Symbol Tables
- Discussion Prompt: Optional Enrichment on Symbol Tables
Оцениваемый: Symbol Tables
НЕДЕЛЯ 4
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.
5 видео, 2 материалов для самостоятельного изучения
- Reading: Supplements for Lecture 14
- Видео: Overview
- Видео: Regular Expressions
- Видео: DFAs
- Видео: Applications
- Видео: Limitations
- Reading: Optional Enrichment on Theory of Computing
- Discussion Prompt: Optional Enrichment on Theory of Computing
Оцениваемый: Theory of Computing
НЕДЕЛЯ 5
TURING MACHINES
In 1936, Alan Turing published a paper that is widely hailed as one of the most important scientific papers of the 20th century. This lecture is devoted to the two far-reaching central ideas of the paper: All computational devices have equivalent computational power, and there are limitations to that power.
5 видео, 2 материалов для самостоятельного изучения
- Reading: Supplements for Lecture 15
- Видео: Context
- Видео: A simple model of computation
- Видео: Universality
- Видео: Computability
- Видео: Implications
- Reading: Optional Enrichment on Turing Machines
- Discussion Prompt: Optional Enrichment on Turing Machines
Оцениваемый: Turing Machines
НЕДЕЛЯ 6
INTRACTABILITY
As computer applications expanded, computer scientists and mathematicians realized that a refinement of Turing's ideas is needed. Which computational problems can we solve with the resource limitations that are inescapable in the real world? As described in this lecture, this question, fundamentally, remains unanswered.
5 видео, 2 материалов для самостоятельного изучения
- Reading: Supplements for Lecture 16
- Видео: Reasonable questions
- Видео: P and NP
- Видео: Poly-time reductions
- Видео: NP-completeness
- Видео: Living with intractability
- Reading: Optional Enrichment on Intractability
- Discussion Prompt: Optional Enrichment on Intractability
Оцениваемый: Intractability
НЕДЕЛЯ 7
A COMPUTING MACHINE
Every programmer needs understand the basic characteristics of the underlying computer processor being used. Fortunately, the fundamental design of computer processors has changed little since the 1960s. In this lecture, we provide insights into how your Java code actually gets its job done by introducing an imaginary computer that is similar to both the minicomputers of the 1960s and the microprocessor chips found in today's laptops and mobile devices.
5 видео, 2 материалов для самостоятельного изучения
- Reading: Supplements for Lecture 17
- Видео: Overview
- Видео: Data Types
- Видео: Instructions
- Видео: Operating the machine
- Видео: Machine language programming
- Reading: Optional Enrichment on A Computing Machine
- Discussion Prompt: Optional Enrichment on A Computing Machine
Оцениваемый: A Computing Machine
НЕДЕЛЯ 8
VON NEUMANN MACHINES
Continuing our description of processor design and low-level programming, we provide context stretching back to the 1950s and discuss future implications of the von Neumann machine, where programs and data are kept in the same memory. We examine in detail the idea that we design new computers by simulating them on old ones, something that Turing's theory guarantees will always be effective.
4 видео, 2 материалов для самостоятельного изучения
- Reading: Supplements for Lecture 18
- Видео: Perspective
- Видео: A note of caution
- Видео: Practical implications
- Видео: Simulation
- Reading: Optional Enrichment on von Neumann Machines
- Discussion Prompt: Optional Enrichment on von Neumann Machines
Оцениваемый: von Neumann Machines
НЕДЕЛЯ 9
COMBINATIONAL CIRCUITS
Starting with a few simple abstractions (wires that can carry on/off values and switches that can control the values carried by wires), we address in this lecture the design of the circuits that implement computer processors. We consider gates that implement simple logical functions and components for higher-level functions, such as addition. The lecture culminates with a full circuit for an arithmetic/logic unit.
4 видео, 2 материалов для самостоятельного изучения
- Reading: Supplements for Lecture 19
- Видео: Boolean algebra
- Видео: Digital circuits
- Видео: Adder circuit
- Видео: Arithmetic/logic unit
- Reading: Optional Enrichment on Combinational Circuits
- Discussion Prompt: Optional Enrichment on Combinational Circuits
Оцениваемый: Combinational Circuits
НЕДЕЛЯ 10
CENTRAL PROCESSING UNIT
In this lecture, we provide the last part of our answer to the question "How does a computer work?" by developing a complete circuit for a computer processor, where every switch and wire is visible. While vastly different in scale, this circuit, from a design point of view, has many of the same characteristics as the circuits found in your computer and your phone.
4 видео, 2 материалов для самостоятельного изучения
- Reading: Supplements for Lecture 20
- Видео: Overview
- Видео: Bits, registers, and memory
- Видео: Program counter
- Видео: Components and connections
- Reading: Optional Enrichment on the CPU
- Discussion Prompt: Optional Enrichment on the CPU
Оцениваемый: CPU
Часто задаваемые вопросы
Как это работает
Coursework
Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.
Help from Your Peers
Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.
Авторы
Принстонский университет
Princeton University is a private research university located in Princeton, New Jersey, United States. It is one of the eight universities of the Ivy League, and one of the nine Colonial Colleges founded before the American Revolution.
Рейтинги и отзывы
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
Best Teaching style.