Formal Methods II
CSE3305
State
Water has states of Solid, Liquid, Gas. It can be obvious what things have state in the physical world.
We're talking about Finite state automators set in space. The automator changes state. It's the machine that is moving through space.
A graph has edges and verticies.
Whenever you have a collection of things we call it a 'set'.
State Space
We will be interested in time/space complexity mostly.
We talk about THE PROGRAM rather than THE PROGRAM ON THIS COMPUTER. We want to analyse the program.
'It take 300 instructions for this program to run.' This cannot be used to measure the complexity because the INPUT changes.
We measure complexity with O notation because
a) it counts for the insignificant size of +n and +x when N is large. and it
b) counts for the variances in language. Chances are that something that takes 20 instructions in one lang are going to take something in the order of 20 instructions in any other language.
So we use this O notation to measure the complexity of algorithms (programs). We also use it for space soo. So we use it for measuring space / time complexity.
Contraints
Limits on the solution
Hard contraints cannot be broken. If you do, the solution in wrong. Soft contraints can be broken and still be correct.
Optimal. The best!
feasable. Is it possible to do it within these contraints? What can we physically manage? Constraints as in time / money. Like 100 bit encyption can be broken with a very simple algorithm which exists. It just takes a couple of thousand years. It's not IMPOSSIBLE but INFEASABLE.
Search Problem
We're searching for an solution in the search problem. We're going through all the possible solutions and finding the right solution. Eveything could be a search problem. Trying to find which photos to print is a search problem.
Heuristic
An innnacurate way of choosing what to do next. "I think it's most likely to be here so I'll look here first."
Websearch does it for you, pulling out what it thinks you need from all those millions of pages (with ranking). Pundits do it on the horses.
Natural numbers include zero. Positive numbers do not.
Water has states of Solid, Liquid, Gas. It can be obvious what things have state in the physical world.
We're talking about Finite state automators set in space. The automator changes state. It's the machine that is moving through space.
A graph has edges and verticies.
Whenever you have a collection of things we call it a 'set'.
State Space
We will be interested in time/space complexity mostly.
We talk about THE PROGRAM rather than THE PROGRAM ON THIS COMPUTER. We want to analyse the program.
'It take 300 instructions for this program to run.' This cannot be used to measure the complexity because the INPUT changes.
We measure complexity with O notation because
a) it counts for the insignificant size of +n and +x when N is large. and it
b) counts for the variances in language. Chances are that something that takes 20 instructions in one lang are going to take something in the order of 20 instructions in any other language.
So we use this O notation to measure the complexity of algorithms (programs). We also use it for space soo. So we use it for measuring space / time complexity.
Contraints
Limits on the solution
Hard contraints cannot be broken. If you do, the solution in wrong. Soft contraints can be broken and still be correct.
Optimal. The best!
feasable. Is it possible to do it within these contraints? What can we physically manage? Constraints as in time / money. Like 100 bit encyption can be broken with a very simple algorithm which exists. It just takes a couple of thousand years. It's not IMPOSSIBLE but INFEASABLE.
Search Problem
We're searching for an solution in the search problem. We're going through all the possible solutions and finding the right solution. Eveything could be a search problem. Trying to find which photos to print is a search problem.
Heuristic
An innnacurate way of choosing what to do next. "I think it's most likely to be here so I'll look here first."
Websearch does it for you, pulling out what it thinks you need from all those millions of pages (with ranking). Pundits do it on the horses.
Natural numbers include zero. Positive numbers do not.
Archives
Links
- JPS2150 Identity and Tradition
- CSE3308 Analysis and Design
- CSE3305 Formal Methods II
- CSE3395 Perl Programming
- CSE3391 Unix Tools
- Monash University
- my.monash
- Mathieutozer.com
- Courseware Page
0 Responses to “Tute Sheet 1”
Leave a Reply