Algoritmusok és adatstruktúrák

Algorithms and Data Structures

A tantárgyleírás hatályossága

Hatályosság kezdete:

2026. March 21.

Hatályosság vége:

—

Tantárgy neve (magyarul, angolul)

Algoritmusok és adatstruktúrák

Algorithms and Data Structures

Tantárgykód

BMEVISZA079

Tantárgyjelleg

—

Képzési szint

—

Kurzustípusok és óraszámok (heti/féléves)

Kurzustípus	elmélet	gyakorlat	laboratóriumi gyakorlat
óraszám (heti)	3	1	0
jelleg (kapcsolt/önálló)	—	kapcsolt	—

Tanulmányi teljesítmény/értékelés típusa

vizsga

Tantárgy kreditértéke

Tantárgyfelelős

DR. Csima Judit

beosztás: egyetemi docens

elérhetőség: csima.judit@vik.bme.hu

Tantárgyat gondozó oktatási szervezeti egység

Számítástudományi és Információelméleti Tanszék

Kar

Villamosmérnöki és Informatikai Kar

Tantárgy weboldala

www.cs.bme.hu/....

Tantárgy elsődleges mintatantervi jellege

—

Közvetlen előkövetelmények – Erős előkövetelmény

nincs

Közvetlen előkövetelmények – Gyenge előkövetelmény

nincs

Közvetlen előkövetelmények – Párhuzamos előkövetelmény

nincs

Közvetlen előkövetelmények – Mérföldkő előkövetelmény

nincs

Közvetlen előkövetelmények – Kizáró feltétel

nincs

Célkitűzés

Tantárgyprogram

First half-semester – Basic techniques and data structures
1. Introduction to algorithms
    Recursion
    Divide and conquer
    Analyzing algorithms
2. Dynamic programming
    Longest common superstring
    Edit distance of strings
    String matching
3. Graph algorithms
BFS and its applications
    Connected components
    Shortest paths
    Recognizing bipartite graphs
    Finding maximum matching in bipartite graphs
4. DFS and its applications
    Strongly connected components
    Directed acyclic graphs
    Shortest and longest path in directed acyclic graphs
5. Shortest path in weighted graphs
    Bellman-Ford algorithm
    Floyd's algorithm
    Dijkstra's algorithm
6. Minimum spanning trees
    Basic properties
    Greedy algorithms (Jarnik-Prim, Kruskal)

Second half-semester – Graph algorithms and geometric algorithms

7. Search in unordered list: worst case and average case
    Finding the smallest and the largest element in a list
    Finding the median in linear time in ordered list
8. Search trees
    B-tree
    Hashing
9. Sorting algorithms:
    Bubble sort
    Insertion sort
    Merge sort
    Quicksort
10. Lower bound on number of comparisons
    Binsort and radix sort11. Union-find data structure
    Geometric problems in the plane
    Intersection of line segments
12. Closest pair of points
    Determining the convex hull of points

Basic techniques and data structures will be presented in the first half of the course (introduction to algorithms, dynamic programming, search in unordered lists - worst case and average case, search trees, sorting algorithms, lower bound on number of comparisons) The second half of the course will focus on graph algorithms and geometric algorithms. Among the graph algorithms special emphasis will be given to BFS and its applications (connected components, shortest paths, recognizing bipartite graphs, finding maximum matching in bipartite graphs), DFS and its applications (strongly connected components, directed acyclic graphs, shortest and longest paths in directed acyclic graphs), shortest paths in weighted graphs and minimum spanning trees. The geometry part will include geometric problems in the plane, intersection of line segments, closest pair of points and determining the convex hull of points.

Tanulmányi eredmények

Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:

Tudás

Nincsenek rögzített tanulási eredmények.

Képességek

Nincsenek rögzített tanulási eredmények.

Attitűd

Nincsenek rögzített tanulási eredmények.

Autonómia és felelősség

Nincsenek rögzített tanulási eredmények.

Oktatási módszertan

Lectures and recitations

Tanulástámogató anyagok

Nincs megadva.

A tantárgy teljesítéséhez ajánlott előzetes ismeretek

Tudás típusú kompetenciák

(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)

None

Képesség típusú kompetenciák

(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)

nincs

Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák

(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)

None

Általános szabályok

Nincs megadva általános szabály.

Teljesítményértékelési módszerek

Szorgalmi időszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Szorgalmi időszakban végzett teljesítményértékelések részaránya

Nincs megadva részarány.

Vizsgaidőszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Vizsgarészek részaránya

Nincs megadva részarány.

Érdemjegy megállapítása

Nincs megadva érdemjegy határ.

Jelenléti és részvételi követelmények

Nincs megadva jelenléti követelmény.

Javítás, ismétlés és pótlás különös szabályai

Nincs megadva.

Rövid leírás

Nincs megadva.

Részletes leírás

Nincs megadva.

Ajánlott tantárgyak

Nincs megadva.

A tantárgy elvégzéséhez szükséges tanulmányi munka

Nincs megadva munkaidő bontás.

Tantárgykövetelmények hatályossága

Tantárgykövetelmények hatályosságának kezdete:

—

Tantárgykövetelmények hatályosságának vége:

—

Tantervi elhelyezés

Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.