Programming I - NPRG030

• Title: Programování I
• Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2008 to 2008
• Semester: winter
• E-Credits: 6
• Hours per week, examination: winter s.:3/2, C [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: RNDr. Tomáš Holan, Ph.D.; doc. RNDr. Pavel Töpfer, CSc.
• Class: Informatika Bc.
• Classification: Informatics > Programming
• Incompatibility : NPRM044
• Is co-requisite for: NPRG047
• Is incompatible with: NPRM045, NPRM044, NPRM001, NMUE021, NMUE022
• Is interchangeable with: NPRM044

Annotation

English

Last update: doc. RNDr. Pavel Töpfer, CSc. (09.10.2017)

Basic course of programming for students in the 1st year of study in study programs "Computer Science" and "Computer Science Education". The course includes basic algorithms and data structures, programming language, design of programs and practical programming.

Czech

Last update: doc. RNDr. Pavel Töpfer, CSc. (18.01.2018)

Základní kurs algoritmizace a programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Obsahem kursu jsou principy algoritmizace, základní algoritmy, datové struktury a programovací techniky, typické prostředky programovacích jazyků, praktický návrh a ladění programů.

Literature

Last update: doc. RNDr. Pavel Töpfer, CSc. (02.02.2018)

P. Töpfer: Algoritmy a programovací techniky, Prometheus 1995, 2. vyd. 2007

J. Drózd, R. Kryl: Začínáme s programováním, Grada 1992

N. Wirth: Algoritmy a štruktúry údajov, Alfa 1987

Syllabus

English

Last update: Adam Dingle, M.Sc. (07.10.2017)

1. Algorithms and data structures

Euklid's algorithm

Sieve of Eratosthenes

Horner's schema

searching in array (binary, sentinel)

heap operation

in-memory sorting, lower estimation of complexity in the worst case

(insertsort, selectsort, bubblesort, heapsort, radixsort, mergesort, quicksort)

long numbers

matrix operations

recursion, backtracking

minimax algorithm

breadth-first search

estimating the complexity of specific algorithms and programs

methods of variable storing (stack, heap)

singly-linked list

binary tree, balanced tree (AVL-tree)

multiway tree (B-tree)

external sorting

2. Programming language (Pascal and Turbo Pascal)

variable, constant, type, typed constants

numeric data types, char, boolean, enumerated and interval types

hierarchical structure of statements, program, elementar and structured statements

data structures (array, record, string)

procedures and functions, parameters, locality, recursion

input and output, text files

complete vs. short evaluation of boolean expresions

label, goto

dynamicaly allocated variables, pointers

2. Work on PC in Turbo Pascal

Turbo Pascal's IDE, debugging tools

Czech

Last update: doc. RNDr. Pavel Töpfer, CSc. (18.01.2018)

a) Základních algoritmy, datové struktury a programovací techniky

• základní představa o efektivitě algoritmů

• dělitelnost čísel, Eukleidův algoritmus

• test prvočíselnosti, Eratosthenovo síto

• Hornerovo schéma

• rozklad celého čísla na cifry, poziční číselné soustavy

• algoritmy vyhledávání v poli (sekvenční, binární, zarážka)

• řazení dat v poli (vnitřní třídění)

• práce s maticemi (základní operace)

• implementace zásobníku a fronty v poli

• aritmetika s vyšší přesností ("dlouhá čísla")

• použití rekurze, backtracking, metoda "rozděl a panuj"

• prohledávání do hloubky a do šířky

• algoritmus minimaxu

• halda a operace s haldou

• faktorová množina

• dynamické datové struktury, operace s lineárními spojovými seznamy

• binární stromy, vyhledávací stromy, vyvažování (AVL-stromy)

• vícecestné vyhledávací stromy (B-stromy)

• notace aritmetického výrazu, vyhodnocování

• vnější třídění

b) Typické prostředky a nástroje programovacích jazyků ukázané na příkladu programovacího jazyka Pascal (Turbo Pascal) v rozsahu

• proměnné, konstanty, typy, inicializované proměnné

• jednoduché a strukturované datové typy (čísla, char, boolean, výčtový typ, pole, záznam, znakový řetězec)

• jednoduché a strukturované příkazy (dosazovací příkaz, if, while, repeat, for, case, with)

• textové soubory (včetně formátování výstupních dat)

• procedury a funkce (lokalita identifikátorů, způsoby předávání parametrů, rekurze)

• příkazy skoku

• ukazatele a dynamicky alokované proměnné

• základní parametry překladače (paměťová omezení, přepínače provádění kontrol).

c) Práce v integrovaném vývojovém prostředí, tvorba a ladění programů - prakticky procvičena na příkladě integrovaného vývojového prostředí Turbo Pascal nebo Free Pascal (editor, překlad, výpočet, ladicí prostředky - trasování, sledování hodnot proměnných atd.).