Transcript Power Point slides

CS 1800
Discrete Structures
(Discrete Mathematics)
Dr. Schafer
Getting to know you
Pull out a sheet of notebook paper and
fold it in half the “long” way .
Using one of the markers I will pass
around, write your “first name and
last initial” (or the name you would
like to be called).
While I come around and take your
“mug shot” please complete the info
sheet that I will pass out.
What would be on my info sheet?
1.
2.
3.
4.
5.
Name : Dr. Ben Schafer
Hometown : Ames originally but …
Class : Sixteenth year (plus 5 as an undergrad)
High School Math: Algebra II/Trig. Mostly As
College Math?: Lots, including Discrete.
Mostly As
6. Other things about me you should know :
My handwriting can be messy
My voice can get loud.
The course “websites”
• Main course website
– www.cs.uni.edu/~schafer/1800
• Course Textbook
– zybooks.zyante.com
A brief look at course logistics
• Take the time outside of class to thoroughly
read the course syllabus posted to the class
website.
• Some highlights…
Syllabus - Instructor Information
• Formal office hours
– MWF 9:00-9:50, 11:00-11:50 and 1:00-1:30
(ITTC 316)
• No appointment NECESSARY but you can
make one by sending me an email.
– Having said that, I follow an open door policy
The Textbook
• We will be using an online textbook from
Zyante.
• You can read it online or, optionally, print it
for reading offline.
• The cost of this textbook is $48 for the
semester.
• You will need access to this BY
WEDNESDAY.
The Textbook
• Each section is relatively short, but it
includes online, embedded activities.
The Textbook
The Textbook
• You are to complete the reading and the
preparation activities by 11:00 AM on the day
they are due.
– Note that this is before class.
• This helps me see where students are at and gauge
what topics we will cover in more detail in class
that day.
• Approximately 10% of your grade will be based
on your on-time completion of these activities.
Syllabus – Evaluation
Quantity
Approximate Points
In Class Exams
4
400 each
Final Exam
1
150 each
Activity
Textbook
Participation
In-Class
Participation
Other Activities
Adjusted to 50 points*
Adjusted to 50 points*
Up to 50 points
Guidelines for Success in this Course
Be on time.
Class sessions will start promptly at 12:00.
I will often start with important announcements.
Do the readings, complete the prep activities, and take notes
in a dedicated notebook
• Your exams will be open notebook – you may use
anything that you hand-write in your class notebook.
Ask questions EARLY.
Important announcements
• For Wednesday
– Obtain
• Your textbook
• A class notebook.
– Complete section 1.1.
• Take any notes you like into your class notebook
Questions?
What the #$% is Discrete Mathematics??
• Discrete structures is simply the mathematics that is
necessary for decision making in non-continuous
situations.
• Discrete structures includes sets, functions, matrix
algebra, combinatorics and finite probability, graph
theory, logic, mathematical induction, and
algorithmic thinking.
What is Discrete Mathematics about??
• Relation to compute science:
– Propositional logic ~ hardware (including VLSI) design
– Predicate logic ~ Artificial Intelligence, compilers
– Proofs ~ Artificial Intelligence, VLSI, compilers, theoretical
physics/chemistry
– Formal “correctness” ~ programming, reverse-engineering,
debugging
– Sets/relations ~ databases (Oracle, MS Access, etc.)
– Counting and combinations ~ Programming, Artificial Intelligence
What is Discrete Mathematics about??
• We will start the semester studying logic
and “arguments”
Argument Example#1
• All men are mortal
• Socrates is a man
• Therefore,
Socrates is mortal
Argument Example #2
• Nothing is better than God
• A sandwich is better than nothing
• Therefore,
a sandwich is better
than God
Validity
• An argument is valid if and only if
– given that its premises hold
– its conclusion also holds
• So…
– Socrates argument: Valid or Invalid?
– Sandwich argument: Valid or Invalid?
How can we tell ?
•
•
•
•
•
Common sense?
Voting?
Authority?
What is valid argument anyway?
Who cares?
• ???
What does this have to do with
this class?
• Logic : a formal way to assess a validity of
an argument
• Can prove theorems in a semi-automatic
fashion
• Can verify given proofs that an argument is
valid
Code Correctness
• Millions of programmers
code away daily…
• How do we know if their
code works?
23
Importance
•
•
•
•
•
USS Yorktown, a guided-missile cruiser -- the first to be outfitted with Smart Ship
technology
09/97: suffered a widespread system
failure off the coast of Virginia.
After a crew member mistakenly entered a
zero into the data field of an application,
the computer system proceeded to divide
another quantity by that zero.
The operation caused a buffer overflow, in
which data leaked from a temporary
storage space in memory, and the error
eventually brought down the ship's
propulsion system.
The result: the Yorktown was dead in the
water for more than two hours.
More Software Bugs…
•
On June 4, 1996, the maiden flight of the European
Ariane 5 launcher crashed about 40 seconds after takeoff.
Media reports indicated that the amount lost was half a
billion dollars -- uninsured.
•
The exception was due to a floating-point error: a
conversion from a 64-bit integer to a 16-bit signed
integer, which should only have been applied to a
number less than 2^15, was erroneously applied to a
greater number, representing the "horizontal bias" of the
flight.
•
There was no explicit exception handler to catch the
exception, so it followed the usual fate of uncaught
exceptions and crashed the entire software, hence the onboard computers, hence the mission.
What does this have to do with this
class?
• Logic : means to prove correctness of
software
• Sometimes can be semi-automated
• Can also verify a provided correctness proof
But what about another more
“normal” example?
How is this related to discrete?
• What is the probability of my single ticket
winning the jackpot?
• If 500 million tickets are sold for
Wednesday’s drawing, what is the
probability that no one wins? What is the
probability that two or more people split the
jackpot?
How is this related to discrete?
• My uncle bought five tickets for Saturday’s
drawing. NO number was duplicated
between the five tickets.
• None of his numbers were in the
combination drawn. Is that unusual?
Who knows the game
Ticket to Ride?
Ticket To Ride
• You have 45 tokens.
• During game play you can
elect to connect two cities on
the map.
• I wanted to know which set
of segments generated the
highest score.
• I was going to “brute force” it
but decided to see how much
force it would take…