wyklad1

wyklad1,

[ Pobierz całość w formacie PDF ]
O czym będziemy mówić
●
czym jest/czym zajmuje się informatyka?
●
nieco historii – „
od liczydła do iPod'a
”
Wstęp do informatyki
●
architektura komputerów
●
systemy operacyjne
●
języki programowania
●
narzędzia programistyczne
Wiesław Pawłowski
●
...
Wstęp do informatyki
1
Wstęp do informatyki
2
Czym jest informatyka ?
Czym jest informatyka ?
●
pojęcie informatyki jest tak obszerne, a jej
zastosowania tak różnorodne, że
trudno o zwięzłą
odpowiedź
●
nauką o komputerach (??)
–
nie obejmuje (bardzo ważnych) prac teoretycznych,
które nie używają prawdziwych komputerów, a jedynie
ich formalnych modeli
–
spora część codziennej pracy informatyków odbywa się
przy pomocy kartki i ołówka (tak, tak!!!)
–
informatyka pojawiła się wcześniej niż same komputery
–
informatyka mówi o komputerach w stopniu nie
większym niż astronomia o teleskopach, czy chemia o
probówkach – nie chodzi o narzędzie, ale o to jak i do
czego możemy je użyć
●
w bardzo dużym stopniu zależeć ona będzie od
tego, kogo zapytamy...
●
jako przyszli „
zawodowcy”
przyjrzymy się
zagadnieniu „
od podstaw
”
Wstęp do informatyki
3
Wstęp do informatyki
4
        Czym jest informatyka ?
Czym zajmuje się informatyka ?
●
nauką o programowaniu (??)
●
jako nauka
–
programowanie jest ważną, ale nie najważniejszą
częścią informatyki
●
nauką o użytkowaniu i zastosowaniach
komputerów i programów (??)
–
problemami przechowywania, przesyłania,
przetwarzania i interpretowania informacji
–
systematycznym badaniem, analizą i
projektowaniem procesów
algorytmicznych
●
jako inżynieria
–
nauka użytkowania komputerów i oprogramowania ma
się tak do informatyki jak kurs prawa jazdy do
inżynierii motoryzacyjnej
–
informatyka odpowiedzialna jest za projektowanie i
konstruowanie oprogramowania
–
implementacją i zastosowaniami procesów
algorytmicznych
Wstęp do informatyki
5
Wstęp do informatyki
6
Algorytm - co to takiego ?
U podstaw informatyki leży pojęcie
algorytmu
algorytm
- przepis postępowania prowadzący do
rozwiązania określonego zadania; zbiór poleceń
dotyczących pewnych obiektów (danych) — ze
wskazaniem kolejności, w jakiej mają być
wykonane; wykonawcą jest układ, który na sygnały
reprezentujące polecenia reaguje ich
realizowaniem — może nim być człowiek lub
urządzenie automatyczne, np. komputer.
[...]
[Encyklopedia PWN]
Wstęp do informatyki
7
Wstęp do informatyki
8
        Algorytm – najważniejsze cechy
Przykłady
●
precyzyjnie i jednoznacznie
zdefiniowany ciąg
czynności (
operacji
)
●
problem
: znajdź i wydrukuj setną w kolejności
liczbę pierwszą
●
ciąg operacji musi być
skończony
●
algorytm (??)
:
●
każda z operacji wchodzących w jego skład musi
być „
obliczalna
” (dać się wykonać)
1. sporządź listę wszystkich liczb pierwszych
2. uporządkuj je w kolejności rosnącej
3. wydrukuj setny element listy
czy jest to algorytm?
●
algorytm musi dawać wynik w
skończonej liczbie
kroków
(zastosowań operacji)
NIE
– operacje 1 oraz 2
nie są efektywnie obliczalne
!
Wstęp do informatyki
9
Wstęp do informatyki
10
Przykłady
Przykłady algorytmów
●
problem
: mycie włosów
●
Euklides
,
400-300 r. p.n.e.
●
algorytm (??)
:
–
algorytm obliczania NWD
●
Muhammad al-Khwarizmi
, IX w. n.e.
1. zwilż włosy wodą
2. użyj szamponu
3. spłucz włosy wodą
4. powtórz czynności 2-4
czy jest to algorytm?
–
algorytmy dodawania, odejmowania, mnożenia
i dzielenia liczb dziesiętnych
●
Król Edward VIII
, lata 30-te XX w.
–
algorytm wiązania krawata „
windsor”
NIE
– mycie włosów nigdy
nie dobiegnie końca
Wstęp do informatyki
11
Wstęp do informatyki
12
        Problemy algorytmiczne
Czy wszystko da się obliczyć?
Poprawne
dane wejściowe
●
„
Własność stopu
”
Specyfikacja poprawnych
danych wejściowych
–
dane wejściowe
●
opis ciągu czynności
A
(„program”)
●
dane wejściowe
D
–
pytanie (wynik)
●
czy „wykonanie”
A
dla danych
D
zakończy się
w skończonej liczbie kroków?
●
Problem „decyzyjny”
: czy istnieje algorytm
testujący własność stopu dla dowolnych
A
i
D
?
+
?
Algorytm
Definicja oczekiwanych
wyników
jako
funkcji
danych wejściowych
Spodziewany
wynik
Problem algorytmiczny
Rozwiązanie
Wstęp do informatyki
13
Wstęp do informatyki
14
Czy wszystko da się obliczyć?
Własność stopu c.d.
●
Załóżmy, że istnieje algorytm
S
, który dla
dowolnego programu
A
i danych
D
zwraca:
T(P) :=
if
S(P,P)=1
then
pętla
else
stop
fi
–
1
jeżeli
A
zatrzymuje się dla danych
D
, oraz
–
0
w przeciwnym razie.
●
Niech
●
Załóżmy, że
S
(T,T)
=1 wówczas...
S(T,T) = 0
T(P) :=
if
S(P,P)=1
then
pętla
else
stop
fi
●
Załóżmy więc, że
S
(T,T)
=0 wówczas...
●
Jaką wartość zwróci
S
(T,T)
?
S(T,T) = 1
!
W obu przypadkach – sprzeczność z założeniem
!
Wstęp do informatyki
15
Wstęp do informatyki
16
        Nie wszystko da się obliczyć
Weryfikacja programów
jest
nierozstrzygalna
●
Wniosek:
1. Program
A
2. Problem algorytmiczny
P
–
Nie istnieje
algorytm pozwalający rozstrzygać
własność
stopu
●
Istnieje wiele problemów
nierozstrzygalnych
(
nieobliczalnych
) tzn. takich, dla których nie
istnieją rozwiązujące je algorytmy
Weryfikator
programów
Tak
, jeśli program
A
rozwiązuje problem
P
Nie
, jeśli program
A
nie
rozwiązuje problemu
P
Wstęp do informatyki
17
Wstęp do informatyki
18
Problemy, algorytmy i programy
Obliczenia są ...
nieobliczalne
Problem
Twierdzenie
[Rice, 1953]
:
Jeśli własność
W
Algorytm
...
Algorytm
–
nie jest własnością wszystkich programów
–
nie zależy od składni (jest własnością algorytmu)
wówczas
W
jest nierozstrzygalna.
Program
...
...
Program
Program
Program
Wstęp do informatyki
19
Wstęp do informatyki
20
         [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

cukierek.xlx.pl

wyklad1

Tematy

wyklad1,