Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Podstawy informatyki
Koordynator przedmiotu:
dr inż. Jarosław Szostakowski, jaroslaw.szostakowski@ee.pw.edu.pl, +48222347320
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
1 / rok ak. 2011/2012
Liczba punktów ECTS:
6
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Brak
Limit liczby studentów:
Cel przedmiotu:
Znajomość podstaw teoretycznych niezbędnych do studiowania informatyki
Treści kształcenia:
Wykład 1. Wprowadzenie (Łańcuch, alfabety i języki. Grafy i drzewa. Dowody przez indukcje. Oznaczenia dla zbiorów. Relacje.) 2. Automaty skończone i wyrażenia regularne (Systemy skończone stanowe. Podstawowe definicje. Niedeterministyczne automaty skończone. Wyrażenia regularne. Zastosowanie automatów skończonych: analizatory leksykalne, edytory tekstu). 3. Gramtyki bezkontekstowe (Wprowadzenie. Definicja. Wyprowadzenia i języki. Drzewa wyprowadzenia.) 4. Automaty ze stosem (Wprowadzenie. Definicje – ruchy, języki akceptowane.) 5. Maszyny Turinga (Wprowadzenie. Model maszyny Turinga. Języki i funkcje obliczalne. Techniki konstruowania maszyn Turinga, Modyfikacje maszyny Turinga. Maszyny Turinga jako generatory). 6. Nierozstrzygalność (Problemy rozstrzygalne i nierozstrzygalne. Własności języków rekurencyjnych i rekurencyjnie przeliczalnych. Uniwersalne maszyny Turinga i problem nierozstrzygalny. Kody maszyn Turinga. Język uniwersalny. Nierozstrzygalność problemu odpowiedniości posta) 7. Hierachia Chomsky’ego Gramatyka regularna. Gramtayki nieograniczone. Języki kontekstowe. 8. Teoria złożoności obliczeniowej (Definicje, Złożoność pamięciowa, Złożoność czasowa, Klasy złożoności. Redukcja złożoności: Przyspieszenie liniowe. Kompresja taśmy. Zmniejszenie liczby taśm.) 9. Problemy niepodatne (Wielomianowy czas i pamięć: Wprowadzenie, Ograniczone redukowalności, Problemy zupełne. Przykład problemu NP-zupełnego: spełnialność). Laboratorium 1. Zajęcia organizacyjne. Zasoby sieci uczelnianej. Informacja o programie i metodyce prowadzenia zajęć laboratorium Teoretycznych Podstaw Informatyki. Informacja o zasobach sieci uczelnianej. 2. System operacyjny UNIX – wyrażenia regularne. 3. Język programowania Pascal – jako narzędzie zapisu algorytmów. Typy operatory i wyrażenia. Sterowanie. Tablice, rekordy i zbiory. Procedury i funkcje. Wskaźniki. Elementy pseudografiki. 4. Automaty skończone. Emulacja działania prostego automatu skończonego 5. Gramatyki bezkontekstowe. Generowanie łańcuchów opisanych za pomocą danej gramatyki 6. Maszyna Turinga. Emulacja działania maszyny Turinga. 7. Rezerwowy termin odrabiania zajęć
Metody oceny:
brak
Egzamin:
Literatura:
1. J. E. Hopcroft, J. D. Ullman Wprowadzenie do teorii automatów, języków i obliczeń. Wydawnictwo Naukowe PWN, 2005.; 2. A. V. Aho, J. D. Ullman Wykłady z informatyki z przykładami w języku C. Helion, 2003.
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się