1. lecture

Report
Programming Fundamentals
1st lecture
Content
 Steps
of solving problems –
steps of writing a computer program
 Languages
ELTE
used when programming
 The alogirithm
 The specificaion
 Languages describing and algorithm –
structogram
 Coding
a program –
programming tool
2015.04.13.
2/42
Steps of solving problems
ELTE
2015.04.13.
Example: build a house
 What can you see from the process?
 What is behind?
1. Assess the needs (aspects: size of family, their idea,
money)
2. Design (plan, building material needs, engineer)
3. Organize (schedule, contractor…)
4. Building operations (supply material, building /
contractor…)
5. Put in practice (have a look – how fancy, try out –
how good)
6. Move in, live in (make corrections, detect problems)
3/42
Steps of creating a
computer program
1.
2.
3.
4.
ELTE
5.
6.
7.
8.
9.
2015.04.13.
Specify (from what?, what?)  specification
Design (with what?, how?)  data and algorithm desc.
Coding (how (computer)?)  program source code
representation + implementation
Testing (any bugs?)  error list (diagnosis)
Search for bugs (where is the bug?)  bug location
Correction (how is it correct?)  correct program
Quality assurance (Q&A), efficiency (can we
make better?, how?)  good program
Documenting (how does it work? etc…)  usable
program
Usage, maintenance (still works?)  durable
program
4/42
Language tiers
ELTE
Living language = English

Specification

Algorithm description

Programming language

Computer language (machine code)
Converge the languages (English  Computer)
2015.04.13.
5/42
The Algorithm
ELTE
2015.04.13.
Usage of drink dispensing machine:
1. Choose the drink!
2. Insert 1€!
3. Press the proper button!
4. Wait until the drink runs out!
5. Get the dring!
6. Drink it!
6/42
The Algorithm
 Executable
ELTE
2015.04.13.
(interpreter exists)
 Can be executed step by step
 The steps themselves are also
algorithms
 Exactly defined, with given order of
steps
 The description is finite, however the
execution time can be infinite
7/42
The Algorithm
ELTE
Usage of drink dispensing machine:
1. Choose the drink!
2. Insert 1€!
3. Press the proper button!
4. Repeat
look at the glass!
Until the drink runs out!
5. Get the dring!
6. Drink it!
New element: Repetition based on a condition
2015.04.13.
8/42
The Algorithm
ELTE
Usage of drink dispensing machine:
1. Choose the drink!
2. If you have 1€
then Insert 1€!
otherwise Insert 5 x 20 cents!
3. …
New element: choice from two options, (can
also be non-deterministic)
2015.04.13.
9/42
The Algorithm
Insert 5 x 20 cents:
1. Repeat 5 times:
Insert one 20 cents!
ELTE
New element: repeat given times
2015.04.13.
10/42
The Algorithm
ELTE
2015.04.13.
Structural elements of an algorithm:
 Sequence (execute step by step)
 Fork (choice from 2 or more activities
based on condition)
 Cycle (repeat given times, or until a
condition turns true)
11/42
Specification
1.
2.
3.
ELTE
4.
5.
6.
7.
2015.04.13.
Input data (identifier, domain set, unit)
What we know about the input
(precondition)
Results (identifier, domain, …)
The rule how to calculate the result (post
condition)
Requirements against the solution
Restrictions
Definitions of the applied notions
12/42
Specification
ELTE
2015.04.13.
Specification has to be
1. Exact, full
2. Short, compact, formalized
3. Expressive, understandable
Specification tools
1. Text description
2. Mathematical formulas
13/42
Example: triangle
(specification)
ELTE
Problem:
Is it true that given 3 numbers represent the
side lengths of a right angle triangle?
Specification:
 Input: x,y,z:Real
 Output: possible:Logical
 Precondition: x>0 and y>0 and z>0
 Post condition: possible=(x2+y2=z2)
Comment: we suppose z is the length of
hypotenuse
2015.04.13.
14/42
Example: triangle
(algorithm)
Algorithm:
ELTE
In: x,y,z [x>0 and y>0 and z>0]
possible:=(x2+y2=z2)
Out: possible
Comment: Later we will not include In and
Out in our algorithms
2015.04.13.
15/42
Example: triangle
(algorithm)
Another algorithm (without In and Out):
xx:=x2
ELTE
yy:=y2
zz:=z2
possible:=(xx+yy=zz)
We can introduce helper (internal, own)
variables.
2015.04.13.
16/42
Example: quadratic equation
(specification)
ELTE
Problem:
Let’s specify one root of a quadratic equation!
The equation is: ax2+bx+c=0
Questions:
What is the solution? – output
 What does it mean: „being a solution”? –

post condition
Does there a solution exist? – precondition
 Are we sure there is only one solution? –

output/post condition
2015.04.13.
17/42
Example: quadratic equation
(specification)
ELTE
Specification1:
 Input: a,b,c:Real
 Output: x:Real
 Precondition: –
 Post condition1: ax2+bx+c=0
Remark: this post condition does not provide
us with information how to create the
algorithm. No worries, let’s try again!
2015.04.13.
18/42
Example: quadratic equation
(specification)
ELTE
Specification2:
 Input: a,b,c:Real
 Output: x:Real
 Precondition: a0
What if we allowed?
 b  b2  4  a  c
 Post condition2: x 
2a
Open questions:


2015.04.13.
Is there always a solution?
Is there only one solution?
19/42
Example: quadratic equation
(specification)
Extend the output:
 Output: x:Real, exists:Boolean
 Post condition: exists=(b24*a*c) and
ELTE
 b  b2  4  a  c
exists  x 
2a
Open question:

2015.04.13.
Is there only one solution? – homework
20/42
Example: quadratic equation
(specification)
Algorithm:
ELTE
d:=b2-4*a*c
exists:=d0
exists?
I
True way
b d
x :
2a
2015.04.13.
N
False way
21/42
Example: quadratic equation
(specification)
Algorithm in another representation:
ELTE
2015.04.13.
Program QuadraticEquation:
d:=b2-4*a*c
exists:=d≥0
b d
If exists then x:
2 a
Program end.
22/42
Languages for algorithms
 Text
description
Describe by sentences
 Pseudo code

ELTE
 Describe
with drawing
Flow chart
 Structogram

2015.04.13.
23/42
Structogram
(and pseudo code)
 Sequence:
Statement1
Statement1
Statement2
Statement2
ELTE
 Fork
(2way):
If Condition then
Statements1
else
Statements2
End if
Condition
Statements1
 Fork
(more):
Condition1
Statements1
2015.04.13.
Statements2
Fork
In case Conition1:Statements1
In case Conition2:Statements2
…
…
Otherwise Statements otherwise
End fork
Condition2
Statements2
…
Otherwise
…
Statements
25/42
Structogram
(and pseudo code)
 Loops:
Condition
Statements
Condition
ELTE
Statements
i=1..n
Statements
 How


2015.04.13.
Loop while Condition
Statements
End loop
Loop
Statements
Until Condition
End loop
Loop i=from 1 to n
Statements
End loop
to draw structogram:
Text editor / spreadsheet
Specific tools (e.g. NSD)
26/42
Coding
(programming tool)
 Framework
(tool):
Code::Blocks
 Download:
ELTE
www.codeblocks.org
 Installation:
easy
2015.04.13.
27/42
Coding
(programming tool)
 At
first startup:
Choose compiler
ELTE
2015.04.13.
28/42
Coding
(programming tool)
 Steps
1.
ELTE
2.
2015.04.13.
of usage:
Create a project , the type determines the
platform of you want to deploy to.
Create a new project
sablon (template) választása:
Console application
29/42
Coding
(programming tool)
 Steps

ELTE
of usage:
workspace of project on the disk
project name
project root
folder
2015.04.13.
30/42
Coding
(programming tool)
 Further

ELTE
steps of usage:
workspace of project on the disk
Project name
Project root
folder
projektfájlnév
Project file
name with
full path
2015.04.13.
31/42
Coding
(programming tool)
 Further


ELTE
steps of usage:
Choose compiler
Finalize
compiler
development
version?
debug dirs
final version?
final version dirs
2015.04.13.
32/42
Coding
(programming tool)
 Our
environment:

on the disk:

in framework:
ELTE
browse
program
2015.04.13.
33/42
Coding
(programming tool)
 Our
environment:

on disk:

in framework:
ELTE
2015.04.13.
34/42
Coding
(programming tool)
 Compiling
our first program
ELTE
2015.04.13.
Szlávi-Zsakó: Programozási alapismeretek 1.
35/42
Codeing
(programming tool)
 The

output of compilation:
on the disk:
ELTE
2015.04.13.
Szlávi-Zsakó: Programozási alapismeretek 1.
36/42
Coding
(programming tool)
 The

output of compilation:
on the disk:
ELTE
2015.04.13.
37/42
Coding
(programming tool)
 Our

first program:
the content of main.cpp :
#include <iostream>
ELTE
using namespace std;
int main()
{
cout << "Hello world!" << endl;
return 0;
}
2015.04.13.
38/42
Coding
(programming tool)
 The

project source file:
The content of firstProg.cbp :
ELTE
(mily meglepő!)
2015.04.13.
39/42
Coding
(programming tool)
 Run


ELTE


the exe in console:
„compilation” –
run (the last compiled) –
compile & run –
the console looks like this:
execution time
The output
of the
program
returned
value
2015.04.13.
Start the exe directly from file system!
What do you experience? Why?
40/42
Programming Fundamentals
End of 1st lecture

similar documents