Serwisy internetowe Uniwersytetu Warszawskiego Nie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Wstęp do programowania (podejście imperatywne)

Informacje ogólne

Kod przedmiotu: 1000-211aWPI Kod Erasmus / ISCED: 11.301 / (0612) Database and network design and administration
Nazwa przedmiotu: Wstęp do programowania (podejście imperatywne)
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy:
Punkty ECTS i inne: (brak)
zobacz reguły punktacji
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

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.