Algoritmik og Datastrukturer

  • user warning: Got error 28 from storage engine query: SELECT DISTINCT t.* FROM drupal_term_node r INNER JOIN drupal_term_data t ON r.tid = t.tid INNER JOIN drupal_vocabulary v ON t.vid = v.vid LEFT JOIN drupal_forum_access fa ON t.tid = fa.tid LEFT JOIN drupal_acl acl_fa ON acl_fa.name = t.tid AND acl_fa.module = 'forum_access' LEFT JOIN drupal_acl_user aclu_fa ON aclu_fa.acl_id = acl_fa.acl_id AND aclu_fa.uid = 0 WHERE ((fa.grant_view >= 1 AND fa.rid IN (1)) OR fa.tid IS NULL OR aclu_fa.uid = 0) AND ( r.vid = 2516 )ORDER BY v.weight, t.weight, t.name in /var/www/dikutal.dk/modules/taxonomy/taxonomy.module on line 632.
  • user warning: Got error 28 from storage engine query: SELECT DISTINCT node.nid AS nid, node.title AS node_title, node.language AS node_language, node.type AS node_type, node.vid AS node_vid, node_revisions.teaser AS node_revisions_teaser, node_revisions.format AS node_revisions_format, node_data_field_date.field_date_value AS node_data_field_date_field_date_value FROM drupal_node node LEFT JOIN drupal_content_field_date node_data_field_date ON node.vid = node_data_field_date.vid LEFT JOIN drupal_term_node term_node ON node.vid = term_node.vid AND (term_node.tid = 9 OR term_node.tid = 10 OR term_node.tid = 12 OR term_node.tid = 19 OR term_node.tid = 18 OR term_node.tid = 13 OR term_node.tid = 16 OR term_node.tid = 17 OR term_node.tid = 11 OR term_node.tid = 14 OR term_node.tid = 15) LEFT JOIN drupal_node_revisions node_revisions ON node.vid = node_revisions.vid INNER JOIN drupal_node_access na ON na.nid = node.nid WHERE (na.grant_view >= 1 AND ((na.gid = 0 AND na.realm = 'all') OR (na.gid = 1 AND na.realm = 'book_page_access_view') OR (na.gid = 1 AND na.realm = 'forum_access'))) AND ( ((node.status <> 0) AND (node.type in ('event')) AND (term_node.tid IS NULL)) AND (DATE_FORMAT(ADDTIME(node_data_field_date.field_date_value, SEC_TO_TIME(7200)), '%Y-%m-%d') >= '2014-10-22') )ORDER BY node_data_field_date_field_date_value ASC LIMIT 0, 3 in /var/www/dikutal.dk/sites/all/modules/views/includes/view.inc on line 771.
Skrevet af Dybber, 2. december 2010 - 21:31

Algoritmik og Datastrukturer er et obligatorisk bachelorkursus, der ligger i blok 4 på første studieår. Lige et par definitioner inden vi beskriver hvad kurset indeholder:

  • Algoritme: En algoritme er en fremgangsmåde til at løse et specifikt problem via beregninger. F.eks. hvordan man opnår et specielt resultat (hvordan ser den sorterede udgave af denne liste ud?) eller foretager en beslutning (er denne liste sorteret?).
  • Datastruktur: Forskellige typer af data kræver specielle måde at organisere og anskue computerens hukommelse. F.eks. er mapperne på en computer normalt organiseret i en træ-struktur, hvorfor man repræsenterer dem som et træ i hukommelsen.

På kurset undervises i en lang række grundlæggende datastrukturer og de algoritmer der behandler dem. Man lærer hvordan en algoritme nedskrives så andre kan læse den (pseudekode) og hvordan man argumenterer eller beviser at sin algoritme er korrekt. Der undervises også i hvordan man analyserer køretiden for sin algoritme og pladsforbruget af de datastrukturer som den benytter. Disse analyser ender ud i et mål der kan bruges til at sammenligne sin algoritmes effektivetet med andre tilsvarende algoritmer.

Stikord: Algoritmer, Datastrukturer, Sortering, Træer, Grafer, Hobe (Heaps), Store-O notation, Køretidsanalyse, Rød-sorte træer, Mindste-udspændende træ, Korteste veje i grafer, m.m.

Undervisere

(dette er på ingen måde en komplet liste)

  • Pawel (??-2010)
  • Martin Zachariasen (??-2009)
  • Jyrki (2010)

Kurset blev i 2008 flyttet til blok 4.

Lærebog

På kurset bruges 3. udgave af bogen "Introduction to Algorithms" af Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, og Clifford Stein.

  • ISBN: 0-262-03384-4
  • Forlag: MIT Press
  • Wikipedia-link: http://en.wikipedia.org/wiki/Introduction_to_Algorithms

Bogen bliver ofte referet til som CLR, CLRS eller Cormen. Den er et grundlæggende værk i datalogien, der formentlig bruges på størstedelen af alle Computer Science uddannelser verden over. Søger man på den på Google Scholar kan man se at den har over 22000 citeringer (December, 2010).

SIS

Handlinger