Transcript PDD_unit1

IT1003 - PDD
• Unit 1
– Creative Thinking and problem solving skills,
visualization and memory- Problem solving
concepts-Problem solving in everyday life,
types of problems, problem solving concepts
for computers, algorithms and flowcharts;
Programming Concepts-preprocessing,
compilation, assembling and linking
Creative Thinking
• A way of looking at problems or situations
from a fresh perspective that suggests
unorthodox solutions (which may look
unsettling at first)
• Creative thinking can be stimulated both
by an unstructured process such as
brainstorming, and by a structured process
such as lateral thinking.
Visualization
• Visualization or visualisation is any
technique for creating images, diagrams,
or animations to communicate a message.
• Visualization through visual imagery has
been an effective way to communicate
both abstract and concrete ideas
Abstract Image
Concrete Image
Human Memory
There are three types of memory function:
Sensory memories
Short-term memory or working memory
Long-term memory
Sensory memory
• Buffers for stimuli received through senses
– iconic memory: visual stimuli
– echoic memory: aural stimuli
– haptic memory: tactile stimuli
• Continuously overwritten
Short-term memory (STM)
• Scratch-pad for temporary recall
– rapid access ~ 70ms
– rapid decay ~ 200ms
– limited capacity 7± 2 chunks
Example:
212348278493202
0121 414 2626
HEC ATR ANU PTH ETR EET
Long-term memory (LTM)
• Repository for all our knowledge
– slow access ~ 1/10 second
– slow decay, if any
– huge or unlimited capacity
• Two types
– episodic
– semantic
– serial memory of events
– structured memory of facts,concepts, skills
semantic LTM derived from episodic LTM
LTM - Storage of information
• rehearsal
– information moves from STM to LTM
• total time hypothesis
– amount retained proportional to rehearsal time
• distribution of practice effect
– optimized by spreading learning over time
• structure, meaning and familiarity
– information easier to remember
LTM - Forgetting
decay
– information is lost gradually but very slowly
interference
– new information replaces old: retroactive interference
– old may interfere with new: proactive inhibition
so may not forget at all memory is selective …
… affected by emotion – can subconsciously `choose' to forget
LTM - retrieval
recall
– information reproduced from memory can be assisted by cues,
e.g. categories, imagery
recognition
– information gives knowledge that it has been seen before
– less complex than recall - information is cue
Computer Memory
• Short Term Memory
– Random access memory (RAM)
• on silicon chips
• 100 nano-second access time
• usually volatile (lose information if power
turned off)
• data transferred at around 100 Mbytes/sec
– Some non-volatile RAM used to store basic
set-up information
Long-term Memory - disks
• magnetic disks
– hard disks typically 40 Gbytes to 100s of
Gbytes
access time ~10ms, transfer rate 100kbytes/s
• optical disks
– use lasers to read and sometimes write
– more robust that magnetic media
– CD-ROM
- same technology as home audio, ~ 600
Gbytes
– DVD - for AV applications, or very large files
Virtual memory
• Problem:
– running lots of programs + each program large
– not enough RAM
• Solution - Virtual memory :
– store some programs temporarily on disk
– makes RAM appear bigger
• But … swapping
– program on disk needs to run again
– copied from disk to RAM
– slows t h i n g s
d o w
n
Compression
• reduce amount of storage required
• lossless
– recover exact text or image – e.g. GIF, ZIP
– look for commonalities:
• text: AAAAAAAAAABBBBBCCCCCCCC
10A5B8C
• video: compare successive frames and store change
• lossy
– recover something like original – e.g. JPEG, MP3
– exploit perception
• JPEG: lose rapid changes and some colour
• MP3: reduce accuracy of drowned out notes
Storage formats - text
• Text
– ASCII - 7-bit binary code for to each letter and character
– UTF-8 - 8-bit encoding of 16 bit character set
– RTF (rich text format) - text plus formatting and layout
information
– docx, txt
• Images:
– many storage formats :
(PostScript, GIFF, JPEG, TIFF, PICT, etc.)
• Audio/Video
– again lots of formats :
(QuickTime, MPEG, WAV, etc.)
methods of access
• large information store
– long time to search => use index
– what you index -> what you can access
• simple index needs exact match
• access without structure …
– free text indexing (all the words in a document)
– needs lots of space!!
Problem….?
•
•
•
•
What is a problem?-Types of problems
Problem Solving in everyday life.
Six steps for general problem solving
Problem solving concepts for computers- Constants,
Variables, Operators, Hierarchy of operations, Data
types, Equations, Functions, Expressions.
• Organising Problems- Problem Analysis Charts,
Structure/Interactivity Charts, IPO Chart, Algorithm,
Flowcharts, Internal and External documentation
What is a
PROBLEM
• A state of difficulty that needs to be resolved
• PROBLEMS EXIST WHERE GOALS NEED TO BE ATTAINED
AND THERE IS UNCERTAINTY ABOUT SOLUTION
Problem Faced in Everyday in Life
•
•






People make decisions everyday
Examples:
Should I wear casual or formal today?
Should I watch TV or go out to cinema?
what career?
what course?
What shoes?
Everything needs a DECISION AS A SOLUTION TO THE
PROBLEM
What happens when bad decisions are made?
• WASTAGE OF TIME AND RESOURCES
Six steps to ensure a Best decision in PROBLEM
SOLVING
•
Identify the problem
•
Understand the problem
•
Identify alternative ways to solve the problem
•
List instructions that enable you to solve the problem
using selected solution
•
Select the best way to solve the problem from the list of
alternative solutions
•
Evaluate the solution
What makes a good decision?
•
•
•
•
Well identified problem
All alternatives considered
Information overloaded – appropriate alternatives
Can the person carry out steps/instructions
Approaches to solve a problem:
Algorithmic
Heuristic
•Solutions that can be solved with a series
of known actions are called
Algorithmic Solutions
•Employing a self-learning approach to the
solution of a problems is known as
Heuristic Solutions
Examples
Algorithmic solution:
•
To make a cup of coffee
•
To find largest of three numbers
Heuristic solutions:
•
how to buy the best stock?
•
How to play chess?
Problem solving with computers
Conventional Computers use algorithmic solutions
• Program – set of instructions that make up solution to a problem
• Results – outcome of running the program
• Testing – Are the outcomes what you expected and correct
• Documentation – instructions telling users how to use the program
Problem solving with computers involves several steps
Clearly define the problem.
• Analyse the problem and formulate a method to solve it (see also
.validation.).
• Describe the solution in the form of an algorithm.
• Draw a flowchart of the algorithm.
• Write the computer program.
• Compile and run the program (debugging).
• Test the program (debugging) (see also verification.).
• Interpretation of results.
Data vs. Information
O
U
T
P
U
T
I
N
P
U
T
Data
Unorganized facts
P
R
O
C
E
S
S
Information
Processed
meaningful
report
Communicating with computer
What is a program?
• A set of step-by-step instructions that directs the computer to
perform tasks and produce results.
What is a Programming Language?
• A programming language is a set of rules that instructs a computer
what operations to perform.
• Syntax: Rules governing the computer oerating system, the
language and the application
• BUG: It is an error
• Debugging: The process of locating and correcting an error.
algorithm
Sequence of steps
that can be taken to solve a given problem
Form of an Algorithm
Control Module
1. Instruction
2. Instruction
3. …
4. ..
..
---end
Note: Uses End
indicating end of
processing
Name of Module (list of
Parameters)
1. Instruction
2. Instruction
3. ..
4. ..
..
……..exit
Note: Uses Exit
bcos processing
continues
Points to Note
1.
The process consists of repeated application of simple steps
2.
All steps are unambiguous (clearly defined)
3.
We are capable of doing all those steps
4.
Only a limited no. of steps needs to be taken
5.
Once all those steps are taken according to the prescribed
sequence, the required result will be found
6.
Moreover, the process will stop at that point
Algorithm (Better Definition)
1st Definition:
Sequence of steps that can be taken to solve a problem
Better Definition:
A precise sequence of a limited number of unambiguous,
executable steps that terminates in the form of a solution
Three Requirements
1.
2.
3.
Sequence is:
a.
Precise
b.
Consists of a limited number of steps
Each step is:
a.
Unambiguous
b.
Executable
The sequence of steps terminates in the form of a solution
Flowchart
• A graphical representation of a process (e.g. an algorithm), in which
graphic objects are used to indicate the steps & decisions that are
taken as the process moves along from start to finish.
• Individual steps are represented by boxes and other shapes on the
flowchart, with arrows between those shapes indicating the order in
which the steps are taken.
Start or stop
Process
Input or output
Decision
Flowchart
Symbols
Flow line
Connector
Off-page connector
Process Module
Flowchart
Symbols
counter
Automaticcounter loop
A
B
S
Developing Short Programs
1.
Read, understand the
problem
5.
Write the code on a piece of
paper
2.
Do you have all the required
data?
6.
Hand-check it
7.
Type it in
8.
Run & check it on test cases
9.
Errors? fix & redo 9
No: Get it
Else assume it. State it
explicitly
3.
Do the design
Done!
4.
Write test cases
Coding
• Writing the program is called Coding.
• In this step, the logic that has been
developed in the algorithm is used to
actually write the program.
• Using any programming language, the
algorithm can be converted to coding.
Compiling and Running the
program
• Compiling is a process in which the source program
instructions are translated into a form that is suitable for
execution by the computer.
• The compiler does the translation after examining each
instruction for its correctness. The translation results in the
creation of object code. If necessary, Linking is also done.
• Linking is the process of putting together other program files
and functions that are required by the program.
•
After compilation, the program can be executed. During
execution, the executable object code is loaded into the
computer memory and the program instructions are executed.
Preprocessor
• The ``preprocessor'' is a translation phase
that is applied to your source code before
the compiler proper gets its hands on it.
• Each preprocessor directive is identified
by the # (pound sign) at the beginning of a
line. [in C programs]
Testing
• Testing is the process of executing a
program with the deliberate intent of
finding errors.
• Some programmers use the terms
“testing” and “debugging” interchangeably,
but careful programmers distinguish
between the two activities.
• Testing is a means of detecting errors.
Debugging is a means of diagnosing and
correcting their root causes.
Debugging
• Debugging is the process of identifying the
root cause of an error and correcting it.
• On some projects, debugging occupies as
much as 50 percent of the total
development time.
• For many programmers, debugging is the
hardest part of programming.
Maintenance
• Programs require a continuing process of
maintenance and
modification to keep pace with changing
requirements and
implementation technologies.
• A program’s ability to be read and
understood is an important prerequisite to
its maintainability and modifiability.
Assembly language
• Assembly language is the most basic
programming language available for any
processor.
• With assembly language, a programmer works
only with operations implemented directly on the
physical CPU.
• Assembly language lacks high-level
conveniences such as variables and functions,
and it is not portable between various families of
processors
Assembly language…
• Sample Program
MOV AX, 47
MOV DS, AX
INT 32
• MOV instruction moves data around, while
the INT instruction transfers processor
control to the device drivers or operating
system.
Assembly language…
• The assembly language program defines
the commands for assembling and linking
a program.
• programs can be assembled with the cc
command or the as command.