Computational Thinking and Problem Solving PDF

Co m p u t a t i o n a l Th i n k i n g a n d Pr o b l e m So l v i n g 4. A b st r a ct in g a n d M o d e lin g De b r i e f i n g  Co m p ut a t io n a l Th in k in g (CT) is n o t t h in k in g lik e co m p ut er s a s co m p ute rs ca n no t think  CT is n o t co m p ut er p r o g r a m...

Co m p u t a t i o n a l Th i n k i n g a n d Pr o b l e m So l v i n g 4. A b st r a ct in g a n d M o d e lin g De b r i e f i n g  Co m p ut a t io n a l Th in k in g (CT) is n o t t h in k in g lik e co m p ut er s a s co m p ute rs ca n no t think  CT is n o t co m p ut er p r o g r a m m in g eit h er  CT is t h in k in g a b o ut h o w y o u ca n use co m p ute rs to so lve p ro b le m s (Lect ur e 1)  Def in in g a n d a n a ly zin g p r o b lem s  Desig n in g st r uct ur ed so lut io n – A lg o r it h m s  Im p lem en t in g t h e so lut io n – Co m p ut er Pr o g r a m De b r i e f i n g (Co n t.)  So lv in g p r o b lem s w it h co m p ut er in v o lv e lo g ica l a nd a lg o rithm ic thinking (Lect ur e 2 )  Thre e te chniq ue s use s  De co m p o sitio n/ Pa tte rn d e te ctio n a nd g e ne ra liza tio n (Lect ur e 4 )  Ab stra ctio n a nd m o d e ling (Th is Lect ur e)  Alg o rithm ic thinking (Lect ur e 2 )  Le a r n i n g O u t co m e s A f t er t h is lect ur e, st ud en t s w ill b e a b le t o :  Exp la in a b st r a ct io n a n d la y er in g a b st r a ct io n s.  Exp la in t h e m o d elin g a ct iv it y. Next Lect ur e  A p p ly a b st r a ct io n a n d Id en t if y p a t t er n s Guided  A p p ly ef f ect iv e m o d elin g Example  Fr o m g e n e r a l i za t i o n t o a b st r a ct i o n  De co m p o sitio n is b r ea k in g t h e p r o b lem d o w n in t o sm a ller sub - p r o b lem s t o m a st er t h e p r o b lem co m p lexit y.  G e ne ra liza tio n/ Pa tte rn re co g nitio n is id en t if y in g p a t t e r n s a m o n g t h o se sub - p r o b lem s a n d sim p lif y in g t h e m (a so r t o f h id in g d et a ils in o r d er t o f o cus o n m a in p a t t er n s)  Ab stra ctio n: is a n a ct iv it y t h a t id en t if ies t h e m o st r ele v a n t in f o r m a t io n n ee d ed t o so lv e t h e p r o b lem a n d elim in a t es t h e ext r a n eo us d et a ils. [In o t h er w o r d s: a b st r a ct io n is r em o v in g un n ecessa r y d et a ils f r o m t h e p r o b lem so t h a t w e ca n f o cus o n im p o r t a n t d et a ils]  A b st r a ct i o n i n r e a l l i f e  Wh en y o u a r e r id in g y o ur b ik e, d o y o u n eed t o k n o w t h e in t er n a l f un ct io n s o f h o w it w o r k s?  Yo u just n eed t o k n o w t h a t y o u h a v e t o p ed a l it t o m a k es it w o r k.  Wh en y o u a r e d r iv in g a ca r d o y o u n eed t o k n o w t h e p a r t s o f t h e en g in e?  Yo u just n eed t o k n o w t h a t y o u h a v e t o g iv e it g a s, b r a k e a t t h e r ig h t t im es, t ur n , et c. t o d r iv e it co r r ect ly.  Wh en y o u a r e p la y in g a v id eo g a m e such a s M in ecr a f t d o y o u n eed t o k n o w t h e co m p ut er co d e used t o cr ea t e it ?  Wh y a b st r a ct i o n ?  We w a n t t o so lv e r ea l- w o r ld p r o b lem s usin g co m p ut er s, b ut r ea l- w o r ld p r o b lem s a r e f illed w it h en d less d et a ils.  We ca n ’t d escr ib e t h e w o r ld in it s en t ir et y.  In st ea d , w e cr ea t e m o d els o f t h e r ea l w o r ld a n d t h e n r ea so n a b o ut t h e p r o b lem v ia t h ese m o d els.  Th en , w e t ea ch co m p ut er h o w t o use t h ese m o d els. A b st r a ct io n is a k ey t o b uild in g ef f icien t m o d els  A b st r a ct i o n e x a m p l e (M a k k a h Tr a n si t ) We f o cus o n ly o n t h e t r a n sit d et a ils, o t h er d et a ils in M a k k a h cit y w er e r em o v ed La y e r e d a b st r a ct i o n La y e r e d a b st r a ct i o n La y e r e d a b st r a ct i o n  M o d elin g  A ll m o d els h id e so m e d et a ils o f t h e r ea lit y t h ey r ep r esen t.  Th e t h in g s jud g ed ir r elev a n t in a m o d el’s co n t ext a r e lef t o ut o f it (See Fig ur e 4.6)  Th e t h in g s r em a in in g p la y o n e o f t w o r o les in t h e r ep r esen t a t io n :  en t it ies: t h e co r e co n cep t s o f t h e sy st em ;  r ela t io n sh ip s: a co n n ect io n t h a t r ela t es en t it ies in t h e sy st em.  M o d elin g  M a n y t y p es o f m o d els exist (d if f er en t v iew s o f t h e sa m e sy st e m ) => ch o o se t h e a p p r o p r ia t e m o d el(s) d ep en d in g o n w h ich a sp ect s y o u w a n t t o sh o w  Rela t io n sh ip t y p es d ep en d s o n w h a t y o u w a n t t h e m o d el t o d escr ib e a b o ut y o u r en t it ies.  A b elo n g s t o B;  C co n t a in s D;  E h a p p en s b ef o r e F;  G o ccup ies t h e sa m e sp a ce a s H.  So m et im es, t h o se r ela t io n sh ip s a r e d ir ect io n a l. Hen ce:  B o wns A;  D is co n t a in ed b y C;  F h a p p en s a f t er E.  A d d it io n a l in f o rm a t io n f o r a m o d el Properties: discrete pieces of information about that particular entity or relationship, like a station’s name on the Makkah transit map. Type: a classification that the entity belongs to. This can tell you lots of things about that entity implicitly. For example, a line between two stations relates them by saying they’re on the same line; the color denotes the line’s type Rules: statements about an entity that must hold true. A station might be labeled with a rule saying ‘Closed between 10 and 15 November’. Behaviors: descriptions of actions that may be expressed in natural language or algorithmic form. For example, one section of a Makkah transit line might state that buses travel at a slower pace along it.  St a t i c v s. d y n a m i c m o d e l s  Sta tic m o d e ls g iv es us a sn a p sh o t v iew o f t h e sy st e m. Th ey d ep ict en t it ies a n d r ela t io n sh ip s a t a sin g le p o in t in t im e (M a p o f M a k k a h Tr a n sit ).  Dyna m ic m o d e ls (DM ) co n sid er t h a t w o r ld y o u’r e m o d elin g ch a n g es o v er t im e (i.e. exp la in t h e ch a n g es in st a t es a s t im e p r o ceed s). DM in v o lv es t h e f o llo w in g :  st a t es: d escr ip t io n o f t h e en t it ies a t sp ecif ic p o in t s in t im e;  t r a n sit io n s: a ch a n g e in st a t e. DM g en er a lly in clud es so m e o r a ll o f t h e f o llo w in g a s w ell:  ev en t s: t h in g s t h a t h a p p en t o t r ig g er t r a n sit io n s;  a ct io n s: co m p ut a t io n s t h a t a r e ca r r ied o ut a s p a r t o f a st r a n sit io n.  Tu r n st i l e e x a m p l e  A t t h e st a r t p o in t (t h e so lid b la ck cir cle), t h e t ur n st ile is in a lo ck ed st a t e.  In ser t in g a co in is a n ev en t. It t r ig g er s t h e t r a n sit io n o f a lo cked t ur n st ile in t o a n un lo ck ed o n e.  Push in g a n un lo ck ed t ur n st ile (a n o t h er ev en t ) t r a n sit io n s it b a ck t o t h e lo ck ed st a t e.  Push in g a lo ck ed t ur n st ile h a s n o ef f ect.  Dy n a m i c m o d e l s i n Sci e n ce  M o d er n scien ce uses m a the m a tica l m o d els t o m a ke p r ed ict io n s o f ext r em ely co m p lica t ed sy st em s w h e r e t h eo r y a n d sim p le exp er im en t a t io n a r e in suf f icien t.  Clim a t e m o d els a r e o n e o f t h e m o st p o w er f ul exa m p les. Th ey d escr ib e t h e n a t ur e o f g lo b a l en t it ies – like a t m o sp h er e, ice m a sses, la n d sur f a ces a n d ult r a v io let r a y s – a n d t h e co m p lex in t er a ct io n s b et w een t h em usin g m a t h em a t ica l f o r m ula e.  In t h is co ur se y o u w ill b e in t r o d uced t o b uild in g sim p le m a t h em a t ica l m o d els a s a p r o o f o f co n cep t.  M o d e l i n g Da t a  Co m p ut er ized so lut io n s p r o cesses a n d st o r e d a t a v ia a lg o r it h m s. We sh o uld m o d el t h e d a t a , it s t y p es a s w ell a s t h e r e la t io n sh ip s b et w een t h em.  M o d e l i n g Da t a  Ca rd ina lity: a p r o p er t y d e scr ib in g t h e n um b er o f ele m en t s in so m et h in g.  M o d e l i n g i n t e r a ct i o n  Fo r t h e user in t er a ct io n :  d ef in e t h e v a r io us v iew s a v a ila b le t o t h e user (f o r st ud en t exa m p le: p er so n a l d et a ils, co ur se o v er v iew , g r a d e o v er v iew …)  M o d el t h e n a v ig a t io n if y o ur sy st em p r o v id es a lo t o f v iew s  Pr o t o t y p e t h e user in t er f a ce (m o ck - up o f t h e exp ect ed in t er f a ce la y o ut )  Re m e m b e r  A b st r a ct io n is p ick in g o ut o n ly t h e r elev a n t d et a ils a n d sup p r essin g t h e r em a in d er.  La y er s o f a b st r a ct io n co n sid er a p r o b lem f r o m m ult ip le p o in t s o f v iew.  M o d elin g , a t y p e o f a b st r a ct io n , p la y s a n im p o r t a n t p a r t in p r o b lem - so lv in g b y r ep r esen t in g t h e k ey p a r t s o f a so lut io n.  Th is h elp s y o u t o un d er st a n d t h e sy st em y o u’r e t r y in g t o b uild , a s w ell a s p r ed ict it s ev en t ua l b eh a v io r.  M o d els co m e in n um er o us f o r m s, w h ich y o u ca n f r eely ch o o se f r o m. De b r i e f i n g A m o d el r ep r esen t s t h e en t it ies in a so lut io n a n d r ela t io n sh ip s b et w een t h em. Th ey t y p ica lly in clud e o n ly d et a ils r elev a n t in a cer t a in co n t ext (A b st r a ct io n ). M o d els co m e in t w o t y p es: St a t ic m o d els d ep ict a sy st em a t a p a rticula r p o int in tim e. Dy n a m ic m o d els sh o w h o w a sy st em cha ng e s o ve r tim e. M o d els r ed uce t h e m en t a l ef f o r t r eq uir ed t o co m p r eh en d a so lut io n. So m e m o d els a r e f o r m a l m o d els a n d h elp t o v a lid a t e id ea s b y seein g if a n y r ules a r e b r o k en. So m e m o d els a r e execut a b le m o d els a n d p r ed ict h o w a so lut io n w ill b eh a v e  M o d elin g  Eng ine e rs f o cus o n p h y sica l m o d els t h a t d ep ict w o r k in g sy st em s. Scie ntists o f t en f a v o r m a t h em a t ica l m o d els t h a t r ed uce p h en o m en a d o w n t o v a r ia b les. So ftwa re d e ve lo p e rs t en d t o use co n cep t ua l m o d els t h a t d escr ib e id ea s.  Un if ied M o d elin g La n g ua g e (UM L) is a g en er a l- p ur p o se m o d elin g la n g ua g e used t o d escr ib e a n y p a r t o f a so f t w a r e - in t en siv e sy st em. UM L ca n b e used t o m o d el:  en t it ies;  r ela t io n sh ip s;  p r o cesses;  usa g e.  M o d e l i n g En t i t i e s  En t it ie s a r e t h e f o cus o f st a t ic d ia g r a m s (a k a st r uct ur a l d ia g r a m s in UM L), w h ich d ep ict co m p o n en t s in a so lut io n.  A cla ss d ia g r a m sh o w s a so lut io n d eco m p o sed in t o cla sses.  M o d e l i n g Re l a t i o n sh i p s: d e p e n d e n ci e s  En t it y B r eq uir es en t it y A t o p r o v id e so m e f un ct io n a lit y (B is sen sit iv e t o ch a n g es in A )  In h er it a n ce cr ea t es a sp ecif ic so r t o f d ep en d en cy b e t w een a t y p e a n d it s sub t y p e so t h a t t h ey sh a r e a n ‘is a ’ r ela t io n sh ip.[Fo r d Tr a n sit is a va n, a n d t h a t a va n is a ve hicle ]  M o d e l i n g Re l a t i o n sh i p s: A sso ci a t i o n s  A sso cia t io n s d escr ib e a r ela t io n sh ip w h er e eit h er en t it ies sh a r e a lin k o r o n e en t it y a g g r eg a t es o t h er en t it ies.  A n a g g re g a tio n is a n a sso cia t io n t h a t im p lies a lo o se r ela t io n sh ip b et w een t w o t y p es. (O n e m a y m a k e use o f t h e o t h er , b ut t h eir exist en ces a r e in d ep en d en t o f ea ch o t h er )  A co m p o sitio n is st r o n g er t h a n a n a g g r eg a t io n. It im p lies t h a t a n in st a n ce o f o n e t y p e is co m p o sed o f in st a n ces o f a n o t h er a n d t h a t t h e exist en ce o f t h e la t t er d ep en d s o n t h e exist en ce o f t h e f o r m er.  M o d e l i n g Pr o ce sse s (d y n a m i c b e h a v i o r )  St a t e Ch a n g e  M o d e l i n g Pr o ce sse s (d y n a m i c b e h a v i o r )  Wo rkflo w: A st a t e m a ch in e d ia g r a m em p h a sises t h e ch a n g es in st a t e o f a sin g le en t it y , essen t ia lly sh o w in g p r o g r ess f r o m o n e o b ject ’s p o in t o f v iew.  M o d e l i n g Pr o ce sse s (d y n a m i c b e h a v i o r )  Use ca se : a n a ct io n (o r seq uen ce o f a ct io n s) p r o v id ed b y a sy st em t h a t h elp s a user.  Ch a r a ct e r i st i cs o f a n e f f e ct i v e m o d e l Ab stra ct: a g o o d m o d el h id es un im p o r t a n t a n d ir r elev a n t d et a ils, a llo w in g us t o co n cen t r a t e o n t h e im p o r t a n t co n cep t s. Und e rsta nd a b le : a g o o d m o d el p r e sen t s in f o r m a t io n in t uit iv ely a n d r e q uir es less ef f o r t t o un d er st a n d t h a n t h e eq uiv a len t co d e d o es. Accura te : a g o o d m o d el m ust b e a t r ue- t o - lif e r ep r esen t a t io n o f t h e sy st em it m o d els. Pre d ictive : a g o o d m o d el a llo w s us t o co r r ect ly p r ed ict t h e n o n - o b v io us p r o p er t ie s o f a sy st em. Ine xp e nsive : it sh o uld b e ch ea p er t o p r o d uce a m o d el t h a n t o co n st r uct t h e a ct ua l sy st e m it self. A n y Q uest io n ? ◊ « ’ Tå « ö