Základy programování II - MC260P26

• Anglický název: Computer programming fundamentals II
• Český název: Základy programování II
• Zajišťuje: Katedra fyzikální a makromol. chemie (31-260)
• Fakulta: Přírodovědecká fakulta
• Platnost: od 2023
• Semestr: letní
• E-Kredity: 3
• Způsob provedení zkoušky: letní s.:
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: 16
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: čeština
• Vysvětlení: nedojde-li k jine dohode, kurz probiha pouze v letech x, kde (x+1) mod 3=0
• Poznámka: povolen pro zápis po webu
• Garant: doc. RNDr. Filip Uhlík, Ph.D.

Anotace

čeština

Poslední úprava: doc. RNDr. Filip Uhlík, Ph.D. (05.04.2016)

Tato přednáška pokrývá základní datové struktury (například seznamy a stromy), algoritmy a jejich analýzu (například vyhledávání, třídění a grafové algoritmy). Obecné programovací techniky (například "rozděl a panuj" a "dynamické programování") jsou také diskutovány. Tato přednáška je volným pokračováním přednášky Základy programování I. Příklady jsou v programovacím jazyce C.

V případě, že se předmět nevyučuje, neváhejte a zapište si Programování pro informatiky na MFF.

angličtina

Poslední úprava: ZUSKOVA (29.01.2003)

Computer programming fundamentals II

This lecture covers basic data structures (e. g., lists and trees), algorithms and their analysis (e. g., searching, sorting and graph algorithms). General programming techniques (e. g., "divide and conquer" and "dynamical programming") are also discussed. This lecture is a loose continuation of Computer Programming I. Examples are given in the C programming language.

Literatura

čeština

Poslední úprava: ZUSKOVA (29.01.2003)

D. E. Knuth: The Art of Computer Programming, Addison-Wesley, 1969.

angličtina

Poslední úprava: doc. RNDr. Filip Uhlík, Ph.D. (07.06.2019)

D. E. Knuth: The Art of Computer Programming, Addison-Wesley, 1969.

Požadavky ke zkoušce

čeština

Poslední úprava: doc. RNDr. Filip Uhlík, Ph.D. (15.10.2020)

Zkouška se skládá z písemné části, kdy student napíše program řešící dohodnutou úlohu a ústní části, kdy se zkoušejícím řeší jeho správnost a případné úpravy. Bude-li to nutné, budou kurz a zkouška distační.

angličtina

Poslední úprava: doc. RNDr. Filip Uhlík, Ph.D. (15.10.2020)

Exam consists in two parts, a written one when student creates a program for an agreed problem and an oral one when students defends its correctness and eventual changes. If necessary, the couse and the exam will have a distant form.

Sylabus

čeština

Poslední úprava: doc. RNDr. Filip Uhlík, Ph.D. (07.06.2019)

Algoritmus a jeho složitost

co je to algoritmus? časová a prostorová složitost, asymptotická složitost a notace s velkým O

Základní datové struktury a algoritmy

sequential allocation, linked allocation, zásobník (stack), fronta (queue), stromy, halda (heap)

Rozděl a panuj (Divide and Conquer)

Dynamické programování

Vyhledávání (Searching)

sekvenční vyhledávání, binární vyhledávání, binární vyhledávací stromy, AVL stromy, 2-3 stromy, B-stromy, hashing, externí vyhledávání

Třídění (Sorting)

insert a select sort, quick, heap a merge sort, externí třídění

Grafové algoritmy

průchod grafem, komponenty grafu, nejkratší cesta v grafu, minimální kostra grafu

angličtina

Poslední úprava: doc. RNDr. Filip Uhlík, Ph.D. (07.06.2019)

Algorithms and complexity

what is an algorithm? time and space complexity, asymptotic complexity and big O notation

Basic data structures and algorithms

sequential allocation, linked allocation, stack, queue, trees, heap

Divide and Conquer

Dynamic programing

Searching

sequential searching, binary searching, binary searching trees, AVL trees, 2-3 trees, B-trees, hashing, external searching

Sorting

insert and select sort, quick, heap and merge sort, external sorting

Graph algorithms

graph traversal, graph components, shortest path, minimal spanning tree