4962385645

Wykład ze Wstępu do Informatyki

Rok 2015-2016 Marek Zawadowski

Wydział Matematyki, Informatyki i Mechaniki Uniwersytet Warszawski

31 maja 2015

Spis treści

1    Wstęp    3

1.1    Literatura................................. 3

1.2    Zaliczenie i egzamin ........................... 3

1.3    Historia Informatyki........................... 3

2    Wprowadzenie    4

2.1    Algorytm Euklidesa ........................... 4

2.2    Problem algorytmiczny.......................... 4

2.3    Sortowanie liczb.............................. 5

2.4    Analiza złożoności algorytmu...................... 5

2.5    Wieże Hanoi................................ 7

2.6    Wyszukiwanie słowa w słowniku..................... 7

2.7    Tablice rzeczywistego czasu działania algorytmów........... 8

2.8    Komputer od środka........................... 9

3    Język Pascal    11

3.1    Języki programowania wysokiego poziomu............... 11

3.2    Diagramy składniowe........................... 11

3.3    Formalna definicja języka imperatywnego ............... 12

3.4    Zmienne.................................. 13

3.5    Typy proste................................ 14

3.6    Typy strukturalne ............................ 15

3.7    Przegląd instrukcji języka Pascal.................... 16

3.8    Procedury................................. 22

3.9    Procedury rekurencyjne......................... 26

3.10    Poprawność programów ......................... 30

4    Podstawowe metody programowania    32

4.1    Metoda powrotów (prób i błędów) ................... 32

4.2    Metoda ’dziel i rządź’ .......................... 36

4.3    Sortowanie przy pomocy porównań................... 39

4.4    Programowanie dynamiczne....................... 41

1