Transcript Introduction

snick

snack
CPSC 121: Models of Computation
2009 Winter Term 1
Introduction & Motivation
Steve Wolfman, based on notes by
Patrice Belleville and others
1
Learning Goals: In-Class
By the end of the unit, you should be able to:
– Give an example of how we can apply formal
reasoning and computers to a simple, realworld task.
– Give an example of how a computational
solution to a simple task might go wrong.
– Describe the two “big stories” of CS121:
reasoning about computation and building
computers.
2
Outline
•
•
•
•
•
Introductions
Introductions Exercise
The CS121 Story
Course Administration
I Can’t Believe It’s Not a Pop Quiz
(but it isn’t)
• Next Lecture Notes
3
Introductions
Steven Wolfman
[email protected]
ICICS 239; office hours;
some every day, listed on the website
I also have an open door policy:
If my door is open, come in and talk!
Also, I will usually be available after class.
And, you can make appointments with me.4
Outline
•
•
•
•
•
Introductions
Introductions Exercise
The CS121 Story
Course Administration
I Can’t Believe It’s Not a Pop Quiz
(but it isn’t)
• Next Lecture Notes
5
More Introductions
Introduce yourselves… how?
6
Introduce Yourselves
in Groups of 4-ish
FIND ~3 people around you, preferably
people you’ve never met. Form a group.
Have everyone in the group introduce
themselves to everyone else in the group.
(Count the number of intros this takes.)
Tell everyone why you’re here, your favorite
career that you’ll never have, and one
unusual thing about you.
7
Problem: How Many
Introductions?
Problem: How many introductions does it
take for everyone in a group to meet
everyone else in a group?
8
Concept Q: Intros for 4
How many introductions does a group of 4
people take?
a. 3
b. 4
c. 6
d. 12
e. None of these
9
Problem: How Many
Introductions?
Problem: How many introductions does it
take for everyone in a group to meet
everyone else in a group?
10
To solve this problem, we need to model it more formally.
How Many Introductions?
Model: One “introduction” is one person
introducing themselves to another person. (Two
people need two introductions to introduce
themselves to each other.)
A group has “introduced themselves” when every
group member has introduced themselves to
every other member. (No self-introductions!)
Hi, I’m
Grace H.
Intro #1
Intro #2
Hi Grace,
I’m Alan T.
11
How Many Introductions?
Problem: How many introductions does it
take for a group of n people to introduce
themselves?
12
How Many Introductions?
For 2 people?
For 3 people?
For 4 people?
For 5 people?
…
For n people?
13
How Many Introductions?
For 100 people?
For 8675309 people?
For 1526097757 people?
14
Program for Introductions
introductions n = n * (n - 1)
(In a programming language called Haskell.)
int introductions(int n)
{
return n * (n - 1);
}
(In the Java programming language.)
Do you believe it?
15
Program for Introductions:
Testing
Java version with 100: 9900
Do you believe it?
16
Program for Introductions:
Testing
Java version with 100: 9900
Java version with 8675309: 265642364
Do you believe it?
17
Program for Introductions:
Testing
Java version with 100: 9900
Java version with 8675309: 265642364
Java version with 1526097757: -645820308
Um.. Do you believe it?
18
Does this fit with your “model” of Java computation?
Program for Introductions:
Testing
Haskell version with 100: 9900
Haskell version with 8675309:
75260977570172
Haskell version with 1526097757:
2328974362394333292
Do you believe it?
19
Will Haskell always get the right answer?
Outline
•
•
•
•
•
Introductions
Introductions Exercise
The CS121 Story
Course Administration
I Can’t Believe It’s Not a Pop Quiz
(but it isn’t)
• Next Lecture Notes
20
Questions that CPSC121
Answers
How can we prove that our formula for the
number of introductions is correct? (induction)
What went wrong in our Java implementation?
(number representation)
How do we model and reason about
computational systems at various levels of
abstraction? (propositional and predicate logic,
proof, sets, functions, DFAs, relations, ...)
21
CPSC 121: The Big Stories
Theory
How do we model
computational systems
(programs/computers) in
order to design and
analyze them?
End goal: Reason about
what is and isn’t
possible to compute.
Hardware
How do we build devices
that can compute out of
real materials (“sand and
rocks and water”)?
End goal: break
down a full computer
into simple “gates”.
Bonus end goal: Develop tools to communicate
computational ideas clearly and precisely.
22
Our Working Computer
23
CPSC 121: The (By?)Products
Theory
Products:
• Propositional logic
• Predicate logic
• Sets and functions
• Proof techniques
(especially induction!)
• Finite Automata/Regular
Expressions
• Universal machines
• Uncomputability
Hardware
Products:
• Gates
• Combinational circuits
• Binary data
representations
• Sequential circuits
• A full computer
24
What is CPSC 121 Good For?
With CPSC121’s help, you will be able to:
• model important problems so that they are easier
to discuss, reason about, solve, and test.
• learn new modeling formalisms more easily.
• communicate clearly and unambiguously with
other CS experts on complex topics.
• characterize algorithms (CS problem solutions),
such as proving their correctness or efficacy.
• critically read proofs: justifying why each step is
correct and judging what the proof means.
25
Outline
•
•
•
•
•
Introductions
Introductions Exercise
The CS121 Story
Course Administration
I Can’t Believe It’s Not a Pop Quiz
(but it isn’t)
• Next Lecture Notes
26
Course Administration
Explore the CPSC 121 website:
http://www.ugrad.cs.ubc.ca/~cs121/
You are required to be familiar with the
course website. Ignorance of information
on the website may harm you.
27
Additional Administrative Notes
The first quiz is “any marks gives full marks”.
So, if you get more than 0%, we’ll count it
as 100%.
Labs, tutorials, and the Demco Learning
Centre all start NEXT week.
TA assignments will be up by the end of the
week (but may change through ~week 2).
28
Outline
•
•
•
•
•
Introductions
Introductions Exercise
The CS121 Story
Course Administration
I Can’t Believe It’s Not a Pop Quiz
(but it isn’t)
• Next Lecture Notes
29
Outline
•
•
•
•
•
Introductions
Introductions Exercise
The CS121 Story
Course Administration
I Can’t Believe It’s Not a Pop Quiz
(but it isn’t)
• Next Lecture Notes
30
Learning Goals: In-Class
By the end of the unit, you should be able to:
– Give an example of how we can apply formal
reasoning and computers to a simple, realworld task.
– Give an example of how a computational
solution to a simple task might go wrong.
– Describe the two “big stories” of CS121:
reasoning about computation and building
computers.
31
Next Lecture Learning Goals:
Pre-Class
By the start of class, you should be able to:
– Translate back and forth between simple
natural language statements and
propositional logic.
– Evaluate the truth of propositional logic
statements using truth tables.
– Translate back and forth between
propositional logic statements and circuits that
assess the truth of those statements.
32
Next Lecture Prerequisites
Read Sections 1.1 and 1.4
Solve problems like Exercise Set 1.1, #1-18
and Exercise Set 1.4, #1-17.
You should have completed the open-book,
untimed quiz on Vista that’s due by 9PM
the day before class.
(You are responsible for ensuring that you
have submitted the quiz by 9PM!)
33
snick

snack
Some Things to Try...
(on your own if you have time,
not required)
34
What Works is
NOT Always Obvious
Let’s sort cards with the Quicksort “Algorithm” :
1. If there are no cards in a deck, it’s sorted.
2. Otherwise, pick a card at random.
a. Divide the other cards into a deck of cards less than or equal to
that card and a deck of cards greater than it.
b. Give the “less” deck to a helper and have them Quicksort it.
c. Give the “greater” deck to a helper and have them Quicksort it.
d. Put the Quicksorted “less” deck on top of the picked card on
top of the Quicksorted “greater” deck.
How can that work?
It relies on itself to get its work done!
TRY it with a deck of cards.
To compare cards, first: A < 2–10 < J < Q < K
35
If they’re equal so far: Clubs < Diamonds < Hearts < Spades
What Doesn’t Work is
NOT Always Obvious (1 of 2)
Class Main {
public static void main(String[] args) {
// Let's add up 4 quarters.
System.out.println("4 quarters gives us:");
System.out.println(0.25 + 0.25 + 0.25 + 0.25);
// Let's do something a hundred times.
int i = 100;
do {
// Make i one smaller.
i--;
} while (i > 0);
System.out.println("Done!");
System.out.println("i ended up with the value: " + i);
System.out.println("It went down by: " + (100 - i));
}
}
Predict and then TRY: What does this print?
36
(If you’re just taking 111, give it a week and then try.)
What Doesn’t Work is
NOT Always Obvious (2 of 2)
Class Main {
public static void main(String[] args) {
// Let's add up 10 dimes.
System.out.println("10 dimes gives us:");
System.out.println(0.1 + 0.1 + 0.1 + 0.1 + 0.1 +
0.1 + 0.1 + 0.1 + 0.1 + 0.1);
// Let's try do something a hundred times..
// but accidentally go forever
int i = 100;
do {
// Make i one LARGER. Oops!
i++;
} while (i > 0);
System.out.println("Done!");
System.out.println("i ended up with the value: " + i);
System.out.println("It went down by: " + (100 - i));
}
}
37
Predict and then TRY: What does this print?
Even Bigger Story:
“Clear Thought”
Computer Science is the science of “clear
thought”, but not like philosophy (or religion,
or poetry, or...).
CS is the science of thoughts so clear in their
expression and intent that we can realize
them: execute them or test their truth in the
world.
CPSC121 provides and applies the
fundamentals you need to model the world
with “clear thought”.
38