Maths - Induction (part 2)

A better Example

Let’s take a look at another example, this time lets use:

Maths - Induction (part 1)

[ A = for all.    E = there exists ]

The Principles of Induction

Firstly, welcome to Induction. The one thing in Discrete Maths that I hear a heck of a lot of people complaining about! – So don’t worry, you’re not the only one :)

Maths - Functions (Part 2)

Composition of Functions

Say we have 2 functions:

• f: R ------> S₁


• g: S₂ -----> T

Maths - Functions (part 1)

In Discrete Maths, 'Functions' have 3 features:

1. Source (S) , or more commonly known as the Domain
2. Target (T), or more commonly known as the CoDomain
3. Behaviour, which is what the function does as it transforms the source (input) into the target (output)

Distributed Systems - Bully Algorithm

Let’s assume that we have 7 nodes:



At this current moment in time, node ‘7’ is the coordinator, because it is the highest numbered node. But then node ‘7’ leaves, so who is now the coordinator? Lets say node ‘4’ decides it wants to be the coordinator, then we have:

Distributed Systems - Logical Clocks and Processes

Fat Clients

A fat client is a client in a client-server architecture network which typically provides rich functionality independently of the central server. Originally known as just ‘client’ or ‘thick client’, the name is contrasted to thin client, which describes a computer heavily dependant on a servers applications.

Distributed Systems - Massive Distribution for Performance

Definition of a Distributed System

A distributed System is one in which independent, self-sufficient – often autonomous or heterogeneous – spatially-separated components must use a common interconnect to exchange information and coordinate actions, and allow the whole to appear to the user as one single coherent system.

Distributed Systems - Socket Level Servers

Definition of a Distributed System

A distributed System is one in which independent, self-sufficient – often autonomous or heterogeneous – spatially-separated components must use a common interconnect to exchange information and coordinate actions, and allow the whole to appear to the user as one single coherent system.

Distributed Systems - Axioms of Distributed Computing

Definition of a Distributed System

A distributed system is one in which independent, self-sufficient, often autonomous and heterogeneous, spatially separated components must use a common interconnect to exchange information in order to coordinate there actions and allow the whole to appear to its users as one single coherent system.

Distributed Systems - Interconnects

Definition of a Distributed System

A distributed System is one in which independent, self-sufficient – often autonomous or heterogeneous – spatially-separated components must use a common interconnect to exchange information and coordinate actions, and allow the whole to appear to the user as one single coherent system.

Distributed Systems - Architectural Paradigms

Definition of a Distributed System

The definition of a distributed system is one which has independent and self-sufficient – often heterogeneous or autonomous – spatially-separated components which must us a common interconnect to exchange information in order to coordinate information, and to make the whole system appear to its user as a single coherent system.

To further this more a distributed system is the result of collaboration between separate, independent processes. In order for separate, independent processes to collaborate, then they must interact.

Distributed Systems - Sync and Blocking Primitives

Definition of a Distributed System

A distributed system is one in which independent, self-sufficient, often autonomous and heterogeneous, spatially separated components must use a common interconnect to exchange information in order to coordinate there actions and allow the whole to appear to its users as one single coherent system.

Distributed Systems - Defining A Distributed System

Definition of a Distributed System

A distributed system is one in which independent, self-sufficient, often heterogeneousand autonomous,spatially separated components must use a common interconnect to exchange information in order to coordinate their actions and allow the whole to appear to its users as a single coherent system.

Artifical Intelligence - Dutch Books

Dutch Books

In the previous post we talked about probability theory, and talked about agents having a probability distribution to represent their degrees of belief.  We also talked about the axioms K1 and K2, that is:

K1 – If a is always true, then p(a) = 1.
K2 – If a AND b are never true at the same time, then the probability of a OR b being true is p(a) + p(b).

These axioms become more important when we talk about the idea of a 'dutch book'.

Artificial Intelligence - Robot Localisation

Artificial Intelligence

Artificial Intelligence is the field of computer science that concerns itself with getting better and more positive responses to the question 'Can machines think?'.  Over the years there have been a number of approaches to artificial intelligence, the current best method that is growing in popularity is the use of probability theory in AI, and this probabilistic reasoning is spreading to almost all areas of Artificial Intelligence.

Maths - Relations

Relations

If we have two sets, A and B, we can refer to the 'Cartesian Product' as being A x B.  This means that if A = {1, 2, 3} and B = {a, b, c}, then A x B = {1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c}.  It's the set of all pairs of values where the first is from A and the second  is from B.

A relation from A to B is a subset of A x B.  A relation can be said to connect values together, in a way, showing a relationship between them.

Computation - Patterns

Patterns

In the last blog post we looked at what the various components in the module, mostly languages, symbols, and alphabets.  Now we're going to look in more detail at how to define a language from symbols.

To define languages more easily we're going to look at patterns.  Patterns can also be called regular expressions.  Computers, after all, can't recognise set notation symbols such as {, }, or ∈.

Computation - Sets & Languages

Sets & Languages

In order for a computer to organise a textual input, the computer has to be able to recognise certain strings, such as, in parsing a programming language, it has to be able to find 'if' or 'while'.

The first part of Computation deals with how we describe to a computer what string to look for, how to come up with the right description to solve the problem, and how to do more advanced things such as check whether a piece of code is correctly formed, making sure that opening and closing brackets match, or checking that a webpage is written in valid HTML.

Computation - CFG to DFA

CFGs to DFAs

Hopefully you should remember what a CFG consists of. That is:

• A set of terminal symbols. That is, some given alphabet.


• A set of non-terminal symbols.


• A start state – S.

Computation - Growth Rates and Orders

Growth Rate of Functions

OK, so this post is mainly because some people ‘begged’ me to put it on. From the examples you may have – hopefully? – seen in a previous post – if you haven’t here it is: http://computersciencesource.wordpress.com/2009/09/09/comp10042-computation-time-space-complexity/ .

Computation - Halting Problem

Termination

Let’s take another look at the piece of simple Java code that we looked at earlier:

Computation - Time & Space Complexity

Time is a precious thing

Imagine, if you will, a children’s puzzle game – the Tower of Hanoi. With this, you have to move – say 8 disks – from one post to another. Each disk has to be moved – one at a time – onto another post, provided that the disk – if it exists – that it lands on is not smaller. Continuing on with the 8 disks, to solve such as simple puzzle will take a child 2ⁿ-1moves. So for 8 disks, this will be 255 moves – that’s quite a lot.

Computation - Context-Free Grammars

Well-defined Rules

Instead of thinking of patterns that may be matched by some strings, it is our aim here to generate all the words of some language following so well-defined rules. The way of reading the rules is to see them as way of rewriting the string generated so far. For example, by using the given rules, to change one of the symbols in the current string, into a string of others. Such as, changing ‘S’ in this string to ‘at’:

Computation - Patterns to Automaton

What If?

So, now we’ve seen a way to transform an automaton into a pattern. BUT! How do we go about doing it the other way around? How do we transform a pattern into its counterpart automaton?

Computation - Automaton to Patterns

A brief Summary

So far we have seen 3 ways in which to talk about a language over given alphabet. These are:

1. Set-theory


2. Regular Expressions (patterns)


3. NFAs and DFAs (automatons)

Computation – An NFA to a DFA

Non-Deterministic Finite Automata (NFA)

So now you’ve seen a slight introduction into DFAs, its time to introduce their counterpart – NFAs! Now as seen from above, a DFA can sometimes be relatively simple to draw, however, sometimes it can be even easier to draw an NFA.

Computation - Finite State Automaton (part 2)

Finite State Automata

OK, so that last part was only introducing you to the idea of using automata for expressing patterns in a better, and more meaningful way. However, it is now time to take this to a new and more formal level.

Before we can even think about drawing an automaton, we must know one thing! That is of course the alphabet, Σ. As without an alphabet, an automaton would be pretty darned meaningless!

Computation - Intro to Automaton (part 1)

Using Pictures for Patterns

Imagine if someone told you to check a queue of an unknown length to see if it contained an even number of zombies. How would you do it?

Computation - Regular Expressions

Computers and Sets don’t go

Up till now we’ve only seen how to express languages as sets, such as:

• {(01)n | n Є N}

While we can all understand this, if you go ahead right now and type it into a computer then you’ll just get a lot of evil error messages thrown at you - no, not becuase you're using Windows, but because we have to express the language in a very different way. This way of expressing is known a patterns!

Computation - Sets and Languages

OK, so first things first, we need to settle on some terminology here. This is because things such as symbols can also be cause characters, so I need to mention which terminology will be used here.