Problem solving

The topic of this lec­tu­re is pro­blem-sol­ving. You might say, “What a vast topic.” True. It’s such a gene­ral term that we cer­tain­ly can’t asso­cia­te it only with com­pu­ter scien­ce. Certainly, mathe­ma­ti­cians and phy­si­cists have been using this term for deca­des. There is a very famous book, “How to Solve It” by George Pólya, which descri­bes a series of methods for sol­ving mathe­ma­ti­cal pro­blems. Take a look at the Wikipedia page dedi­ca­ted to the book.

n the field of com­pu­ter scien­ce, when we refer to pro­blem-sol­ving, we often refer to the con­cept of ste­p­wi­se refi­ne­ment, which was pro­mo­ted by Wirth in a famous article:

It’s such a clas­sic that you can’t help but know it. Unfortunately, this arti­cle is older than me (by three mon­ths) and it sho­ws, in terms of sty­le. Therefore, I ask you to at lea­st take a look at the intro­duc­tion. If you want, you can tac­kle it more calm­ly later on. Alternatively, explo­re the web loo­king for “ste­p­wi­se refi­ne­ment” to try to under­stand how this tech­ni­que is described.

Following Wirth’s arti­cle, most text­books dea­ling with pro­gram­ming talk about this tech­ni­que, perhaps refer­ring to it as a “top-down approach”, often pro­po­sing exam­ples of its appli­ca­tion. Elliot Soloway, howe­ver, makes a very accu­ra­te cri­ti­ci­sm of this induc­ti­ve approach, then pro­mo­ting his vision based on pro­gram­ming plans that we have seen tal­king about the role of varia­bles and pro­gram­ming patterns.

Leggete la par­te evi­den­zia­ta in gial­lo (cri­ti­ca) e la par­te evi­den­zia­ta in rosa (pro­po­sta). Se poi vole­te, affron­ta­te con cal­ma l’in­te­ro arti­co­lo per rive­de­re i con­cet­ti del­la lezio­ne su PRIMM.

Read the part highlighted in yel­low (cri­ti­ci­sm) and the part highlighted in pink (pro­po­sal). If you want, calm­ly tac­kle the enti­re arti­cle to review the con­cep­ts of the les­son on PRIMM.

Some have tried to “jot down” some rules, simi­lar to tho­se of Polya, to tac­kle pro­blem-sol­ving in the com­pu­ter field:

At this point, I ask you to reflect on your pro­cess of sol­ving pro­gram­ming pro­blems. I’m not tal­king about com­plex pro­grams (the size of our cour­se pro­jec­ts), but sim­ple tasks that can be pro­po­sed to students.

As an exam­ple, I pro­po­se a series of pro­blems found in text­books for Scientific High Schools — Applied Sciences:

  • Choose one
    “Slow down for a moment” and try to sol­ve it not all at once, but by try­ing to use ste­p­wi­se refi­ne­ment tech­ni­ques; com­pa­re with Vasconcelos’ questions.
  • Try to reflect on how you would pre­sent the pro­blem to students

Here’s the list of problems:

  • Write an algo­ri­thm to print n rows of Pascal’s triangle
  • Write an algo­ri­thm to deter­mi­ne if a num­ber n is per­fect (it is equal to the sum of its divisors)
  • Write an algo­ri­thm that con­verts a deci­mal num­ber n into its equi­va­lent in bina­ry, hexa­de­ci­mal, octal
  • Write an algo­ri­thm that prin­ts all the num­bers that appear more than once in an input vector

From our mathematics/physics stu­den­ts, I would be inte­re­sted in having a discus­sion on how the topic of pro­blem-sol­ving is approa­ched in their fields.

Additional rea­ding

In addi­tion to the mate­rial pre­sen­ted, an arti­cle that addres­ses pro­blem-sol­ving from a more gene­ral point of view is the following

Materiale lezione

  • Slide pre­sen­ta­te duran­te la lezio­ne [Link]
Scroll to top