Complete lattices and closure systems

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 […]

, ,

Leave a comment

Predicates as sets

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 […]

Leave a comment

Boolean lattices

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 […]

Leave a comment

The heap sort algorithm

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 […]

,

Leave a comment

Lattices — Partial order with supremum and infimum

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 […]

Leave a comment

The insertion sort algorithm

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 […]

Leave a comment

The implementation side of framing

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 ~ […]

Leave a comment