Travelling Salesman Problem

An der Schule belege ich das Wahlkursfach Informatik. Kürzlich wählte/bekam ich den Auftrag einen Vortrag über einen Algorithmus für das “Travelling Salesman Problem” oder auf Deutsch “Problem des Handlungsreisenden” vorzustellen. Doch ich konnte nicht einfach einen “normalen” Brute-Force Algorithmus wählen sondern musste das Problem mit Hilfe Dynamischer Programmierung lösen, was die Aufgabe um einiges erschwerte. Denn als bald ich mich dann hinter das Problem machte, musste ich feststellen, dass ich das Dynamische Programmieren immer noch nicht wirklich beherrschte und auch kein fertiger Algorithmus ausser in Pseudocode im Internet zu finden ist.

Kompletten Beitrag lesen

Maturarbeit III

So lange ist es her seit dem letzten Eintrag! 🙂
simxMeine Maturarbeit hat auch sehr an Umfang zu genommen, zumindest was den Code betrifft!

Kompletten Beitrag lesen

Kommentar [1]
Geschrieben am 20.02.2010 von admin in Computer, Reallife, School, Windows
 Tags: , , , , , , ,

Videos zum Zweiten

Da wir uns nun auch in der Schule mit Stopmotion, Real und andere Arten von Film beschäftigen, bin ich auf eine weitere Suche gegangen um gute Programme zu finden.
MonkeyJam hab ich ja bereits in einem früheren Post erwähnt. Leider musste ich nun nach mehreren Versuchen feststellen, dass sich MonkeyJam wohl für direkt Fotografie und Layers eigenen mag, jedoch um aus einer Bilderserie einfach und schnell ein Video zu erstellen nicht ausreicht. Das ewige Klicken um schliesslich bei meinen gewünschten Bildern anzukommen, um dann diese nicht per Ctrl+A (weil es das nicht unterstützt) sondern mit Erstes-auswählen-Shift+Letztes-auswählen markieren und importieren und schlussendlich wieder Datei->Exportieren und den richtigen Codec auswählend den Film erstellen, ging mir so ziemlich auf die Nerven und hat mich auch Zeit gekostet.
Enttäuscht musste ich dann wieder feststellen, wie Geldsüchtig das Internet heute ist. Man kann alle Programme haben, aber alle würden Geld kosten, bis ich dann irgendwie auf der Seite von jarrin gelandet bin. Vergeblich sucht man dort nach einem Kaufpreis, denn es steht alles unter der GNU General Public License. Nun gut es gibt ja auch das eine Freeware Programm JPGVideo, welches aber bei mir überhaupt nicht funktioniert hat. Kritisch testete ich das Programm mit Namen JPG to AVI und musste mit erstaunen feststellen, dass dieses kleine simple Programm genau den Ansprüchen gerecht kam, welche ich stellte. Das Einzige was einzelne stören könnte ist das dotNET-Framework, welches benötigt wird, aber da das bei mir sowieso schon drauf ist spielt dies für mich keine Rolle.
Fazit: Lieber klein dafür fein! 😉

Da unsere ebenfalls schon erwähnte Canon PowerShot SX1 IS keine 720p Realfilm Aufnahmen machen kann und mein Notebook keine 1080p Filme abspielen kann muss ich diese konvertieren. Zwar kann mein Videoschnitt- / Bearbeitungsprogramm die Filme laden und verarbeiten, jedoch wäre es im vorneherein noch praktisch zu wissen, welche Szene ich nun gerade rein geladen habe.
Auch hier gibt es eine Unzahl an kommerziellen Programmen, jedoch sind die gratis Programme auch nicht gerade in kleiner Zahl vorhanden, so dass man die Qual der Wahl hat. Da die Kamera ein 1080p Film im MOV-Format erstellt und dies wahrscheinlich nicht von allen Programmen unterstützt wird, habe ich spezifisch gegoogelt und bin dann auf das Programm RAD Video Tools gestossen, welches ursprünglich für Konvertierungen für verschiedene Computerspiele gedacht war, jedoch auch Konvertierungen in normale Videoformate wie AVI durchführen kann. Nachdem ich ein paar der FAQs und ein kleines Tutorial durchgelesen hatte, konvertiere die erste Szene und war über die Geschwindigkeit und die gute Qualität sehr positiv überrascht. An verschiedenen Stellen gibt es zwar ein Problem mit der Darstellung jedoch kann dies genauso gut Codec spezifisch sein. Ich habe die Filme komprimiert da ich die Filme ja eigentlich nur als Vorschau benötige und nicht als Quellmaterial. Als Encoder hab ich dann wieder den FFdShow verwendet, diesmal jedoch mit anderen Einstellungen: “one pass – quantizer 4”.
Fazit: Das RAD Video Tools überzeugt vor allem durch seine einfach gehaltene Benutzeroberfläche und seinen grossen optionalen Einstellungsmöglichkeiten.

Fazit

Nebst dem grossen Müll welchen man im Internet findet, gibt es doch immer wieder kleine versteckte Programme, welche genau den gestellten Ansprüchen entspricht, man muss nur genug lange danach Suchen, was sehr Nerv tötend sein kann, jedoch sehr lohnend ist!

RAD Video Tools
JPG to AVI

Comics

So da wir in der Schule ein Comicstrip zeichnen mussten, dachte ich stell ich den einmal hier rein, obwohl es nicht sonderlich hübsch ist. 🙂comicstrip

Kompletten Beitrag lesen

Kommentare [2]
Geschrieben am 26.11.2009 von admin in Reallife, School
 Tags: , , , ,

Mathematik – Extremal Probleme & Integrieren

So wieder einmal einen kleinen Beitrag zum Thema Mathematik.

Extremal Probleme

Da es nicht einen grossen Nutze hat, wenn man einzelne Aufgabe hier vor löst, werde ich einen “Algorithmus” erstellen, mit welchem wohl die meisten Probleme gelöst werden können.

  • Problemerkennung: Die für viele wohl am Schwierigste Aufgabe ist das Erkennen des Problems bzw. das Suchen nach dem Ziel. Dies ist meist sehr logisch und kann daher nur durch viel üben angeeignet werden. Als Tipp kann ich höchstens sagen: Lest die Aufgabe mehrmals gut durch, erstellt eine Skizze und schreibt euch die gegebenen Dinge auf.
  • Suchen der Zielfunktion: Da man nun weiss was gesucht ist, muss man dies Mathematisch ausdrücken können. Dafür überlegt man sich was genau im Extremum stehen soll. Meist ist es eine Fläche, eine Strecke, einen Umfang o.ä. Die Formeln zu Flächen und Umfänge kann man gut in der Formelsammlung nachschlagen.
  • Suchen der Nebenbedingung(en): Das wohl zweit schwerste oder z.T. auch schwerste ist das Suchen nach den Nebenbedingungen. Der Nutzen von Nebenbedingungen ist, dass man für das Lösen der Zielfunktion nur eine Unbekannt haben darf. Man muss nun also Nebenbedingungen eliminieren. Dafür gibt es unzählige Methoden, welche hier natürlich nicht aufgeführt werden. Was jedoch meistens anwendbar ist, ist das Umformen, so dass die anderen Unbekannten nur noch von der einen Unbekannten abhängig ist. (z.B. Wenn man x und y als Unbekannte hat und die Funktion y=x^2, dann kann man x^2 anstatt von y verwenden.)
  • Lösen: Nachdem man nun die Zielfunktion und die Nebenbedingungen hat, kann man die Nebenbedingungen in die Zielfunktion einsetzten und man erhält eine Funktion mit einer Unbekannten. Da man ja ein Extremum (Maximum/Minimum) möchte, leitet man die erhaltene Funktion ab und setzten diese gleich Null. Warum? Da an den Nullstellen der Ableitung einer Funktion normalerweise ein Extremum existiert. (Siehe Formelsammlung)
  • Überprüfung: Wie oben geschrieben gibt es “meist” ein Extremum, um dies zu überprüfen, muss/kann man nun noch die zweite Ableitung der Funktion erstellen und die durch die erste Ableitung erhaltenen Nullstelllen einsetzten. Wenn das Resultat Negativ ist, hat man ein Maximum (Höhepunkt). Wenn das Resultat Positiv ist, hat man ein Minimum (Tiefpunkt). Wenn das Resultat gleich Null ist, hat man kein Extrempunkt.
  • Erfüllung der Aufgabenstellung: Nun muss man nochmals die Aufgabenstellung betrachten und auch wirklich die Dinge berechnen, welche dann gefragt sind!

Integrieren

Analog zu Extremal Problemen erstell ich hier einen “Algorithmus”.

  • Problemerkennung: Das Problem beim Integrieren ist wohl meist das finden einer bestimmten Fläche unter einer Parabel o.ä. Auch hier ist eine Skizze meist sehr hilfreich, was jedoch bei Parabeln gerade auch sehr trickreich sein kann. Wenn man eine gegebene Funktion hat, kann man diese auch auf dem Taschenrechner zeichnen lassen damit man eine ungefähre Vorstellung hat. Auch hier kann ich keine konkreten Lösungswege geben.
  • Informationen zum Lösen suchen: Da jede Aufgabe sehr differenziert sein kann, werd ich ein wenig allgemeiner. Um eine Fläche zu berechnen benötigt man die folgenden Informationen: Obere und untere Grenze, die Funktion und ihre Stammfunktion (“Aufleitung”) und jeweils nur eine unbekannte. Wenn es nun mehrere Unbekannten gibt, muss man entweder mehrere Gleichungen finden, oder die Unbekannten eliminieren.
  • Lösen: Nun haben wir alles zusammen und können die Fläche berechnen. Um nicht nur den CAS Funktionen zu verwenden, müssen wir die Stammfunktion (Aufleitung) zweimal berechnen, für das einmal nimmt man die obere Grenze als x und subtrahiert diese mit der zweiten, welche die untere Grenze als x annimmt.
  • Kontrolle: Um zu kontrollieren, ob unser Resultat nun auch wirklich richtig ist, kann man nun die CAS Funktion “integrate” verwenden, dazu muss man zuerst das Integralzeichen mit der Klammer aufschreiben (->Katalog) und danach gibt man der Reihe nach, die gegebene Funktion (nicht Stammfunktion), dann die verwendet Variable (meist x), dann die untere Grenze und dann die obere Grenze, und alles wird mit einem Komma getrennt. Wenn nun eure Resultat mit dem des Taschenrechners übereinstimmt, habt ihrs richtig gelöst!
  • Erfüllung der Aufgabenstellung: Nun muss man nochmals die Aufgabenstellung betrachten und auch wirklich die Dinge berechnen, welche dann gefragt sind!

Taschenrechner

Hier noch ein paar Bilder wie man etwas in den Taschenrechner eingibt.

Extremal Problem lösen

int3 int4

“Aufleiten”

int2

Integrieren

int1

Kommentare [0]
Geschrieben am 04.11.2009 von admin in Reallife, School
 Tags: , , , , ,

Maturarbeit II

Nun kommt schon der zweite Post obwohl inzwischen noch nicht viel geschehen ist.

Ich hab es nun aber endlich geschafft die Zeit richtig zu berechnen, um sie dann auch für physikalische Berechnung durch zuführen. Weiter hab ich eine “Physics” Klasse eingefügt, welche dann für die physikalischen Funktionen und Berechnungen zuständig sein wird.

Zum das ganze noch ein wenig zu veranschaulichen, hab ich wieder ein kleines Video gemacht:

Kompletten Beitrag lesen

Kommentare [3]
Geschrieben am 01.11.2009 von admin in Computer, Reallife, School, Windows
 Tags: , , , , , , , ,

Maturarbeit I

So wie wohl die meistens Stammleser meines Blogs wissen, bin ich mit einem Kollegen an unserer Maturarbeit. Es geht darum ein paar physikalische Grundgesetzte am PC grafisch zu simulieren. Das ganze soll in C++ und DirectX geschrieben werden (ja OpenGL ist viel besser…) und hier hab ich ein paar kurze Videos von verschiedenen Versuchen:

Kompletten Beitrag lesen

Kommentar [1]
Geschrieben am 29.10.2009 von admin in Computer, Reallife, School, Windows
 Tags: , , , , , , , , , ,

Code::Blocks und DirectX

Für meine Maturarbeit setzte ich mich mit DirectX und C++ auseinander. Da ich Code::Blocks als IDE beim Programmieren von C++ bevorzuge, wollte ich auch meine DirectX Programme mit dieser IDE verwenden, was sich aber gar nicht als so einfach herausstellte.

Die IDE hat tollerweise ja direkt ein DirectX Wizard mitgeliefert bekommt, wollte ich dieses verwenden, welches sich dann schnell nach einer Fehlermeldung als nicht verwendbar herausstellte. Ich suchte wohl mehrere Stunden im Internet nach funktionierenden Lösungen. Probierte sogar Programme mit der Visual C++ 2008 Express Edition zum Laufen zu bringen, jedoch auch erfolglos.

Das Problem lag meistens am Linker, welcher immer irgendwelch “komischen” Fehlermeldungen zurückgab. Ein Linker Error tritt eigentlich meist dann ein, wenn mit Libraries gearbeitet wird, was im Falle von DirectX auch so ist, nur habe ich eigentlich alle DirectX Libraries, welche ich verwenden wollte eingebunden.

Nach sehr langem hin und her Probieren und Suchen, fand ich das Problem und zwar hatte ich die “gdi32” Library der Windows Plattform SDK nicht eingebunden, welche irgendwie auch noch verwendet wurde.

Da es sehr viele Code::Block Nutzer ähnliche Probleme gemeldet haben und ich nicht alleine an meiner Maturarbeit arbeite, habe ich eine kleine Übersicht erstellt, wie bei mir zumindest eines meiner Programme funktioniert hat.

Wie benutzt ich Code::Blocks und die DirectX
============================================

Was brauch ich alles?
———————
Code::Blocks
Microsoft DirectX SDK (August 2009)
Microsoft Visual C++ Toolkit 2003
Microsoft Windows Plattform SDK

Installation

Ich habe alles in die folgenden Verzeichnisse installiert und werde mich auch auf diese Beziehen:

Code::Blocks                                        -> C:ProgrammeCodeBlocks
Microsoft DirectX SDK                         -> C:ProgrammeMicrosoft DirectX SDK (August 2009)
Microsoft Visual C++ Toolkit 2003    -> C:ProgrammeMicrosoft Visual C++ Toolkit 2003
Microsoft Windows Plattform SDK    -> C:ProgrammeMicrosoft Plattform SDK

Nach der Installation sollte man sich ein wenig mit der IDE Code::Blocks vertraut machen und ausprobieren.

DirectX Wizard

Tollerweise hat Code::Blocks bereits ein Wizard für DirectX Projekte integriert, nur leider funktionierte das bei mir nicht und ich erhielt immer die Meldung: "The path seems valid, but there are no DirectX files…" o.ä.

DirectX und Code::Blocks

Nach dem das Wizard erfolgreich abgestürzt ist, müssen wir das Ganze halt anderst angehen.
Es gibt zwei Möglichkeiten, die erste ist wohl etwas die einfachere:

1.
– Erstelle ein Windows Projekt mit dem Wizard ("Win32 GUI project").
– Wähle dabei "Frame based" aus.
– Dann deine Destionantion, wo du dein Projekt abspeichern möchtest mit dem Projektnamen.
– Als Compiler musst du nun "Microsoft Visual C++ Toolkit 2003" auswählen, die anderen Felder kann man unberührt lassen.
– Als nächstest fragt er nach Installationsverzeichnis der SDK. (C:ProgrammeMicrosoft Platform SDK)
– Nun hat man ein neues Projekt, welches scho compiliert und ausgeführt werden kann.
– Jetzt muss man noch alle Libraries richtig angeben, damit der Compiler und Linker auch weiss wo was liegt.
– Dazu geht man auf Project->Build options…
– Dort wählt man nicht Debug oder Release sondern den Projektname, welcher übergeordnet ist.
– Dann wechselt man zum Tab "Search directories".
– Unter Compiler sollte jetzt stehn bzw. hinzugefügt werden (ohne -):
   – $(#psdk.include)
   – $(#dx.include)     jenachdem wird auch der Komplette Pfad benötigt
– Unter Linker kommen dann folgende Einträge:
   – $(#psdk.lib)
   – $(#dx.lib)     jenachdem wird auch der Komplette Pfad benötigt
– Dann wechselt man zum Tab "Linker settings" und fügt dort die Folgenden Libraries ein:
   – gdi32
   – user32
   – kernel32
   – d3d9.lib
   – d3dx9.lib
   – DxErr.lib
– Beachte, dass .lib entweder klein geschrieben oder ganz weggelassen wird!
– Zur Kontrolle sollte oben "Mircosoft Visual C++ Toolkit 2003" eingestellt sein.
– Fertig!
2.
– Erstelle ein leeres Projekt.
– Dann deine Destionantion, wo du dein Projekt abspeichern möchtest mit dem Projektnamen.
– Als Compiler musst du nun "Microsoft Visual C++ Toolkit 2003" auswählen, die anderen Felder kann man unberührt lassen.
– Nun hat man ein leeres Projekt.
– Füge eine neue leere Datei hinzu, und bennene sie "main.cpp" oder nach belieben.
– Jetzt muss man noch alle Libraries richtig angeben, damit der Compiler und Linker auch weiss wo was liegt.
– Dazu geht man auf Project->Build options…
– Dort wählt man nicht Debug oder Release sondern den Projektname, welcher übergeordnet ist.
– Dann wechselt man zum Tab "Search directories".
– Unter Compiler sollte jetzt stehn bzw. hinzugefügt werden (ohne -):
   – $(#psdk.include)
   – $(#dx.include)     jenachdem wird auch der Komplette Pfad benötigt
– Unter Linker kommen dann folgende Einträge:
   – $(#psdk.lib)
   – $(#dx.lib)     jenachdem wird auch der Komplette Pfad benötigt
– Dann wechselt man zum Tab "Linker settings" und fügt dort die Folgenden Libraries ein:
   – gdi32
   – user32
   – kernel32
   – d3d9.lib
   – d3dx9.lib
   – DxErr.lib
– Beachte, dass .lib entweder klein geschrieben oder ganz weggelassen wird!
– Zur Kontrolle sollte oben "Mircosoft Visual C++ Toolkit 2003" eingestellt sein.
– Fertig!

 

So ich wünsch euch nun viel Spass bei DirectX programmieren! =)

Mathematik – Analysis I

Nun wieder einmal ein Beitrag zum Thema Mathematik. Da wir Morgen einen Test schreiben und viele aus meiner Klasse die ganzen Ableitungen usw. immer noch nicht ganz gepeilt haben, haben ein kleines Dossier erstellt, in welchem die grundlegenden Dinge noch einmal einfach erklärt sind.

Da das Dossier sehr schnell geschrieben wurde, dürft ihr alle Rechtschreibefehler behalten und ich geben keine Garantie auf absolute Richtigkeit! Viel Spass trotzdem!

Download: Microsoft Word 2007 oder Microsoft Word 98-2003

Kommentar [1]
Geschrieben am 02.09.2009 von admin in Reallife, School
 Tags: , , , ,

Mathematik Orientierungs(lose) Arbeit

So nach dem tollen Beschluss der geehrten Schulleitung unseres Gymnasiums, kann man nun seine Mathematik OA wiederholen.
Um den Leuten, welche dieses riskante Vorhaben anstreben, zu helfen, habe ich meine OA eingescannet und korrigiert.

Seite 1/8


Seite 2/8


Seite 3/8


Seite 4/8


Seite 5/8


Seite 6/8


Seite 7/8


Seite 8/8

Viel Spass und Erfolg damit!

Fragen einfach als Kommentar anfügen!

Kommentare [2]
Geschrieben am 06.06.2009 von admin in School
nächste Seite »