|Informatics for Secondary Education - A Curriculum for Schools (ED/HEP - pii-iip - IFIP - UNESCO, 1994, 103 p.)|
This Advanced Level Module is specified for secondary schools which have the necessary hardware and software, as well as trained teachers able to deliver the units.
Ideally, courses should be built up from Units GA1-3, in consultation with universities and tertiary institutions, so that advanced credit can be obtained towards a tertiary computer science course.
Students should be able to design and implement technical computer-based systems which model real problems using an algorithmic, problem solving approach.
Units GAS and GA2 together represent a standard set of courses which are commonly used at both secondary and post-secondary level as foundation in a study of Informatics. The depth and breadth of coverage and practice must be adjusted to match the student population so that students will be able to enter Higher Education with basic knowledge and skills in the programming of systems and in software development.
Students who have acquired these skills will often apply them in the modelling and programming of complex problems in areas such as robotics, artificial intelligence, graphics, and mathematics. Unit GA3 provides the comprehensive grounding for such modelling skills.
General Advanced Module
UNIT GA1 - FOUNDATIONS OF PROGRAMMING AND SOFTWARE DEVELOPMENT
Students should be able to design and program relatively small computer-based systems which model process-oriented problems.
Students should be able to:
1. adhere to the basic principles of software engineering
2. methodically analyse procedure-oriented problems through decomposition into procedural steps;
3. apply more or less formal techniques to design effective algorithms and data structures;
4. code and realise programs and sub-programs (modules) using a general purpose programming environment
5. use a functional model of a computer system and its programming environment.
Students need to develop skills which are fundamental to informatics as a discipline and to software development at all levels. These include the use of more or less formal methods of problem analysis and program design with an emphasis on creating not too complex programs which meet given specifications and which contain usable user interfaces.
Specific attention is paid to the type of problems which can programmed using fundamental, simple and structured data types (character, integer, real, array, etc.) and basic control structures (sequence, selection and repetition) of a high-level, block-structured programming language.
Emphasis is on modelling through process abstraction (top-down decomposition into sub-processes and subprograms). Methods of analysis, design strategies and the programming language environment should support this type of modelling.
Students will solve several, increasingly-complex problems. Problems are drawn from real application areas which students can readily understand and model. Small individual problems are chosen to learn how to use new algorithmic operations in conjunction with elements already known. But, also, some allencompassing problems should be included in which students have to integrate all that they have learned before.
Students apply informal and elementary formal techniques to analyze simple process-oriented problems in many application areas and describe them in terms of sub-process steps.
ALGORITHMS: Students design modular solutions through top-down analysis and stepwise refinement. They choose and specify data structures and algorithms to match the design. The data structures and control structures used in the algorithms should be directly related to the primitive structures of a block-structured programming language.
USER INTERFACE: Students design a simple user interface for their algorithms in the form of a tree of screen designs.
The algorithms and the modular structure are coded into a general-purpose programming language.
Realisation and Evaluation
The code is then realised in the form available programming environment. limitations of the programs.
problem solving process, software life cycle
process, input and output specification
identification of steps and modules
informal specification of pre- and post- conditions
top down, modular stepwise refinement
simple, useful user interfaces
simple and nested control structures
simple data structures code structure, readable and useful form elementary sorting and searching algorithms
simple recursion design of test data
execution, testing, and debugging
informal comparison of algorithms
limitations of design and program
system software and compilers
representation of stored data
Programming Language Elements
simple and structured data types of language, user-defined types
evaluation of expressions and standard elementary library functions
sequence, control, and iteration structures
simple interactive and text file input and output
subprograms and parameters
local and global variables and scope of variables and subprograms
Minimum necessary resources:
Version of a high-level block-structured programming language which supports modular program design and contains the necessary data types and control structures.
Introductory level textbook which presents examples of applications using the programming language. Most relatively recent texts, on an introduction to informatics or on computer science organizational-patterns, which have been developed through practice and fit the objectives of this unit
Optional extra resources:
Additional text material on machine organisation, systems software, compilers and language translators, internal representation of information, software engineering and the software life cycle.
Introduction to Programming (P1); Top-Down Programming (P2); Business Information Systems (VA1).
The concepts and skills included in this unit are those which have usually been presented in a first course on informatics for advanced students which some countries will find more appropriate for tertiary institutions than for secondary schools. The unit is quite extensive and requires teaching time every week, extending from over half a year to more than one year The time needed depends on prior experience and student background: whether they have studied Computer Literacy or Programming at Foundation Level. Depending on the target group, a subdivision of the unit may be advisable, organised around the concepts or principles under study.
Emphasis in the unit must be placed on hands-on applications. Students must apply techniques and principles, starting with elementary problems and building up their ability to handle more complex problems. Skills and concepts learned in earlier lessons are constantly reinforced through practice in new problems involving new concepts. Periodic exercises and projects which allow students to synthesize and integrate what they have learned must also be included.
Different countries will be at different phases of development: Automation Phase (pages 7, 17, 19)
UNIT GA2 - ADVANCED ELEMENTS OF PROGRAMMING
Students should be able to design, program and evaluate relatively complex computer-based systems which model process-oriented problems in many subject and application areas.
Students should be able to:
1. methodically analyse and model relatively complex process-oriented problems in a variety of application areas
2. apply moderately advanced formal analysis, design and data abstraction techniques to design effective algorithms, abstract data types and relatively sophisticated data structures;
3. code and realise programs and sub-programs (modules) using a general purpose programming environment
4. evaluate and explore alternative designs to programs.
Students should develop skills for solving more complex and sophisticated problems in many application areas. Emphasis needs to be placed on modelling through data abstraction (an important technique for improving reliability and refuse). Specific attention should be paid to algorithms and strategies for simulating advanced linear and non-linear data structures for the implementation of abstract data types.
This unit extends and builds on unit GAS: Foundations of Programming and Software Development. Students will solve several, increasingly-complex problems from real application areas.
Students develop models for relatively complex process-oriented systems using design strategies, such as modelling through abstract data types. They analyse systems to determine basic data objects, and associated functions which are used on these objects in the system.
Students develop abstract data types for the identified objects, which may be reused in other designs which involve the same objects. Students design a solution for the problem expressed in terms of modules which manipulate the abstract data objects only through the identified functions. Students design a suitable and effective user interface.
Students construct sophisticated linear and tree-like data structures to represent the abstract data types and also construct the functions needed to access these abstract data types in a general purpose programming language which supports information hiding and encapsulation, either directly or through simulation of data abstractions. Students code their design in the programming language.
The coded programs are realised and run in the programming environment. Students first realise, test and verify the realisation of the abstract data types, and only then the entire program.
Students determine order of magnitude indicators to compare algorithms, and practice some basic formal methods of program verification.
Where time is available, design strategies using other development paradigms, such as object-oriented
methodology or logic programming, may be explored if resources make this possible.
Design for reliability, reuse
Analysis strategies, such as data flow analysis using pre- and post-conditions
Formal program verification, assertions, invariants
Data abstraction and information hiding
Effective user interfaces
Graphs and graph algorithms
Encapsulation of abstract data types
Dynamic data types and structures
Binary search trees
Advanced searching algorithms
Efficient non-quadratic sorting algorithms
Algorithm analysis for order of magnitude approximation
Limitations of algorithms and unsolvable problems
Limits of numerical representations and simple numerical methods
Programming language elements
Singly and doubly linked list representations
Non-linear table data structures
Applications in graphics, robotics, or artificial intelligence
Modelling using logic or functional programming
Parallel processing of algorithms
Minimum necessary resources:
A high-level, structured programming language environment, which supports modular program design and data abstraction.
Intermediate level, modern text book on data structures and algorithm analysis which uses a data abstraction approach.
Programming environments for logic, functional, object-oriented programming or parallel processing.
Foundations of Programming and Software Development (GAB)
Emphasis is on concepts, theories, and practices of the discipline rather than on exhaustive coverage of language syntax. It is advisable to use, if possible, the same structured programming language for both units. The unit has an established traditional content which is described in many advanced texts on data structures. Teachers and curriculum designers should consider using the structure of these texts as the basis for sub-units and curriculum development.
Different countries will be at different phases of development: Information Phase (pages 7, 17, 19)
UNIT GA3 - APPLICATIONS OF MODELLING
Students should be able to work in teams and specify, methodically model and solve relatively complex problems.
Students should be able to integrate previously acquired knowledge, abilities and skills to enable them to:
1. specify, methodically model and solve relatively complex problems with the aid of general purpose programming tools
2. specify, methodically model and solve relatively complex problems in other subject areas with the aid of subject oriented programmable tools;
3. work in teams on a common modelling project.
Modelling ability is fundamental to the successful application of advanced software tools. This Unit requires students to use a variety of computer models, for example simulations and games; to identify the design decisions and simplifications which the developer made; and to discuss their importance and the consequences of possible mistakes.
Students work in teams to find answers to questions from the teacher, involving the creation of a model in which IT concepts, tools and methods play a role. Algorithmic thinking is an important capability for achieving these tasks.
During the development of the project the teacher will coach the students using generalisations, pointing out problems in modelling, team work and project development.
In this way students are able to integrate previously acquired knowledge, abilities and skills gained from their informatics experience and elsewhere.
What is modelling and what tools are
Students work with examples of modelling techniques in informatics and in different subject areas, going through the different phases of a modelling process and making an inventory of classical modelling tools. They study characteristics of team work, examine project management techniques and assess the effects of external pressures on the project. Students are also confronted with examples where modelling implies simplification of reality.
Methodological modelling using appropriate tools - what must
With a simple question as starting point the description of a problem is first expressed in natural language and then refined by asking appropriate questions and setting limits to the task. Students are then asked to point out components of the "reality to be modelled" which are relevant for constructing the model, and those which can be left out; giving explanations and justifying their choices.
Students write down the precise specifications for the work to be done and make a plan for its realisation. Working together in a team, they search and choose suitable tools and mode fling techniques for solving the problem; they then design and construct the executable solution to the problem.
Evaluation of models and of the process of modelling - how it
Students first explain and justify their choices of tools, techniques and solutions. They then investigate how closely the solution conforms to the initial description of the problem, updating their original solution as necessary. At this stage they should discuss any social or political issues arising out of the use of incorrect or oversimplified models for real life situations.
Topics for Modelling using General Purpose Programming Tools
Starting points are information modelling techniques such as entity-relationship modelling. Then situations such as growth and decay (for example Forresters model, the Game of Life), the spread of a disease or pollution, and waiting in a queue can be modelled. First an algorithmic model of the situation is made, which is then realised as a general purpose programming language.
Other rich fields for investigation are:
· Elementary Operational Research: linear programming, assignment problems, the travelling salesman problem;
· Probability (tossing coins or rolling dice, lotteries, roulette wheels): for example, a starting point for discussion could be "Everybody knows what is a roulette wheel in a casino. Can you build an "electronic" roulette wheel on your computer and prove that I will have the same chances to succeed or to lose as with a real life roulette wheel?;
· Graphical problems such as adjacency, paths, loops and shortest path: for example, "Here is a simplified map of the main road of our country; can you represent this map in a diagram on the computer and be able to give the distance when driving from one town to another along one of the roads?"
Topics for Modelling using Subject Oriented Programming
Here, models can be built and simulated which are part of a particular subject area for which special purpose programming tools exist. For example, problems in Statistics can be modelled and simulated (solved) with a statistical package, models for other mathematical problems can be simulated (solved) with a mathematical tool such as Maple or Mathematics Also more general tools, such as a spreadsheet, can be used to run a simulation.
Appendix 2 gives further examples of modelling opportunities.
Minimum necessary resources:
General purpose programming language such as Turbo-Pascal;
Software tools such as a data base management system, a text processor, a spreadsheet, depending on the type of problem to be solved, as well as a subject oriented tool such as Mathematica; Examples of ready made simulations should be available for evaluation and discussion.
Optional extra resources:
Graphics software, statistics package, Hypertext, Prolog.
Foundations of Programming and Software (GAS), Informatics in Other Disciplines (Appendix 2)