Transcript What is Discrete Math?

What is
Discrete Math?
Fall 2008
Day 1
Discrete Means…
• Discrete:
– consisting of distinct or unconnected elements
– taking on or having a finite or countably infinite
number of values
• Not Continuous:
– Real numbers are no longer the base
– Integers are the primary tool
Why Discrete?
• DM provides models and tools for
real world phenomena that change
abruptly or have distinct states
• DM has become increasingly
important in the digital/computer
age
DM intersects other areas
•
•
•
•
•
•
•
•
•
•
•
•
Computer Science
Electrical Engineering
Operations Research
Probability
Statistics
Number Theory
Cryptology
Group Theory
Graph Theory
Coding Theory
Set Theory
Logic, and more
Applications
•
•
•
•
•
•
•
•
•
•
•
•
algorithms
network flows
telephone routing
delivery routes
computer networks
airplane schedules
personnel assignments
genetics
election procedures
secure and reliable wireless communications
design of statistical experiments
bin packing, and more…
More on Applications
• Software engineering – uses sets, graphs, trees,
and other structures
• Analysis of algorithms – requires ability to count
number of operations, proofs of correctness
• Recursive algorithms – require solution to
recurrence relations, proofs of correctness through
induction
• Cryptology – requires number theory
• AI – requires logic
• Theory of computation and compiler design –
requires proofs including proofs by induction
What’s in store this
semester?
• Learn how to count!
– You may be surprised that counting
certain things can be really, really hard!
– But you may also be surprised at how
good you’ll get at counting!
Count things like..
• Number of ways to buy a dozen donuts
from a choice of 32 different varieties
• Number of ways to triangulate an n-gon
• Number of ways to configure a network so
that certain connectivity requirements are
met
• Number of ways to assign students to
groups, considering certain constraints on
student preferences
The Pigeon-hole Principle
• Learn how to use pigeons to “unlock
the common sense in your head”
Find out how many colors it takes to
color any map such that no “neighbor
states” have the same color
Learn about the Königsberg
Bridge Problem
c
Euler - 1736
River Pregel
d
a
b
• Is it possible?
– Start at locations a, b, c, or d
– Cross each bridge exactly once
– Return to the starting location
Study how the NASA
Mariner Mission sent
pictures back to Earth
Unlock the secrets of ISBN
and UPC
Discover why this is perhaps
the coolest figure in
mathematics
What Else Can You Expect?
• Work lots of hard but fun problems
• Learn to argue clearly, convincingly, and
flawlessly
• Improve technical writing and presentation skills
• Investigate topics in small groups
• Participate actively in class
• Get help early and often
• Work closely with classmates and professor
Number 1 Piece of Advice
from Previous Students
Do Practice
Problems
RSA Cryptosystem
• Learn how the famous RSA algorithm
actually works
Learn how to prove
things like:
•
Every amount of postage of 12 cents or
more can be formed using just 4-cent
and 5-cent stamps.
•
For all positive integers n, a 2n x 2n
chessboard with one square removed
can be tiled using L-shaped pieces,
where these pieces cover 3 squares at a
time, as shown