Wstęp do programowania: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 1: | Linia 1: | ||
== Forma zajęć == | == Forma zajęć == | ||
Wykład (30 godzin) + | Wykład (30 godzin) + ćwiczenia (30 godzin) | ||
== Opis == | == Opis == | ||
Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych. | Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych. | ||
Wersja z 07:56, 15 cze 2006
Forma zajęć
Wykład (30 godzin) + ćwiczenia (30 godzin)
Opis
Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych.
Sylabus
Autor
- Piotr Chrząstowski-Wachtel
Wymagania wstępne
- brak
Zawartość
- Pojęcie algorytmu
- Historia powstania pojęcia algorytmu
- Algorytmy znane ze szkoły (Euklidesa, Hornera, rozwiązywanie równań liniowych i kwadratowych)
- Języki formalne
- Alfabet, składnia i semantyka
- Gramatyki bezkontekstowe, jako narzędzie definiowania składni
- Definicja semantyki przez interpretację wyrażeń poprawnych składniowo
- Reprezentacja liczb w komputerze
- Stałe całkowite i rzeczywiste
- Reprezentacje binarne stało- i zmiennopozycyjne
- Systemy znak-moduł i uzupełnieniowy
- Rachunek zmiennopozycyjny - pojęcie zakresu, błędu zaokrągleń
- Zmienne i wyrażenia
- Typ zmiennej i wartościowanie zmiennych
- Wyrażenia arytmetyczne i logiczne: składnia i semantyka
- Instrukcje while-programów
- pusta, przypisania, warunkowa, iteracji, wyboru, czytania, pisania, wywołania procedury
- Składnia i semantyka powyższych instrukcji
- Obliczenia skończone i nieskończone
- Błędy obliczeń
- Przykłady algorytmów
- Asercje w programach i niezmienniki pętli
- Formuły Hoare'a
- Uzasadnianie poprawności programów
- Własność stopu i metody jej dowodzenia
- Typy danych
- tablice
- rekordy
- zbiory
- pliki
- typy wyliczeniowe i okrojone
- typy wskaźnikowe
- Pliki
- pliki o dostępie bezpośrednim
- pliki tekstowe
- Funkcje i procedury
- Składnia i semantyka
- Sposoby przekazywania parametrów: przez wartość i przez zmienną
- Widoczność zmiennych w zagnieżdżonych procedurach
- Miary złożoności algorytmów
- Koszty algorytmu czasowy i pamięciowy, pesymistyczny i średni
- Rozmiar danych
- Przykłady wyznaczania kosztów.
- Koszt zamortyzowany
Literatura
- Wstęp do programowania systematycznego, N.Wirth, Wydawnictwa Naukowo - Techniczne 1999.
- Elementy analizy algorytmów, L. Banachowski, A.Kreczmar, Wydawnictwa Naukowo - Techniczne 1987
- Projektowanie programów poprawnych i dobrze zbudowanych', S.Alagić, M.Arbib, Wydawnictwa Naukowo - Techniczne 1982
