Algorithmen - Rekursion und Quicksort

Kategorie: Technik  ·  Kommentare: 8

Vor kurzem habe ich zwei grundlegende Algorithmen beschrieben, die benutzt werden können, um eine Menge von Daten zu sortieren. Betrachtet wurden Bubblesort und Selectionsort, wobei für beide Algorithmen festgestellt wurde, dass sie relativ ineffizient sind, was ihr Sortierverhalten angeht. Für den Einsatz in Programmen, wo Geschwindigkeit wichtig ist und große Datenmengen sortiert werden müssen, können sie daher nicht wirklich eingesetzt werden. Man benötigt demzufolge Algorithmen, die etwas effizienter arbeiten als die beiden bereits vorgestellten. Der bekannteste und am häufigsten verwendete Algorithmus ist hier zweifelsohne der von Tony Hoare entwickelte Quicksort-Algorithmus, und um den soll es jetzt gehen.

...mehr

Autor: Marcus Frenkel· 24.10.11 · 15:42 Uhr· 8 Kommentare

Berührungsempfindliche Eingabe auf beliebigen Oberflächen mit Kinect

Kategorie: Technik  ·  Kommentare: 19

Der letzte Artikel mit spannenden Neuigkeiten liegt schon etwas zurück - damals ging es um die vielfältigen Nutzungsmöglichkeiten von Microsofts Eingabemedium Kinect,bei dem die Eingabe lediglich über eine Kamera und einen Tiefensensor stattfindet. Chris Harrison von Microsoft Research hat den bisherigen (teilweise beeindruckenden) Anwendungsszenarien ein weiteres hinzugefügt: arbiträre Touch-Oberflächen. Bisherige Systeme mit Touchbedienung bedienen sich häufig einer speziellen Oberfläche mit gleich wie gearteten Sensoren. In der Forschungsarbeit von Microsoft wurde ein System entwickelt, welches eine Touch-Oberfläche lediglich mit Hilfe des Tiefensensors von Kinect umsetzt; die Folge davon ist, dass die anzuzeigenden Inhalte nicht mehr auf einem speziellen Bildschirm angezeigt werden müssen, sondern auf jede beliebige Oberfläche projiziert werden können.

...mehr

Autor: Marcus Frenkel· 18.10.11 · 16:00 Uhr· 19 Kommentare

Turingmaschinen und Turing-Vollständigkeit

Kategorie: Technik  ·  Kommentare: 20

Bisher habe ich Themen aus den Gebieten der Grundlagen-Informatik, der technischen Informatik, der (hardwarenahen) Programmierung und der Algorithmen besprochen; nicht erwähnt wurde aber (unter anderem) die theoretische Informatik; diesen Missstand möchte ich heute beseitigen und das Wunschthema von Leser Michael beantworten: er hat eine kurze Abhandlung über die Turing-Vollständigkeit erbeten. Nun denn, auf geht's.

...mehr

Autor: Marcus Frenkel· 12.10.11 · 16:50 Uhr· 20 Kommentare

Algorithmen - Bubblesort und Selectionsort

Kategorie: Technik  ·  Kommentare: 22

In den letzten Artikeln habe ich versucht, das grundlegende Vorgehen beim Programmieren darzulegen - einerseits natürlich, um die Idee des Programmierens selbst zu erläutern, andererseits aber natürlich auch, um die Grundlagen für die Erklärung der eigentlichen Aufgabe der Informatik zu schaffen: der Problemlösung. Der durchschnittliche Informatiker hat im Arbeitsalltag nämlich in der Regel relativ wenig mit Computern an sich zu tun (abgesehen davon, dass er an ihnen programmiert); viel öfter ist er damit beschäftigt, für ein gegebenes Problem nach einer Lösung zu suchen. Ein Problem kann hier alles mögliche sein; von der Lösung einer einfachen Gleichung über die Suche nach dem kürzesten Pfad auf einer Landkarte bis hin zu komplexen Simulationen ist alles denkbar. Die Lösung ist natürlich immer vom Problem abhängig, wobei typischerweise für ein Problem viele verschiedene Lösungen mit jeweils ganz eigenen Vor- und Nachteilen existieren. Ein häufig anzutreffendes, bereits vielfach gelöstes und daher teilweise trivialisiertes Problem ist die Sortierung einer Menge von Daten. Was ein Mensch relativ intuitiv machen kann, ist für den Computer harte Arbeit (der Mensch wird dem Computer beim Sortieren trotzdem immer unterlegen bleiben) und wird von den sogenannten Sortieralgorithmen erledigt. Und um zwei deren einfachste Vertreter soll es heute gehen (übrigens werden Sortieralgorithmen üblicherweise auf der Grundlage von Feldern natürlicher oder ganzer Zahlen erklärt und an diese Konvention möchte ich mich hier auch halten).

...mehr

Autor: Marcus Frenkel· 06.10.11 · 22:22 Uhr· 22 Kommentare

Gastbeitrag: vierter Programmierwettbewerb des freien Magazins und Catalysts Coding Contest '11

Kategorie: Kultur·Naturwissenschaften  ·  Kommentare: 24

Und wieder ein Gastbeitrag von Sebastian Wagner, der sich fleißig darum bemüht, verschiedene Informatik-Wettbewerbe etwas bekannter zu machen - meinen Dank dafür.

...mehr

Autor: Marcus Frenkel· 03.10.11 · 20:58 Uhr· 24 Kommentare

Humor mit binären Zahlen - der Witz zum Sonntag

Kategorie: Kultur  ·  Kommentare: 7

Für humortechnisch auf der entsprechenden Wellenlänge liegende Menschen bietet das binäre Zahlensystem etliche Möglichkeiten für schöne Witze (die ihren Humor insbesondere dadurch gewinnen, dass nicht mit dem Zahlensystem Vertraute sie praktisch nicht verstehen können). Die Website xkcd.com ist immer wieder ein schöner Quell für derartigen Humor, so auch mit diesem Bild:

Besonders schön ist auch die Bildunterschrift:

If you get an 11/100 on a CS test, but you claim it should be counted as a 'C', they'll probably decide you deserve the upgrade."

Ich kann jedem mit entsprechendem Humor empfehlen, die xkcd-Comis im RSS-Feed zu haben (so noch nicht geschehen). Es lohnt sich.

Autor: Marcus Frenkel· 02.10.11 · 11:10 Uhr· 7 Kommentare

Musizierende Diskettenlaufwerke oder: Wenn Informatiker sich langweilen...

Kategorie: Technik  ·  Kommentare: 9

Wenn Informatiker sich langweilen und Kanäle für ihre überschüssige Kreativität suchen, kommen die absurdesten (mit durchaus positiver Note) Sachen heraus. Ein Klassiker sind wohl die musizierenden elektrischen Geräte; im Internet finden sich Videos zuhauf, in denen alltägliche Geräte zweckentfremdet und für die musikalische Unterhaltung genutzt werden. Ein schönes Beispiel hierfür sind die musizierenden Diskettenlaufwerke; das folgende Video ist der jüngste Spross dieser Kategorie:

Für die Leute mit entsprechendem Humor (ich gebe es hier gerne zu: ich finde es toll!) ist das allein sicherlich schon Unterhaltung genug, aber immerhin ist das hier ein Portal für Wissenschaftsblogs, also wollen wir dem auch gerecht werden und einmal hinter den Kulissen schauen, wie man denn nun Diskettenlaufwerke dazu bringt, etwa den imperialen Marsch aus Star Wars zu spielen (der Autor des Videos hat seine Beschreibung auch unter dem Video auf Youtube verlinkt).

...mehr

Autor: Marcus Frenkel· 01.10.11 · 21:50 Uhr· 9 Kommentare