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