Podstawy programowania
(1)
dr Jerzy Bartoszek
jerzy.bartoszek@put.poznan.p
l
Opis przedmiotu
Cele:
• Podstawowym celem przedmiotu jest nauczenie studentów budowania
algorytmów i programowania w języku imperatywnym wyższego rzędu.
Studenci zapoznają się z podstawowymi cechami algorytmów, strukturami
danych, instrukcjami, elementarną analizą programów, ich kompilowaniem i
testowaniem.
Opis przedmiotu:
• Wykład. Algorytmy i ich cechy. Podstawowe konstrukcje programistyczne:
zmienne; stałe; typy danych: typy proste, tablice jedno- i wielowymiarowe,
struktury, referencje; pliki; instrukcje: podstawienia, warunkowe, pętli;
procedury i funkcje oraz ich parametry; rekursja; moduły; biblioteki;
przestrzenie nazw. Obsługa zdarzeń i wyjątków. Podstawowe komponenty
interfejsu z użytkownikiem. Zasady programowania strukturalnego. Etapy
kompilacji. Elementy analizy poprawności programów i ich efektywności.
• Laboratorium. Składowe środowiska programowania. Tworzenie programów
wykorzystujących proste typy danych i podstawowe instrukcji
programistycznych (instrukcje podstawienia, warunkowe, pętle, konsolowe
operacje wejścia/wyjścia). Tworzenie programów zawierających typy złożone
(tablice jedno i dwuwymiarowych, struktury). Tworzenie programów z
procedurami, funkcjami, modułami i obsługą wyjątków. Tworzenie prostego
interfejsu z użytkownikiem i obsługiwanie zdarzeń. Śledzenie wykonywania
programów.
Opis przedmiotu cd.
Forma prowadzenia zajęć:
•
Wykład wykorzystujący środki multimedialne oraz
laboratorium.
Metody oceny:
•
Zaliczenie wykładu w formie egzaminu pisemnego,
zaliczenie laboratorium – sprawdziany i projekty
programistyczne.
Bibliografia:
1.
N. Wirth, Algorytmy+struktury danych=programy, WNT
Warszawa 1980 (i późniejsze)
2.
N. Wirth, Wstęp do programowania systematycznego, WNT
Warszawa 1978
3.
H. Gantenbein i inni, Microsoft Visual Basic .NET 2003.
Księga eksperta, Wydawnictwo Helion, 2006
4.
M. Szeliga, Visual Basic .NET : ćwiczenia, Wydawnictwo
Helion, 2004
Algorytm
Algorytm
to jednoznaczny, dobrze określony
przepis rozwiązania
dowolnego zadania
z pewnej klasy zadań
.
• składa się z kroków,
• wykorzystuje dane wejściowe,
• wytwarza wyniki,
• jest dobrze określony,
• jest skończony,
• jest wykonywalny.
Złożoność obliczeniowa
algorytmów
Czas wykonywania algorytmu wyrażony jako
funkcja rozmiaru zadania (liczby danych), to
złożoność czasowa
.
• logarytmiczna O(log n)
• liniowa O(n)
• kwadratowa O(n
2
)
• wielomianowa O(n
k
) , k>2
• wykładnicza O(2
n
) lub O(n!).
Porównanie czasów
wykonywania algorytmów
Porównano w niej czasy wykonywania
algorytmu na dwóch komputerach, w
których każda operacja jednostkowa
zajmuje, odpowiednio, 10
-6
s i 10
-9
s.
Porównanie czasów
wykonywania algorytmów
Rozmiar
20
50
100
200
Czas
działani
a(2
n
/10
6
)
1,04s
35,7 lat 4 * 10
14
wieków
5 * 10
44
wieków
Czas
działani
a(2
n
/10
9
)
0,001s
13 dni
4 * 10
11
wieków
5 * 10
41
wieków
Wniosek:
nawet zastosowanie komputera
działającego 1000 razy szybciej
nie
pozwala
na wykonanie algorytmu (w
rozsądnym czasie)
.
Przykładowy program
Module Module1
Sub Main()
Dim BankBalance As Single =
500.01
If (
BankBalance < 0
) Then
Dim strError As String strError
=
"Hey, your bank balance is negative!"
System.Console.WriteLine(strError)
End If
End Sub
End Module
Programowanie w logice
append([ ], X, X).
append([H1 | T1], Y, [H1 | T2]) :- append(T1,Y,T2).
?- append([a, b, c], [d, e], X).
X = [a, b, c, d, e]
?- append([a, b], X, [a, b, c]).
X = [c]
?- append(X, Y, [a, b, c]).
X = [ ] Y = [a, b, c] ;
X = [a] Y = [b, c] ;
X = [a, b]
Y = [c] ;
X = [a, b, c]
Y = [ ] ;
no
Programowanie funkcyjne
(define (silnia n)
if (n = 0) 1
n * (silnia (n-1)))
(silnia 5)
120
Przykładowe elementy
języka
• stałe
• zmienne
• typy
• deklaracje
• instrukcje
• funkcje i procedury
• moduły
Deklaracje stałych
Const name [ As type ] = initexpr
Przykłady:
Const Pi = 3.14159
Const
m
As
Integer
= 30
identyfikator
typ
Type
Storage size
Boolean
2 bytes
Byte
1 byte
Char
2 bytes
Date
8 bytes
Decimal
16 bytes
Double
8 bytes
Integer
4 bytes
Long
8 bytes
Object
4 bytes
Short
2 bytes
Single
4 bytes
Deklaracje zmiennych
Dim name [ As type ] [ = initexpr ]
Przykłady:
Dim EmployeeID As Integer = 1
Dim EmployeeName As String =
"Bob Owens"
Dim EmployeeAddress As String
Przykład
Module Module1
Sub Main()
Dim intVariable1 As Integer = 1234
Dim intVariable2 As Integer = 2345
Dim intVariable3 As Integer
intVariable3 = intVariable1 + intVariable2
System.Console.WriteLine(intVariable3)
End Sub
End Module
Operatory arytmetyczne
^
Exponentiation
*
Multiplication
/
Division
\
Integer division
Mod
Modulus
+
Addition
-
Subtraction
& +
String Concatenation
Podstawienia
=
Assignment
^=
Exponentiation followed by assignment
*=
Multiplication followed by assignment
/=
Division followed by assignment
\=
Integer division followed by assignment
+=
Addition followed by assignment
-=
Subtraction followed by assignment
&=
Concatenation followed by assignment
Operatory relacyjne
<
(Less than) True if operand1 is less than operand2
<=
(Less than or equal to) True if operand1 is less than
or equal to operand2
>
(Greater than) True if operand1 is greater than
operand2
>=
(Greater than or equal to) True if operand1 is
greater than or equal to operand2
=
(Equal to) True if operand1 equals operand2
<>
(Not equal to) True if operand1 is not equal to
operand2
Is
True if two object references refer to the same object
Like
Performs string pattern matching
And
Performs an And operation (for logical operations: True if
both operands are True, False otherwise; the same for bit-by-
bit operations where you treat 0 as False and 1 as True).
Not
Reverses the logical value of its operand, from True to False
and False to True, for bitwise operations, turns 0 into 1 and 1
into 0.
Or
Operator performs an Or operation (for logical operations: True
if either operand is True, False otherwise; the same for bit-by-
bit operations where you treat 0 as False and 1 as True).
Xor
Operator performs an exclusive-Or operation (for logical
operations: True if either operand, but not both, is True, and
False otherwise; the same for bit-by-bit operations where you
treat 0 as False and 1 as True).
AndAlso
"short circuited" And operator; if the first operand is
False, the second operand is not tested.
OrElse
"short circuited" Or operator, if the first operand is True,
the second is not tested.
Priorytety operatorów
Module Module1
Sub Main()
Dim intGrade1, intGrade2, intGrade3,
_
intNumberStudents As Integer
intGrade1 = 60
intGrade2 = 70
intGrade3 = 80
intNumberStudents = 3
System.Console.WriteLine("Average grade = " & _
Str(
intGrade1 + intGrade2 + intGrade3/ _
intNumberStudents
))
End Sub
End Module
Priorytety operatorów
Module Module1
Sub Main()
Dim intGrade1, intGrade2, intGrade3, _
intNumberStudents As Integer
intGrade1 = 60
intGrade2 = 70
intGrade3 = 80
intNumberStudents = 3
'Three students
System.Console.WriteLine
("Average grade = " & _
Str(
(
intGrade1 + intGrade2 + intGrade3
) / _
intNumberStudents
))
End Sub
End Module