Prosecode Heapsort

Heapsort (list), fügt eine Liste list in einen Heap ein und gibt sie in sortierter Reihenfolge wieder aus, wahlweise vom kleinsten zum größten Element bzw. umgekehrt. Durch die Eigenschaften der Datenstruktur Heap befindet sich an der Stelle heap[0] immer der kleinste/größte Eintrag der Liste.

Die Schritte des Algorithmus:

1. Einfügen der Listenelemente in den Heap:
Das einzufügende Element aus der übergebenen Liste list wird an der Stelle i auf den Heap       gelegt und i um 1 erhöht. Dies wiederholt sich bis list leer ist:
for each position i in list –> heap.insert(list[i])

2. Auslesen des Heaps:
An Stelle heap[0] befindet sich das kleinste/größte Element. Dieses wird aus heap entfernt und zurück in list gespeichert. Dies wiederholt sich, bis heap leer ist. In list befindet sich anschließend die sortierte Folge:
while heap.length not 0:
heap.remove(heap[0])
and
for each position i in list –> list[i] = heap.remove(heap[0])

Anwendung Checkliste „Efficient Graph-Based Document Similarity“

  1. What phenomena or properties are being investigated? Why are they of interest?
    – Ähnlichkeiten zwischen Dokumenten sollen anhand eines effizienten Graphs erkannt werden, der auf Semantikuntersuchungen basiert
    – gängige Methoden operieren z.Bsp über Wortverteilung innerhalb des Textes
    – dabei werden Mehrdeutigkeit von Wörtern und Synonyme häufig zum Problem
    – außerdem sind Vergleiche zwischen verschiedenen Texten schwierig, z. Bsp. durch Verwendung unterschiedl. Vokabulars
  2.  Has the aim of the research been articulated? What are the specific hypotheses and research questions? Are these elements convincingly connected to each other?
    – gibt nicht wirklich Hypothesen
    – sie wollen zeigen, dass ihr Algorithmus:
    1. Vergleichsergebnis höhere Korrelation mit der menschlichen Vorstellung von Dokumentenähnlichkeit
    2. auch für kurze Dokumente anwendbar
    3. durch die Graph-Basirung effizient
  3. To what extent is the work innovative? Is this reflected in the claims?
    –  der Vergleich auf semantischer Ebene verbessert die gängigen Methoden –> zuverlässeriges Finden von Ähnlichkeiten
  4. What would disprove the hypothesis? Does it have any improbable consequences?
    – es werden keine negativen Aspekte im Paper benannt
    – wenn es nicht schneller wäre oder die Ergebnisse des Vergleichs von Dokumenten gleich oder schlechter ist, als bei bisherigen Verfahren
  5. What are the underlying assumptions? Are they sensible?
    – Texte sind vergleichbar anhand semantischer Zusammenhänge
  6. Has the work been critically questioned? Have you satisfied yourself that it is sound science?
    – ausführliche Modelbeschreibung bei den Ähnlichkeitsfunktionen
    – aber keine Einschränkungen oder kritische Fälle werden betrachtet
    –> eher nein
  7. What forms of evidence are to be used? If it is a model or a simulation, what demonstrates that the results have practical validity?
    – mathematisches Model als Grundlage der Ähnlichkeitsfunktionen
    – Experimente mit echten Datensätzen
  8. How is the evidence to be measured? Are the chosen methods of measurement objective, appropriate, and reasonable?
    – wird die Suchzeit-Kompkexität betrachtet –> sinnvoll, da ein schnelleres Verfahren als bisherige erreicht werden soll
    – Vergleich der Ergebnisse aus Experimenten –> ebenfalls sinnvoll, da sie bessere Suchergebnisse erzielen wollen
  9. What are the qualitative aims, and what makes the quantitative measures you have chosen appropriate to those aims?
    – Qualität: schneller und bessere Vergleichsergbnisse
  10. What compromises or simplifications are inherent in your choice of measure?
    – Nicht beantwortbar, da ich das Paper nicht geschrieben habe und damit nicht für Wahl verantwortlich war
  11. Will the outcomes be predictive?
  12. What is the argument that will link the evidence to the hypothesis?
    – Ergebnisse der Experiemente und der Laufzeitvergleich(?)
  13. To what extent will positive results persuasively confirm the hypothesis? Will negative results disprove it?
  14. What are the likely weaknesses of or limitations to your approach?
    – Es muss bei kurzen Sätzen mindestens eine Einheit gefunden werden mit der verknüpft werden kann

Abstract Bioinformatik

Der Begriff Bioinformatik wurde 1977 erstmalig von der dänischen Forscherin Paulien Hogeweg, die im Bereich theoretische Biologie tätig ist, verwendet.
Seither hat sich die Bioinformatik als interdisziplinäre Wissenschaft, die Mathematik, Informatik und Molekularbiologie miteinander verknüpft, fest etabliert. Unter Verwendung von mathematischen und informatischen Techniken werden biologische Daten, wie DNA- und Proteinsequenzen, organisiert und analysiert. Dieses Paper gibt einen Überlick über wesentliche Werkzeuge der Informatik, die in der Bioinformatik Anwendung finden.
Datenbanken bilden die Grundlage der Forschung im Bereich Bioinformatik und der Datenbestand wächst exponentiell. Die Bereitstellung und Pflege entsprechender Datenbanken, sowie Möglichkeiten in diesen zu suchen, zu vergleichen und Datensätze zu verknüpfen ist ein  wichtiger Aspekt.
Des weiteren bedingen die speziellen Anforderungen der Bioinformatik Programme zur Analyse von biologischen Daten, bspw. um Sequenzähnlichkeit festzustellen (FASTA), Gene zu  identifizieren oder Vorhersagen treffen zu können. Dazu werden u.a. Algorithmen aus den  Bereichen Klassifikation und Clustering, Aufbau von Netzwerken und Simulation verwendet,  deren Zusammenspiel ebenfalls in diesem Paper betrachtet wird.

 

Referenzen:

Attwood, T., Gisel, A., Bongcam-Rudloff, E., Eriksson, N.: Concepts, historical milestones
and the central place of bioinformatics in modern biology: a European perspective.
INTECH Open Access Publisher (2011)

Böckenhauer, H.J., Bongartz, D.: Algorithmische Grundlagen der Bioinformatik:
Modelle, Methoden und Komplexität. Springer-Verlag (2013)

Hütt, M.T., Dehnert, M.: Methoden der Bioinformatik: Eine Einführung zur Anwendung in
Biologie und Medizin. Springer-Verlag (2015)

Luscombe, N.M., Greenbaum, D., Gerstein, M., et al.: What is bioinformatics?
a proposed definition and overview of the field. Methods of information in medicine 40(4),
346–358 (2001)

Merkl, R.: Bioinformatik: Grundlagen, Algorithmen, Anwendungen. John Wiley & Sons (2015)

Literatur Student Project

Ich habe Google Scholar genutzt und mich hauptsächlich auf einführende Literatur und Lehrbücher konzentriert, um mir erst einmal eine Überblick über das Thema zu verschaffen. Die Suche nach Papers möchte ich erst starten, wenn ich besser einschätzen kann, in welche Richtung ich suchen muss.

  1. Böckenhauer, H.J., Bongartz, D.: Algorithmische Grundlagen der Bioinformatik: Modelle, Methoden und Komplexität. Springer-Verlag (2013)
  2. Hütt, M.T., Dehnert, M.: Methoden der Bioinformatik: Eine Einführung zur Anwendung in Biologie und Medizin. Springer-Verlag (2015)
  3. Merkl, R.: Bioinformatik: Grundlagen, Algorithmen, Anwendungen. John Wiley & Sons (2015)
  4. Attwood, T., Gisel, A., Bongcam-Rudloff, E., Eriksson, N.: Concepts, historical milestones and the central place of bioinformatics in modern biology: a European perspective. INTECH Open Access Publisher (2011)
    –> Dieses Paper habe ich zufällig bei der Scholarsuche entdeckt und es wurde relativ oft (33 mal) zitiert. Die Grafiken sind zwar gruselig und der Aufbau erinnert mehr an ein Buchkapitel, aber es scheint einen recht guten Überblick über die Entwicklung des Themengebiets zu geben. Im Zweifelsfall geeignet, um Anregungen zu finden, in welche Richtung man weiter recherchieren kann.
  5. Ouzounis, C.A.: Rise and demise of bioinformatics? promise and progress. PLoS Comput Biol 8(4), 1–5 (04 2012)
    –> Wird in „Methoden der Bioinformatik“ zitiert.

 

Hausaufgabe 4 – Punctuation Game

  • We live in the era of Big Data, with storage and transmission capacity measured not just in terabytes but in petabytes (where peta- denotes a quadrillion or a thousand trillion). Data collection is constant and even insidious, with every click and every “like” stored somewhere for something. This book reminds us that data is anything but “raw”;? that we shouldn’t think of data as a natural resource but as a cultural one that needs to be generated, protected, and interpreted. The book’s essays describe eight episodes in the history of data, from the predigital to the digital. Together they address such issues as the ways that different kinds of data and different domains of inquiry are mutually defining, how data are variously “cooked” in the processes of their collection and use, and conflicts over what can  –or can’t-? be “reduced” to data. Contributors discuss the intellectual history of data as a concept describe early financial modeling, and some unusual sources for astronomical data discover, the prehistory of the database in newspaper clippings and index cards, and consider contemporary “dataveillance” of our online habits as well as the complexity of scientific data curation.
  • During succession, ecosystem development occurs but in the longterm absence of catastrophic disturbance, a decline phase eventually follows. We studied six long term chronosequences in Australia, Sweden, Alaska, Hawaii, and New Zealand; for each the decline phase was associated with a reduction in tree basal area and an increase in the substrate nitrogen-to-phosphorus ratio, indicating increasing phosphorus limitation over time. These changes were often associated with reductions in litter decomposition rates, phosphorus release from litter and biomass, and activity of decomposer microbes. Our findings suggest that the maximal biomass phase reached during succession, cannot be maintained in the longterm absence of major disturbance and that similar patterns of decline occur in forested ecosystems spanning the tropical, temperate, and boreal zones.

Per Warp durchs All?

Der Traum sich im Weltall unbegrenzt fortzubewegen, fremde Galaxien, außerirdisches Leben und vielleicht eine zweite Erde zu finden, all das regt schon lange Fantasie und Forscherdrang des Menschen an. Doch die Probleme rund um das interstellare Reisen sind so vielfältig, wie Science Finktion Literatur. Mark Alpert greift in seinem Artikel „Warp drive research key to interstellar travel“ diese Probleme auf, beleuchtet aber gleichzeitig die mannigfaltigen Versuche des Menschen sich diesen Probleme zu nähern.

Problem Nummer eins bilden die Antriebstechniken. Zum einen ist die erzeugbare Geschwindigkeit zu gering. Selbst kleine unbemannte Raumsonden bräuchten bspw. über 70.000 Jahre um einen der Sterne zu erreichen, der unserer Erde sehr ähnlich zu sein scheint.
Zum anderen ist die Kapazität für Treibstoff begrenzt.

Die NASA investiert jährlich etwa $50.000, um die Umsetzung des, aus „Raumschiff Enterprise“ bekannten, Warp-Antriebs zu erforschen. Eine eher hypothetische Möglichkeit, die darauf basiert um das Raumfahrzeug eine Blase aus verzerrter Raumzeit entstehen und so durch die Raumzeit „springen“ zu lassen. Unter der Leitung von Harold „Sonny“ Smith untersucht man gerade, in wie weit winzige Verzerrungen der Raumzeit überhaupt möglich sind.
Der Traum vom Reisen durchs All vereint Wissenschaftler, Ingenieure und weltraumbegeisterte Amateure. Es gibt verschiedene Organisationen, bspw. 100 Year Starship Project, the Tau Zero Foundation und Icarus Interstellar, außerdem Konferenzen zum Austausch von Ideen und Forschung, die sich thematisch auch weit ab vom Warp-Antrieb bewegen.
Icarus Interstellar bspw. koordiniert Untersuchungen, nukleare Methoden als Antriebstechnik zu verwenden. Seit mehr als 50 Jahren wird auf diesem Gebiet experimentiert. Leider bisher ohne nennenswerte Erfolge.

Als zweites großes Problem muss der interstellare Staub einberechnet werden, obwohl die Staubkörner nur mikroskopisch klein sind. Es ist zu erwarten, dass ein auf Millionen km/h beschleunigtes Objekt immensen Schaden durch Kollisionen mit diesem Staub nehmen wird. Eine verstärkte Panzerung könnte abhelfen, erfordert durch das gesteigerte Gewicht jedoch wiederrum zusätzlichen Treibstoff. Die Mitnahme von letzterem ist und bleibt aber begrenzt.

Mit der extremen Geschwindigkeit geht ein weiteres Problem einher, der „Bremsweg“. Um nicht am eigentlichen Ziel vorbeizurauschen, muss sich die Raumsonde verlangsamen können. Im Weltall ist dies nur erreichbar, wenn der Antrieb sich umdrehen und in die entgegengesetzte Richtung feuern kann. Diese Art des Verlangsamen bedingt wiederrum, dass mehr Treibstoff verbraucht wird und somit mitgeführt werden muss.

Mark Alpert kommt in seinem Artikel zu dem Schluss, dass sich, trotz der vielen Probleme, der Traum vom interstellaren Reisen hartnäckig hält. Vielleicht auch deswegen, weil die Flucht ins All als einzige Möglichkeit betrachtet wird, uns Menschen langfristig das Überleben zu sichern. Denn solange der Mensch an die Erde gebunden ist, ist das Risiko auszusterben groß.
In unserem eigenen Sonnensystem kommt allerdings nur der Mars annährend als „neue Erde“ in Frage. Um diesen jedoch für uns bewohnbar zu machen, sind noch hunderte Jahre Klimaengineering nötig.

Bis wir den Sprung ins All schaffen, sollten wir uns, auf Empfehlung von Mark Alpert, immer das Motto der Enterprise vor Augen halten: „We have “to boldly go where no man has gone before.”“.

Hausaufgabe 3 – Ambiguity

  1. improper syntax (1): …Department of Energy is only considering Yucca Mountain… –> …Department of Energy is considering only Yucca Mountain…

2. missing comma (2): If the airplane waits too long to take off, the de-ice fluid can dissipate.

3. Ich bin hier total unsicher, aber ich halte beides für möglich:
? grouping of conflicting words (4): ….only designed to hold two astronauts and to have…
? improper syntax(1): …designed to hold only two astronauts and to have only a life time…

4. missing comma (2): The beams are positioned with respect to the chopper blade so that while one beam passes, the output of the opposite beam is completely blocked.

5. unclear pronoun reference (3): The report claimed that a hull wire could have ruptured a gas cell if it fractured. –> If what fractured? A hull wire or a gas cell?

6. ???

7. grouping of conflicting words (4): …all tanks were equipped with basins and automatic shutoff devices or overfill alarms or ball float valves. –> Unklar mit was die Tanks alles ausgestattet wurden.

8. improper syntax (1): „Being the first step…“

9. missing comma (2): As with any system, errors occur in localization.

10. improper syntax (1)“ …predict the effects of engine operation over all speeds.“