-*- text -*-
Presentation
============
Nicolas M. Thiéry
Office: SH222, Tel: 3462, Email:
Web page: http://www.mines.edu/~nthiery/
Web page for the class: http://www.mines.edu/Academic/courses/math_cs/macs358/
Reserve in the library: MACS 358
Ask questions, make comments!
- during the course
- after the course
- by email: nthiery@mines.edu
- with appointment
Send me an email:
Name, Major, year, email, web page,
How many other courses
Courses in Computer Science/Math before/now
Experience in programming
What do you expect to learn in this course
Additional comments
Picture
==============================================================================
Practical stuff
===============
Office hours, Syllabus, Course notes, ... see the web page
Homeworks:
----------
- very important
- 30% of the final grade
- One homework every week:
list of exercises given on monday (or earlier) on the web page
due the next monday
corrections in the reserve in the library
difficult exercises corrected in class
- One week: collected and graded
Other week: one exercise of the list as in-class quizz on wednesday
- You can ask for clues during the week
- You can work in group
Computer projects:
------------------
- Extra credit
Exams:
------
- Test1, Test2, Final:
- 20% + 20% + 30% of the final grade
Textbook:
---------
- Mathematical structures for Computer Science 4th edition
Judith L. Gersting
- Followed step by step
- Read in advance
Further reading:
----------------
- How to solve it (Polyá, G.)
- The art of Computer Programming (Knuth, D. E.)
- Gödel Escher Bach, an Eternal Golden Braid (Hofstadter, D. R.)
==============================================================================
Objectives
==========
- Mathematical tools for solving problems (possibly with a computer) ?
- Problems to solve
- Problems to prove
Problem: Finding the exit of a labyrinth
Phase 1: Understanding the problem
Phase 2: Devising a plan
Phase 3: Carrying out the plan
Phase 4: Looking back
Phase 1: Understanding the problem
- What is the data ?
- What is the goal ?
- Introduce notations
- How would you store this in a computer ? (Data structure)
- Do you need all data ? Can you simplify the data ?
Look at an example !
Phase 2: Devising a plan
- Can you try to solve a simpler problem ?
- Look at examples !
Phase 3: Carrying out the plan
Phase 4: Looking back
- Can you make it an algorithm ?
- Is your algorithm correct ?
- Can you prove it is correct ? (Proof of correctness)
labyrinth with a cycle
Hmm, it's incorrect. In which case is it correct ?
- Can you use your solution (algorithm) to solve another problem ?
(Generalization)
- What is the structure behind ? (Abstraction)
- How many labyrinths can you build ?
- How many walls are there in a labyrinth ?
Tools:
Abstraction
Generalization
Structures
Proofs and programs
Solving a problem can take time !
==============================================================================
Sloane ?
1 1 2 5 14 Catalan numbers
Labyrinth ...
==============================================================================
Contents
========
- I) Formal Logic
- Programming (Prolog)
- Electronic
- II) Proofs
- of algorithms, of programs (example of Ariane 4)
- What is a proof
- Tools for proving theorems
- III) Combinatorics
- Counting objects
- V) Graphs, Trees, Finite state Automats
==============================================================================
Homework for monday:
- read and try MIU systems
Goal:
- Keep you challenged
class difficult
grading is accordingly
- Math and cs are fun