Sök i kursutbudet

Använda sökfunktionen för att hitta i Chalmers utbildningsutbud, både vad gäller kurser och program. När det finns en kurshemsida visas en hus-symbol som leder till denna sida. Tänk på att välja det läsår du vill se information om.
Sök program och utbildningsplaner


Institutionernas kurser för doktorander

​​​​​​​​​​​​​​​​​​​​

Kursplan för

Läsår
TIN092 - Algorithms
 
Kursplanen fastställd 2009-02-25 av programansvarig (eller motsvarande)
Ägare: MPALG
7,5 Poäng
Betygskala: TH - Fem, Fyra, Tre, Underkänt
Utbildningsnivå: Avancerad nivå
Huvudområde: Datateknik, Informationsteknik
Institution: 37 - DATA- OCH INFORMATIONSTEKNIK


Kurstillfälle 1


Undervisningsspråk: Engelska

Modul   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs
0106 Tentamen 7,5 hp Betygskala: TH   7,5 hp   19 Okt 2010 em M,  11 Jan 2011 fm V,  25 Aug 2011 fm M
0206 Laboration 0,0 hp Betygskala: UG   0,0 hp    

I program

TKDAT DATATEKNIK, CIVILINGENJÖR, Årskurs 3 (valbar)
ITIDM INTELLIGENT SYSTEMS DESIGN, Årskurs 2 
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Årskurs 1 (obligatorisk)
MPIES INTEGRATED ELECTRONIC SYSTEM DESIGN, MSC PROGR, Årskurs 2 (valbar)
MPNET NETWORKS AND DISTRIBUTED SYSTEMS, MSC PROGR, Årskurs 2 (valbar)
MPSEN SOFTWARE ENGINEERING AND TECHNOLOGY, MSC PROGR, Årskurs 1 (valbar)
MPSEN SOFTWARE ENGINEERING AND TECHNOLOGY, MSC PROGR, Årskurs 2 (valbar)
MPSYS SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR, Årskurs 2 
TKITE INFORMATIONSTEKNIK, CIVILINGENJÖR, Årskurs 3 

Examinator:

Univ adjunkt  Erland Holmström
Professor  Devdatt Dubhashi
Bitr professor  Peter Damaschke



Kurstillfälle 2


Undervisningsspråk: Engelska

Modul   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs
0106 Tentamen 7,5 hp Betygskala: TH   7,5 hp   23 Maj 2011 em V
0206 Laboration 0,0 hp Betygskala: UG   0,0 hp    

I program

TKDAT DATATEKNIK, CIVILINGENJÖR, Årskurs 3 (valbar)
ITIDM INTELLIGENT SYSTEMS DESIGN, Årskurs 1 
MPIES INTEGRATED ELECTRONIC SYSTEM DESIGN, MSC PROGR, Årskurs 1 (valbar)
MPNET NETWORKS AND DISTRIBUTED SYSTEMS, MSC PROGR, Årskurs 1 (valbar)
MPSEN SOFTWARE ENGINEERING AND TECHNOLOGY, MSC PROGR, Årskurs 1 (valbar)
MPSYS SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR, Årskurs 1 
TKITE INFORMATIONSTEKNIK, CIVILINGENJÖR, Årskurs 3 (valbar)
TKITE INFORMATIONSTEKNIK, CIVILINGENJÖR, Årskurs 2 (valbar)

Examinator:

Univ adjunkt  Erland Holmström
Professor  Devdatt Dubhashi
Bitr professor  Peter Damaschke



Ersätter

TIN090   Algoritmer

Kursutvärdering:

http://document.chalmers.se/doc/1022566681


  Gå till kurshemsida

Behörighet:

För kurser inom Chalmers utbildningsprogram gäller samma behörighetskrav som till de(t) program kursen ingår i.

Kursspecifika förkunskaper

An introductory course in data structures and elementary knowledge in discrete mathematics.

Syfte

The algorithms course revolves around three central questions that appears naturally when one wants to use a computer to compute a problem:

  • Is the problem computationally solvable at all?
  • How can we do it?
  • How fast can the solution be?

The course shall provide basic knowledge and methods to answer these types of question as precisely as possible, and improve the ability to write fast and well-founded programs.


Other important aspects are: to improve the intuitive sense of time complexity of problems and algorithms in general, to show how the choice of data structures can influence speed of a program, and how data structures must be adapted to algorithms.


The most important goal of the course is to give general principles of creating good algorithms for new problems for which you cannot find any published algorithm.

Lärandemål (efter fullgjord kurs ska studenten kunna)

After attending the course you will be able to:

  • Model problems: Formulate a clear mathematical model of real world problems.
  • Design algorithms: Construct algorithms with several algorithm design methods
    and be able to choose appropriate data structures and abstractions.
  • Describe your algorithms and their qualities to others.
  • Prove correctness: Prove that your algorithms are correct.
  • Analyse algorithms: perform an objective evaluation of the performance and be able to compare it to other algorithms performance.
  • Recognize intractable problems and other classes of problems like P, NP, NPC
  • Recognize a number of specific algorithms for basic problems which tend to appear over and over again in different applications

You will also know something about

  • Problem analysis: how to analyse the complexity of a problem e.g. how much
    resources are require to solve a problem.
  • Approximation algorithms: how to solve problems with exponential complexity.

However, be aware that this is not a course in programming! The main focus is on the design of algorithms from a given problem specification and the analysis of efficiency of these algorithms. This is, so to speak, the analytical work that has to be done before writing any line of code, if one wants to solve a new problem with the help of computers.

Innehåll

The course topics are as follows:

  • Introduction. What is an algorithm? Description of algorithms. What is an efficient algorithm?
  • Tools for analysis of algorithms. O-notation. Analyzing loops and recursive calls. Amortized analysis. Solving recurrences.
  • Data structures and algorithms. Review of basic data structures. Combining data structures. Merge-and-find.
  • Graph algorithms.
  • Greedy algorithms.
  • Dynamic programming.
  • Divide-and-conquer.
  • Backtracking and Implicit search trees. Branch-and-bound.
  • Introduction to local search and approximation algorithms.
  • Basic complexity theory. Complexity classes P, NP, and NPC, reductions. Examples of NP-complete problems. NP-hard problems. Coping with hard problems.
  • Short introduction to other design techniques: local search, approximation algorithms, randomized algorithms, preprocessing band network flow.

Organisation

The course is given as lectures, combined with tutorial groups for problem solving related to the course and programming exercises (laboration) and a number of assignments intended to develop the skill of analyzing and designing algorithms.

Litteratur

Information about literature is given on the course homepage before course start.

Examination

Examination consist of two parts: written exam and laboration.
To pass the course you have to finish both these parts during the course (within one year from course start).


Sidansvarig Publicerad: må 13 jul 2020.