Wstęp do programowania (podejście imperatywne)
Informacje ogólne
Kod przedmiotu: | 1000-211aWPI |
Kod Erasmus / ISCED: |
11.301
|
Nazwa przedmiotu: | Wstęp do programowania (podejście imperatywne) |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: | |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | polski |
Rodzaj przedmiotu: | obowiązkowe |
Skrócony opis: |
Podstawowy przedmiot pierwszego semestru studiów, mający zapoznać studentów z pojęciem algorytmu. Celem zajęć jest nauczenie projektowania, zapisywania, dowodzenia poprawności i analizowania złożoności algorytmów. Uwagi: Następny przedmiot w serii: Metody programowania. |
Pełny opis: |
1.Historia powstania pojęcia algorytmu. Algorytmy znane ze szkoły (Euklidesa, Hornera, rozwiązywanie równań liniowych i kwadratowych). 2.Historia powstania komputera. 3.Język formalny: alfabet, składnia i semantyka. Gramatyki bezkontekstowe, jako narzędzie definiowania składni. Definicja semantyki przez interpretację wyrażeń poprawnych składniowo. 4.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ń. 5.Zmienne i wyrażenia. Typ zmiennej i wartościowanie zmiennych. Wyrażenia arytmetyczne i logiczne: składnia i semantyka. 6.Instrukcje: pusta, przypisania, warunkowa, iteracji, wyboru, czytania, pisania, wywołania procedury. Składnia i semantyka. Obliczenia skończone i nieskończone. Błędy obliczeń. Przykłady algorytmów. 7.Typy danych: tablice, rekordy, zbiory, pliki, typy wyliczeniowe i okrojone. 8.Pliki o dostępie bezpośrednim i pliki tekstowe. 9.Funkcje i procedury. Składnia i semantylka. Sposoby przekazywania parametrów: przez wartość i przez zmienną. Widoczność zmiennych w zagnieżdżonych procedurach. 10.Częściowa i całkowita poprawność programów. Elementy logiki Hoare'a. Niezmienniki iteracji. Dowodzenie poprawności algorytmów. Własność stopu. Metoda zbiorów dobrze ufundowanych. 11.Koszty algorytmu czasowy i pamięciowy, pesymistyczny i średni. Rozmiar danych. Przykłady wyznaczania kosztów. Koszt zamortyzowany. |
Literatura: |
1.Wstęp do programowania systematycznego, N.Wirth, WNT 1999. 2.Elementy analizy algorytmów, L. Banachowski, A.Kreczmar, WNT 1987 3.Algorytmika, rzecz o istocie informatyki, D. Harel, WNT 2001. 4.Projektowanie programów poprawnych i dobrze zbudowanych, S.Alagić, M.Arbib, WNT 1982 |
Właścicielem praw autorskich jest Uniwersytet Warszawski.