Algorithms

/**
* Performs a sequential search using sentinel
* and changes the array after the value is found
*
* @param array $arr
* @param mixed $value
*/
function sequential_search(&$arr, $value)
{
$arr[] = $value;
$index = 0;
 
while ($arr[$index++] != $value);
 
if ($index < count($arr)) {
 
// put the item at the front of the list
array_unshift($arr, $arr[$index-1]);
 
// remove the value from its previous position
unset($arr[$index]);
 
// unset the sentinel
unset($arr[count($arr)+1]);
 
return true;
}
 
return false;
}
 
// the list
$arr = array(1, 2, 3, 3.14, 5, 4, 6, 9, 8);
 
// the value
$x = 3.14;
 
if (sequential_search($arr, $x)) {
// now the array is changed to
// (3.14, 1, 2, 3, 5, 4, 6, 9, 8)
echo "The value $x is found!";
} else {
echo "The value $x doesn't appear to be in the list!";
}

 

Ich würde die Hausaufgabe gerne machen,aber im ersten Semester kenne ich mich damit leider noch nicht aus:/

 

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

Hausaufgabe Checkliste – Kai

Regarding hypotheses and questions

  • What phenomena or properties are being investigated? Why are they of interest?
    • Graph-based document models are often slow, but are can give promising results. Paper invesitgates means to improve performance. They are of intereset since relatedness of documents are used in many applications  (e.g. document retrieval and recommendation).
  • Has the aim of the research been articulated? What are the specific hypotheses and
    research questions? Are these elements convincingly connected to each other?

    • Not really hypotheses / research questions.
    • Developing a faster algorithm compared to other graph-traversal based approaches.
    • Specific claims:

      • higher correlation with human notions of document similarity
      • holds for short documents with few annotations
      • document similarity is computed (more) efficiently
  • To what extent is the work innovative? Is this reflected in the claims?
    • They use a different/new  approach for efficient knowlegde-graph based semantic similarity (the preprocessing step called Semantic Document Expansion??)
  • What would disprove the hypothesis? Does it have any improbable consequences?
    • Not really hypothesis, rather their claims: It would be disproved if the results from the experiments would be slower / worse than the other approaches.
  • What are the underlying assumptions? Are they sensible?
  • Has the work been critically questioned? Have you satisfied yourself that it is
    sound science?

Regarding evidence and measurement

  • What forms of evidence are to be used? If it is a model or a simulation, what
    demonstrates that the results have practical validity?

    • Running a simulation with standard benchmark (enables comparison with other work).
  • How is the evidence to be measured? Are the chosen methods of measurement
    objective, appropriate, and reasonable?

    • Is measured by results from experiments. Its objective, fitting, reasonable.
  • What are the qualitative aims, and what makes the quantitative measures you have
    chosen appropriate to those aims?

    • Qualtitative aims: approach is faster / better than similar approaches
    • Quantitative measures: correlation, time, ranking in comparison to other approaches
  • What compromises or simplifications are inherent in your choice of measure?
    • I don’t know. Maybe that it uses a standard benchmark
  • Will the outcomes be predictive?
  • What is the argument that will link the evidence to the hypothesis?
    • I think plain, objective data is enough as an argument. So no real argument is given.
  • To what extent will positive results persuasively confirm the hypothesis? Will
    negative results disprove it?

    • Positive results ARE the proof, that confirms the “hypothesis” (the claim that its better), thus negative results would easily disprove them.
  • What are the likely weaknesses of or limitations to your approach?
    • Works only for short sentences if an entity can be found to be linked with (maybe its not that improbable that sentences don’t have entities, I don’t know)

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)

Natural Language Processing Abstract

The following paper will discuss the field of Natural Language Processing, starting with different definitions and explaining these by using specific examples. Furthermore it will give an overview over the history and the evolution of Natural Language Processing over the years and explain, how and where it is used. Lastly, the paper will take a look on the possible future path, Natural Language Processing could head down.

Abstract: Swarm Intelligence

Häufig werden neue Lösungsansätze für Probleme in der Informatik durch reale Phänomene inspiriert. Die Swarm Intelligence ist ein solcher Lösungsansatz. Sie ist dem Gebiet der künstlichen Intelligenz (AI)  zuzuordnen und ist von dem kollektiven Verhalten sozialer Tiere, allen voran den Insekten,  inspiriert.

Ameisen, Termieten, Wespen, Bienen, Vögel und Fische sind Beispiele solcher Tiere. Als Gruppe bilden die einzelnen Individuen ein emergentes System. Obgleich die Individuen mit nur begrenztem Wissen und einer recht niedrigen Intelligenz ihre Aufgaben verrichten, scheint das System als solches komplex, intelligent und problemlösend zu sein. So sind beispielsweise  Ameisen in der Lage gemeinsam komplexe Nester zu bauen, obgleich keine der Ameisen das Wissen um einen gemeinsamen Plan des Bauwerkes besitzt. Sie arbeiten selbstorganisierend und dezentralisiert.

In der Informatik werden die Individuen solcher Tiere als sogenannte Agenten modeliert. Jeder Agent hat dabei recht simple Aufgaben und weiß von anderen Agenten in der Nähe. Mit diesem simplen Modell lassen sich sehr komplexe Probleme lösen. Häufige Anwendungsgebiete finden sich in der Robotik und Optimierung. Bei der Optimierung ist ein solches Swarm Intelligence System beispielsweise äußerst robust und leidet äußerst selten unter dem Problem, nur ein lokales Extrem zu finden.

Nachdem das vorliegende Paper die grundlegenden Aspekte von Swarm Intelligence erläutert hat, folgen Anwendungsgebiete und Beispiele in denen sie genutzt wird. Anschließend werden Probleme und die Einschränkungen von Swarm Intelligence näher gebracht. Das Paper schließt dann mit einem Ausblick auf die Entwicklung von Swarm Intelligence ab.

 

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.

 

Student Project Sources

Adam L. Berger,Stephen A. Della Pietra, Vincent J. Della Pietra: A Maximum Entropy Approach to Natural Language Processing. Association for Computational Linguistics, 1996    (Anzahl von Zitierungen)

Christopher D. Manning, Hinrich Schütze: Foundations of Statistical Natural Language Processing. Cambridge, The MIT Press,1999

S. Bird, E. Klein, E. Loper: Natural language processing with Python. O’Reilly Media, 2009