-*- text -*-

Presentation
============

Nicolas M. Thiéry

Office: SH222, Tel:	3462, Email: <nthiery@mines.edu>
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