Computational Thinking
is
Informational Thinking
Greg Michaelson
School of Mathematical & Computer Sciences
Heriot-Watt University
[email protected]
http://www.macs.hw.ac.uk/~greg
21/11/2012
Computational Thinking is Informational
Thinking
1
Models
• we make models of the
world to:
– understand it
– change it in predictable
ways
Columbus Globes
http://www.maps2anywhere.com/Globes/columbus_world_globes_01.htm
21/11/2012
Computational Thinking is Informational
Thinking
2
Programs and models
world
• a program:
– maps the abstractions of
a conceptual model
21/11/2012
Computational Thinking is Informational
Thinking
brain
model
3
Programs and models
world
• a program:
– maps the abstractions of
a conceptual model
– onto the concrete
behaviours of a physical
computer
brain
model
program
computer
21/11/2012
Computational Thinking is Informational
Thinking
4
Programs and models
world
• a program:
– maps the abstractions of
a conceptual model
– onto the concrete
behaviours of a physical
computer
– so the behaviour of the
program on the
computer tells us about
the world
brain
model
program
prediction
• computing
computer
21/11/2012
Computational Thinking is Informational
Thinking
5
How do we...?
• make models?
– solve problems
• realise models as
programs?
– write programs
– programming
Then a miracle occurs...
http://www.sciencecartoonsplus.com/pages/gallery.php
21/11/2012
Computational Thinking is Informational
Thinking
6
Discourse & method
• should we separate out:
– problem solving
– model making
– programming?
• are they inextricably linked?
21/11/2012
Computational Thinking is Informational
Thinking
7
Discourse & method
• we need languages/notations to:
– solve problems
– make models
– write programs
• should these be the same or different?
21/11/2012
Computational Thinking is Informational
Thinking
8
Computing Science?
• academic discipline
• underpins all ICT
– model making
– tool building
• theory & practice of computation
– making models of reality from information
structures & algorithms
– animating models on computers
• programming bridges models and computers
21/11/2012
Computational Thinking is Informational
Thinking
9
Computing Science?
• is programming the
“new Latin”?
• should we teach all
students to program?
Observer 1/4/12
21/11/2012
Computational Thinking is Informational
Thinking
10
Computing Science?
• NO!
• we need to teach all
students to think:
– first characterise
problem
– then choose
technology
• how to characterise
problems?
21/11/2012
Computational Thinking is Informational
Thinking
11
Computational thinking
• modern approach to
problem solving
• draws heavily on insights
from Computing Science
• very widely applicable
• not about programming
http://chomskyscolorlessgreenideas.blogspot.co.
uk/2009/09/chinese-room.html
21/11/2012
Computational Thinking is Informational
Thinking
12
Computing triangle
Computational
Thinking
problems
praxis
solutions
concepts
social needs
ICT
tools
21/11/2012
Computational Thinking is Informational
Thinking
Computing
Science
13
Computational thinking
• homage to:
– N. Wirth, Algorithms + Data Structures = Programs,
Prentice-Hall, 1973
• information + computations = solutions
– how do we know when the problem is solved?
– what information is relevant to solving the problem?
– how must the information change for the problem to be
solved?
– what computation(s) should we perform on the
information to reach the solution?
21/11/2012
Computational Thinking is Informational
Thinking
14
Computational thinking
• hardest part is characterising the problem
• two standard approaches:
– ask someone else...
– look for a similar problem you already know how to
solve
• what makes problems similar?
– similar information + computations
21/11/2012
Computational Thinking is Informational
Thinking
15
Computational thinking
• four core techniques;
– decomposition
– pattern recognition
– pattern generalisation/abstraction
– algorithm design
21/11/2012
Computational Thinking is Informational
Thinking
16
Decomposition
• identify the information
needed to solve
problem
• break the problem up
into smaller subproblems
• identify the subinformation needed to
solve sub-problems
21/11/2012
http://www.lostateminor.com/2012/03/14/if-stonehenge-came-with-ikeainstructions/
Computational Thinking is Informational
Thinking
17
Pattern recognition
• look for patterns amongst
problems
– have I seen a problem like this
before?
– how is this problem different?
• look for patterns in the information
http://en.wikipedia.org/wiki/Bank_statement
– how is the information structured?
– are there useful relationships within
the information?
– have I seem information organised
like this before?
– how is this information different?
http://www.moneymatterstome.co.uk/interactiveworkshops/writingcheque.htm
21/11/2012
Computational Thinking is Informational
Thinking
18
Pattern generalisation/abstraction
• what is the general case for
my problem?
– what doesn’t change in how
sub-problems are organised?
– what does change?
http://en.wikipedia.org/wiki/Bank_statement
• what is the general
organisation of the
information?
– what doesn’t change in
structure?
– what information does change?
http://www.learndirect.co.uk/campaigns/worthlearning/managing-money/understanding-bank-statement/
21/11/2012
Computational Thinking is Informational
Thinking
19
Algorithm design
• what is the sequence of
steps from the initial
information to the
problem being solved?
• how are sub-problems
connected?
• how does the
information change
between steps?
21/11/2012
Mug design – Le Chat Noir Boutique
http://www.lechatnoirboutique.com/proddetail.php?prod=FSFPTS
Computational Thinking is Informational
Thinking
20
Applying computational thinking
• what does this mean for
practical teaching?
• where to begin?
• are familiar approaches
useful?
• can we retrofit
computational thinking to
what we do already...?
21/11/2012
An armillary sphere and discussion by R. W.
Seale, in A New Geographical Dictionary,"
published by J. Coote, London, 1760
*http://www.columbia.edu/itc/mealac/pritchett/00routesdata/17
00_1799/compendia/coote/sphere.jpg
Computational Thinking is Informational
21
Thinking
Current approaches
• programming language oriented
–
–
–
–
–
full strength language
pedagogic or full strength subset
functional/logic
object oriented
pseudo code – language independent
• simple to complex
– stepwise refinement
– structured programming
– iterative prototyping
21/11/2012
Computational Thinking is Informational
Thinking
22
Current approaches
• components
–
–
–
–
–
–
21/11/2012
• design
modular programming
algorithms
data structures
types
classes
libraries
–
–
–
–
flowcharts
data flow
entity relationship
UML
•
•
•
•
•
Computational Thinking is Informational
Thinking
use case
class diagrams
structure diagrams
sequence diagrams
state machines
23
Current approaches
•
•
•
•
•
fashions change
too many possibilities
none work easily beyond simple cases
all have a strong focus on the final program
programming not hard when you know how to solve
the problem...
• ...except for vagaries of specific language syntax &
semantics & tools
– get in the way of problem solving & model making
21/11/2012
Computational Thinking is Informational
Thinking
24
Forget the past...!
• familiar approaches useful
– at end of problem solving to realise solution
– with more advanced classes when basic
computational concepts understood
• need to focus on problem without worrying about
how to implement solution
• key is to characterise information & computations
• start with information, not computations
21/11/2012
Computational Thinking is Informational
Thinking
25
Characterising information
• information = base/atomic elements + structure
• NB not type, class etc
– programming concepts
– used to represent/implement problem
information
21/11/2012
Computational Thinking is Informational
Thinking
26
Characterising information
• base/atomic elements
– things!
• at simplest, represented as symbols
– sequences of characters
– unitary entities that are meaningful
– e.g. words, numbers
• elements may be composite
– made up of sub-elements
– structured
21/11/2012
Computational Thinking is Informational
Thinking
27
Characterising information
• information structures
– sequences: before/after, unordered/ordered
– tables: rows & columns of contents
– arrays: index & contents
– record: fields & contents
– lists: head & tail values
– trees: value & branches
– graphs: nodes & arcs
• NB not data structures: programming concept
21/11/2012
Computational Thinking is Informational
Thinking
28
Characterising information
• structures have equivalences
– table == array of records of row/column contents
– array == list of index/value records
– list == array of records of head & tail
• for some problems, base elements in structures are
themselves structures
• where to begin...?
• back to Computing Science...?
21/11/2012
Computational Thinking is Informational
Thinking
29
Thinking about information
• start in real world!
• look at lots of concrete
examples:
– parked cars
– numbered houses
– supermarket queue
– English v Scottish
bank queue
– shopping list
21/11/2012
– receipt
– bill
– account statement
– itinerary
– diary
– calendar
– invitation list
– address book
– seating diagram
Computational Thinking is Informational
Thinking
30
Thinking about information
– shop catalogue
– library catalogue
– family tree
– cladistic tree
– decision tree
– underground map
– road map
– lottery ticket
– betting slip
21/11/2012
– sports league table
– mobile contacts
– browser favourites
– social media friends
– eBook downloads
– digital photo album
– digital music library
– music play list
Computational Thinking is Informational
Thinking
31
Thinking about information
• use concrete problem scenarios:
• typically, how to find specific information in
structure
• start from scratch
• try to characterise scenario’s:
– elements
– structures
• don’t yet introduce named structures
• do this intuitively
21/11/2012
Computational Thinking is Informational
Thinking
32
Thinking about information
• ask if information is:
– simple or composite
– linear or grid or branching or cyclical
– unordered or ordered
– fixed or changeable:
• content
• size
• shape
21/11/2012
Computational Thinking is Informational
Thinking
33
Thinking about information
• ask how to access elements
– why do you want to access elements
– which elements do you want to access
– how does why/which affect access
– where to start access
– how to continue access
– how to know if successful/unsuccessful
– what to do if unsuccessful
• then ask how to add/delete/modify elements
21/11/2012
Computational Thinking is Informational
Thinking
34
Thinking about information
• next, compare apparently disparate structures
• ask what:
– changes
– stays the same
• look for similarities in:
– concrete detail
– gross structure, ignoring elements
– access/update/add/delete
• use comparisons to draw out named structures
21/11/2012
Computational Thinking is Informational
Thinking
35
Thinking about information
• finally develop notion of abstract data type (ADT)
• operations to:
– construct new, empty structure
– add to structure
– find in structure
– change contents
– delete from structure
21/11/2012
Computational Thinking is Informational
Thinking
36
From information to computation
• abstract data type defines base operations
– like the verbs of a language
• computations structure these operations into
algorithms
• try to make structure of computation follow
structure of information
• not yet programming...
21/11/2012
Computational Thinking is Informational
Thinking
37
From information to computation
• go back to scenarios
• computation solves problems by changing old
information into new information
• in the scenario, explore sequences of information
change
21/11/2012
Computational Thinking is Informational
Thinking
38
From information to computation
• typically want to:
– traverse structure
• visit each element once
• continue visit until some condition is met
– do something to each element
– accumulate intermediate information
21/11/2012
Computational Thinking is Informational
Thinking
39
Structure traversal
• bounded iteration
– from first to last element
– notion of next element
• unbounded iteration
– continues while some condition holds
• how to start/continue/end iteration...?
21/11/2012
Computational Thinking is Informational
Thinking
40
Structure traversal
• bounded recursion
– base case
• at end of structure so return final value
– recursion case
• do something with current element
• recurse on rest of structure
• how to start/end/continue recursion...?
21/11/2012
Computational Thinking is Informational
Thinking
41
Accumulate information
• need to keep track of intermediate stages in
computation
– different positions in structure
– partial results from computations
• variable
– general name/value association
– change association with new value from
computation, often using old value
• use variable to manage stages of traversal...
21/11/2012
Computational Thinking is Informational
Thinking
42
Do something to element
• change element
• how to identify element?
– position in structure associated with a value
– position often found via structure name
– position is like a compound variable
21/11/2012
Computational Thinking is Informational
Thinking
43
How to decide what to do
• often want to change element regardless of its
properties
• may only want to change element if it satisfies
certain criteria
– choice/condition
• may want to change what to do next depending on
element properties
• use choice to manage stages of traversal...
21/11/2012
Computational Thinking is Informational
Thinking
44
Characterising the computation
• finally explore if computation is necessarily:
– iterative, or could it be recursive?
– sequential, or could it be concurrent?
– linear, or could it be backtracking?
– deterministic, could it be non-deterministic?
– bounded, or could it be unbounded?
21/11/2012
Computational Thinking is Informational
Thinking
45
But...
• need to describe information and computation in a
consistent manner
• so why not just use a programming language?
– programming is motivating
– seeing things work early on is motivating
21/11/2012
Computational Thinking is Informational
Thinking
46
But...
• so, use practical programming alongside problem
solving!
• but...
– choice of language affects what can be described
– programming language fine detail gets in way of
fundamental concepts
– simple small scale intuitive techniques don’t scale
to realistic problems
• for problem solving, use a neutral notation
– e.g. pseudo code
21/11/2012
Computational Thinking is Informational
Thinking
47
Conclusions
• focus on problem solving not programming
• CT = decomposition + abstraction + patterns +
algorithms
• solution = information + computation
• let information structure the computation
• start with concrete instances
• use CT to:
– ask good questions
– find well kent information structures
– guide computation design
21/11/2012
Computational Thinking is Informational
Thinking
48
Conclusions
• CT is a framework not a recipe
• CT components overlap and
interact
• maybe classic CT overemphasises computation at
expense of information?
http://affordablehousinginstitute.org/blogs/us/page/251
21/11/2012
Computational Thinking is Informational
Thinking
49
Activity
1. choose two very
different scenarios
from the following list:
– parked cars
– numbered houses
– supermarket queue
– English v Scottish
bank queue
– shopping list
– receipt
21/11/2012
– bill
– account statement
– itinerary
– diary
– calendar
– invitation list
– address book
– seating diagram
– shop catalogue
Computational Thinking is Informational
Thinking
50
Activity
– library catalogue
– family tree
– cladistic tree
– decision tree
– underground map
– road map
– lottery ticket
– betting slip
21/11/2012
– sports league table
– mobile contacts
– browser favourites
– social media friends
– eBook downloads
– digital photo album
– digital music library
– music play list
Computational Thinking is Informational
Thinking
51
Activity
2. choose one information
structure from the
following list:
• sequence: before/after,
unordered/ordered
• table: rows & columns of
contents
• array: index & contents
• record: fields & contents
• list: head & tail values
• tree: value & branches
• graph: nodes & arcs
21/11/2012
3. explain how to represent
both scenarios from 1.
using the information
structure from 2.
This is well suited for use as
an activity for a pair of
people.
Computational Thinking is Informational
Thinking
52
Resources
Jeanette Wing, `Computational Thinking’,
Communications of the ACM, Vol 49, No. 3, pp 33-35,
March 2006
http://www.cs.cmu.edu/~wing/publications/Wing06.pdf
Google, `Exploring Computational Thinking’
http://www.google.com/edu/computational-thinking/
Pat Phillips, `Computational Thinking: A Problem Solving
Tool for Every Classroom’ , CSTA/Microsoft
http://education.sdsc.edu/resources/CompThinking.pdf
21/11/2012
Computational Thinking is Informational
Thinking
53
Descargar

(problem solving && programming) || (problem solving