inf_inz_2011-PytaniaZakreskrotkieOpracowanie.doc

PYTANIA NA EGZAMIN DYPLOMOWY, STUDIA I STOPNIA INŻYNIERSKIE, KIERUNEK INFORMATYKA, SPECJALNOŚĆ INŻYNIERIA SYSTEMÓW INFORMATYCZNYCH oraz INFORMATYKA OGÓLNA

(obowiązuje na egzaminie inżynierskim od lutego 2011)

1. Algorytm. Własności algorytmu. Prezentacja algorytmu.
2. Złożoność algorytmów.
3. Problemy sortowania. Przykłady algorytmów sortowania i ich złożoność.
4. Drzewa przeszukiwań binarnych. Sposób wykonywania na nich podstawowych operacji (dodawanie, wyszukiwanie, usuwanie).
5. Algorytmy przeszukiwania grafu.
6. Abstrakcyjne struktury danych: listy, kolejki, stosy. Ich implementacja komputerowa.
7. Zasada działania i sposoby implementacji tablic haszowanych.
8. Idea algorytmu zachłannego. Przykład.
9. Idea Dijkstry algorytmu znajdowania najkrótszej ścieżki.

10. Pozycyjne systemy liczbowe (binarny, dziesiętny, szesnastkowy). Prezentacja liczb w komputerze.

11. Budowa komputera
12. Struktura procesora.
13. Cykl rozkazowy procesora
14. Metody odwzorowania pamięci głównej w pamięci podręcznej.
15. Przetwarzanie potokowe.

16. Porównanie różnych architektur sieci komputerowych
17. Funkcje warstwy łącza danych modelu OSI.
18. Funkcje warstwy sieci modelu OSI.
19. Dynamiczne przydzielanie adresów.
20. Protokoły połączeniowe i bezpołączeniowe.
21. Tryby FTP.

22.  Podstawowe pojęcia baz danych. Baza Danych. Funkcje bazy danych. Właściwości bazy danych. Modele baz danych.

23.  System zarządzania bazami danych. Funkcje systemu. Przykłady SZDB.

24.  Model relacyjny baz danych. Relacje, klucze główne i obce, integralność referencyjna.

25.  Modelowanie  baz danych. Diagram związków encji.

26.  Język baz danych  SQL. Podjęzyki DDL, DML, DCL.

27.  Instrukcja SELECT.

28.  Instrukcje DDL i DCL.

29.  Indeksy w bazach danych, podział indeksów , B+-drzewo.

30.  Normalizacja., cel normalizacji, postać normalna Boyce'a-Codda.

31.  Transakcje, własności transakcji.

32.  Diody półprzewodnikowe. Tranzystory.

33.  Układy scalone.

34.  Układy impulsowe.

35.  Układy cyfrowe.

36.  Pamięci półprzewodnikowe, magnetyczne, optyczne.

37.  Przetworniki analogowo-cyfrowe i cyfrowo-analogowe.

38.  Metody pomiarów wielkości elektrycznych.

39. Metody pomiarów wielkości nieelektrycznych.

40.  Generatory kwarcowe – czas i częstotliwość w komputerze

41. Grafy. Grafy eulerowskie i  hamiltonowskie.
42. Kolorowanie grafów, definicja liczby chromatycznej grafu i indeksu chromatycznego.
43. Ciąg Fibonacciego. Definicja rekurencyjna i wzór ogólny.
44. Grafy planarne.
45. Drzewa spinające grafu. Minimalne drzewa spinające.

46. Typy zmiennych. Podział. Przykłady w wybranym języku programowania.
47. Rodzaje pętli. Uwarunkowanie zastosowań. Problem równoważności pętli w wybranym języku programowania.
48. Zmienne typu adresowego (wskaźniki). Implementacja w wybranym języku programowania.
49. Funkcje (z wzmianką o procedurach). Przekazywanie parametrów przez wartość i referencję lub adres.
50. Cechy programowania strukturalnego. Kluczowe różnice między programowaniem strukturalnym a obiektowym.

51. Zalety języków programowania obiektowo orientowanych. Składniki klasy. Konstruktory i destruktory. Podać przykłady.
52. Zastosowanie składników statycznych w klasie. Statyczne funkcje składowe. Podać przykłady.
53. Dziedziczenie. Dostęp do składników klasy.  Kolejność wywołania konstruktorów. Przypisanie i inicjalizacja obiektów w warunkach dziedziczenia.
54. Polimorfizm. Deklarowanie funkcji wirtualnych. Mechanizm wywołania. Podać przykłady.
55. Definiowanie szablonu klasy. Korzystanie z szablonu.

56. Cykl pracy procesora przy wykonaniu programu.
57. Procesy, zarządzanie procesami.
58. Metody przydziału pamięci operacyjnej procesowi. Organizacja pamięci wirtualnej.
59. Funkcje systemowe – podstawowe kategorie, przykłady.
60. Szeregowanie procesów. Wybrane algorytmy szeregowania.
61. Synchronizacja procesów współbieżnych. Semafory.

62. Cykle projektowania i życia oprogramowania.
63. Klasyfikacja  narzędzi wspierających wytwarzanie oprogramowania.
64. Metody oraz  strategie testowania oprogramowania.
65. Instalacja i konserwacja oprogramowania.
66. Zagadnienia etyczne i prawne związane z procesem wytwarzania i użytkowania oprogramowania.

67. Etapy cyklu  życia systemu informatycznego i ich charakterystyka
68. Modele organizacyjne wytwarzania systemów informatycznych i ich charakterystyka – zalety i wady.
69. Istota i znaczenie fazy strategicznej  w realizacji przedsięwzięć informatycznych.
70. Metody identyfikacji wymagań na systemy informatyczne  i  ich charakterystyka.
71. Znaczenie modelowania obiektowego funkcjonowania informatyzowanej organizacji  w ustalaniu wymagań na system informatyczny.
72. Pożądana zawartość dokumentu „Wymagania na system informatyczny”.
73. Podstawowe rezultaty fazy modelowania systemu.
74. Podstawowe zadania realizowane w procesie budowy obiektowego  modelu systemu informatycznego.
75. Rodzaje modyfikacji wprowadzanych w fazie pielęgnacji systemu informatycznego.

76. Działania na zbiorach.
77. Rachunek zdań.
78. Działania na macierzach.
79. Układy równań liniowych – twierdzenie Kroneckera-Capelliego, wzory Cramera.
80. Pojęcie relacji i funkcji.
81. Własności relacji: relacje porządkujące; relacje równoważności.
82. Własności funkcji: miejsca zerowe, ciągłość, pochodna.
83. Zmienna losowa i jej charakterystyki liczbowe.

84. Cel i rodzaje programowania deklaratywnego.
85. Definicje unifikatora (podstawienia uzgadniającego), najogólniejszego unifikatora, algorytm unifikacji i twierdzenie o unifikacji.
86. Programy Horna, SLD-rezolucja, odpowiedzi poprawne, odpowiedzi obliczone, poprawność i zupełność SLD-rezolucji.
87. Zasada rezolucji liniowej w programowaniu w logice.
88. Budowa programu w Prologu: klauzule (fakty, reguły), definicje predykatów. Sposób realizacji programu.

89. Co to są systemy (zestawy) funkcjonalnie pełne? Podać przykładowe.
90. Podaj rodzaje układów sekwencyjnych oraz różnice w procedurach ich projektowania.
91. Jakie znasz elementy pamięciowe stosowane układach sekwencyjnych?
92. Co oznacza termin mikroprogramowanie? Do czego służy?
93. Podaj znane zapisy liczbowe i zakres ich stosowania.

94. Co to są mikrokontrolery?
95. Jakie parametry są charakterystyczne dla pamięci dynamicznych?
96. Podaj tryby adresowania dla rozkazów mikrokontrolera i odpowiadający im czas trwania cyklu instrukcyjnego wraz z omówieniem kolejnych cykli maszynowych.
97. Jakie znasz rodzaje transmisji szeregowej i na czym one polegają?
98. Porównaj pod względem szybkości znane rozwiązania operacji mnożenia w systemach wbudowanych.

99. Model obliczeniowy perceptronu – możliwości i ograniczenia.
100. Metody uczenia sieci neuronowych.
101. Mechanizm działania algorytmu genetycznego.
102. Definicja entropii informacji i wybrane zastosowanie tego pojęcia.
103. Metody generacji reguł systemu decyzyjnego, minimalne, pokrywające, wyczerpujące.

104. Podaj znaczenie oraz omów wzajemne związki między terminami:  przestrzeń urządzenia, przestrzeń operacyjna urządzenia, powierzchnia obrazowania, macierz adresowalna, jednostka rastru, krok kreślaka.
105. Zdefiniuj okno i widok oraz oknowanie i obcinanie; podaj co to są współrzędne znormalizowane i do czego one służą.
106. Podaj ideę algorytmu Cohena-Sutherlanda obcinania odcinka do prostokątnego okna i jego trzy pierwsze kroki; podaj w jakich współrzędnych działa ten algorytm i dlaczego?
107. Sformułuj zadanie i ogólne warunki trójkątowania wielokąta, warunki trójkątowania naturalnego oraz podaj ideę trójkątowania wielokąta monotonicznego.

108.    Zdefiniuj przekształcenie 3-punktowe. Do czego ono służy?.

109. Podaj wzajemne położenie układów współrzędnych: danych i obserwatora.
110. Wymień we właściwej kolejności operacje, jakie należy wykonać, aby obrócić punkt P o kąt   dookoła prostej zadanej przez dwa punkty    i  .

111. Opisać 3 podstawowe obszary uzależnień komputerowych.
112. Wymienić przynajmniej 3 polskie ustawy dotyczące środowiska informatycznego.
113. Jaka jest zasadnicza różnica między ochroną własności intelektualnej i ochroną patentową?
114. Opisać na czym polega szpiegostwo komputerowe.

UWAGI. 

1)     Zakresy pytań: 1 – 9 algorytmy i struktury danych;  10 uniwersalne;  11 – 15 architektura i organizacja komputerów;  16 – 21 sieci komputerowe;  22 – 31 bazy danych;  32 – 40 podstawy elektroniki i miernictwo elektroniczne;  41 – 45 matematyka dyskretna; 46 – 50 programowanie strukturalne;  51 – 55 programowanie obiektowe;  56 – 61 systemy operacyjne;  62 – 66 inżynieria oprogramowania; 67 – 75 projektowanie systemów informatycznych;  76 – 83 podstawy logiki i teorii mnogości, algebra liniowa, analiza matematyczna, metody probabilistyczne;  84 – 88 programowanie deklaratywne – paradygmaty programowania;  89 – 93 technika cyfrowa;  94 – 98 systemy wbudowane;  99 – 103 sztuczna inteligencja;  104 – 110 wprowadzenie do grafiki maszynowej;  111 – 114 problemy społeczne i zawodowe informatyki.

2)     Przykładowe szkice odpowiedzi podane przez Pana Doktora inż. Andrzeja Skorupskiego:

Ad. 89:  Systemem funkcjonalnie pełnym nazywa się taki zbiór operatorów (funkcji), którymi można przedstawić dowolne wyrażenie logiczne (dowolną funkcję).

Przykłady: 1. Suma, iloczyn, negacja,  2. NAND,  3. NOR,  4. iloczyn, XOR, 1

Ad. 90:  Układy synchroniczne i asynchroniczne. Różnice projektowania polegają na konieczności eliminacji zjawisk szkodliwych w układach asynchronicznych, tj.               wyścigów i hazardów.

Ad. 91:  Układy synchroniczne projektuje się z przerzutników typu D, T i JK. Układy asynchroniczne projektuje się z przerzutników RS lub bez przerzutników (bramki ze sprzężeniem zwrotnym).

Ad. 92:  Układ mikroprogramowany to jedno z możliwych rozwiązań stosowanych w technice cyfrowej dla projektów o dużej złożoności. Projekt dekomponowany jest na dwie części: układ operacyjny (wykonawczy) i układ sterujący. Układ sterujący można zaprojektować jako układ mikroprogramowany. Bity sterujące, wraz z innymi odpowiednimi bitami służącymi do napisania mikroprogramu, umieszcza się w pamięci ROM.

Ad. 93:  Zapisy można podzielić na stałopozycyjne (liczby całkowite) i zmiennopozycyjne (liczby rzeczywiste). Stałopozycyjne to: ZNAK-MODUŁ, U1 i U2. Najpowszechniejszy jest U2 ze względu na najprostsze algorytmy operacji arytmetycznych. Zmiennopozycyjny zapis polega na reprezentowaniu liczby za pomocą trzech grup bitów: jednobitowej grupy znaku, np. 63-bitowej mantysy i np. 16-bitowego wykładnika.

Ad. 94:  Mikrokontrolery są to systemy mikroprocesorowe (mikroprocesor, pamięć ROM i RAM, sterowniki urządzeń zewnętrznych itp.) wykonane w jednej obudowie jako układ scalony. Z nietypowych dla komputerów urządzeń są wyposażane w konwertery A/C i C/A, sterowniki silnika krokowego, liczniki itp.

Ad. 95:  Oprócz parametrów typowych jak np. pojemność, czas cyklu (dostępu), pobór mocy, koszt itp. pamięć dynamiczna posiada charakterystyczne dla niej parametry, tj. wymagany czas odświeżania (8-64 ms) i wymaganą liczbę cykli odświeżania (pierwiastek z liczby bitów).

Ad. 96:  Cztery proste tryby: rejestrowy (1 cykl maszynowy), natychmiastowy (2 cykle), pośredni rejestrowy (2 cykle) i bezpośredni (4 cykle). Złożonym trybem jest np. tryb indeksowy.

Ad. 97:  Transmisja asynchroniczna (w nadajniku i odbiorniku zegary nastawione na tą samą częstotliwość) pozwalająca na transmisję 1 bajtu z parametrami (bit staru, bit stopu, bit parzystości itp.). Transmisja synchroniczna, gdzie zegar przesyłany jest oddzielnym przewodem (to niemożliwe w istniejących sieciach) lub jest zakodowany razem z ciągiem bitów stanowiących informację (np. kod Manchester).

Ad. 98:  Mnożenie w układzie kombinacyjnym (układ iteracyjny gdzie wynik pojawia się po czasie opóźnienia wnoszonym przez bramki) jest najszybsze. Mnożenie w układzie sekwencyjnym (tyle kroków ile jest bitów, a każdy krok to dodawanie warunkowe i przesunięcie) jest wolniejsze. Mnożenie programowe (bez żadnego sprzętu) jest najwolniejsze.