Podstawy programowania

(1)

dr Jerzy Bartoszek

[e-mail]

[e-mail].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