### Complete lattices and closure systems

Posted by helmutbrandl in Uncategorized on September 16, 2012

Introduction Complete lattices are important because of their connection to closure systems. Closure systems arise in many cases. Some examples: 1. Graphs: If we have a graph we often use the phrase “All the nodes reachable from a specific node”. A set of nodes of a graph which contains all reachable nodes is a closed […]

### Predicates as sets

Posted by helmutbrandl in Uncategorized on August 19, 2012

Mathematical sets Sets abound in mathematics. If a mathematician wants to treat a collection of objects which satisfy a certain property as an entity, he defines a set. Sets are a very powerful tool in specifications. In order to obtain good readability we introduce a set like notation. Set expressions The expression {1,2,3} is the […]

### Boolean lattices

Posted by helmutbrandl in Uncategorized on August 19, 2012

Introduction This article is dedicated to boolean lattices. A boolean lattice is another name for a boolean algebra. A boolean lattice is an algebraic structure with two binary operators “*” and “+” which represent “and” and “or”, a unary operator “-” which represents negation. The binary operators are commutative, associative and distributive. Furthermore there are […]

### The heap sort algorithm

Posted by helmutbrandl in Uncategorized on July 23, 2012

Introduction The heapsort algorithm is a sorting algorithm which has time complexity O(n log n) and does not need additional space. Merge sort has the same time complexity but usually needs additional space. As opposed to merge sort, the heap sort algorithm is not stable i.e. it might reverse the order of equal elements. The […]

### Lattices — Partial order with supremum and infimum

Posted by helmutbrandl in Uncategorized on July 16, 2012

Introduction Types which satisfy the concept of a partial order (i.e. which are descendants of the type PARTIAL_ORDER) have a binary relation “<=” which is reflexive, transitive and antisymmetric, i.e. for every three objects “a”, “b”, and “c” the following conditions are satisfied: reflexive: a<=a transitive: a<=b => b=>c => a=>c antisymmetric: a<=b => b=>a […]

### The insertion sort algorithm

Posted by helmutbrandl in Uncategorized on July 1, 2012

Introduction Insertion sort is one of the simplest sorting algorithms. It is quite efficient for small arrays. Its runtime increases with the square of the number of elements to be sorted. Therefore it should not be used with large data sets. For large data sets algorithms like merge sort or heap sort are far more […]

### The implementation side of framing

Posted by helmutbrandl in Uncategorized on June 17, 2012

The specification In the previous article the specification of a buffer of elements of a certain type has been described. Let us repeat here shortly the essence of the specification. class BUFFER[G] feature capacity: NATURAL content: ghost LIST[G] count: NATURAL ensure Result = content.count end [] (i:NATURAL): G require i < count ensure Result ~ […]