Algorithmic Concepts PDF

Chapter 1 Algorithmic Concepts 2 Dr. Samir FENANIR Chapter 1 : Algorithmic Concepts 1 Introduction Computer science plays a crucial role in today’s world, impacting various aspects of life, including education, commerce, medicine, te...

Chapter 1 Algorithmic Concepts 2 Dr. Samir FENANIR Chapter 1 : Algorithmic Concepts 1 Introduction Computer science plays a crucial role in today’s world, impacting various aspects of life, including education, commerce, medicine, telecommunications, and more. Moreover, with the widespread availability of the Internet, information is accessible everywhere and to ev- eryone. This information is processed and presented through the use of computers. However, a computer alone is not sufficient; it can only execute commands provided to it through a program. Therefore, programming is a fundamental activity in computer science. It can be considered as the art of defining an algorithm (a step-by-step procedure) to solve a problem and expressing this algorithm using a programming language so that it can be executed by a computer. 2 Generalities Before delving into the basic concepts of algorithmics, it would be wise to define some terminologies. 2.1 Computer Science Computer science is the discipline that focuses on the automated processing of information. Information can take various forms, including numbers, text, images, sounds, videos, and more. This automated processing is achieved through a machine known as a ’computer,’ which relies on software to perform these tasks. 2.2 Computer A computer is an electronic machine (Figure 1.1) capable of performing the following operations: 1. Receiving input information through input devices such as: Keyboard, Mouse, Scanner, Microphone,... 2. Processing this information using processing components such as: Microprocessor, Central Memory,... 3. Provide the output result using output devices such as: Screen, Printer, Speakers,... 4. Store information using storage components like: Hard drive, CD/DVD, Flash drive,... 3 Dr. Samir FENANIR Chapter 1 : Algorithmic Concepts Fig. 1.1 Features of a computer 2.3 Units of Data Measurement Data is stored in the central memory or on storage media in binary form. The quantity of data is measured in bytes, where one byte is a group of 8 bits. A bit is a binary digit that can be either 0 (current off) or 1 (current on). Using one byte, we can encode one character. For example, the character ’A’ is encoded as 01000001. The most used multiples of the byte are defined as follows: 1 kilo Bytes (KB) = 210 Bytes = 1024 Bytes 1 Mega Bytes (MB) = 220 Bytes = 1024 KB 1 Giga Bytes (GB) = 230 Bytes = 1024 MB 1 Tera Bytes (TB) = 240 Bytes = 1024 GB 2.4 Computer System The computer system consists of two parts: hardware and software. Hardware comprises physical components such as microprocessors, memory, screen, keyboard, hard disks, etc., used to process information according to sequences of instructions (programs) that make up the software. 2.5 Algorithm / Algorithmic An algorithm is an ordered sequence of instructions that outlines the steps to solve a given problem. On the other hand, algorithmics is the art of constructing algorithms that should be: Readable: understandable even by a non-computer scientist, Concise: use the minimum number of instructions, Structured: composed of different easily identifiable parts, Complete: they must take into account all possible cases. 4 Dr. Samir FENANIR Chapter 1 : Algorithmic Concepts 2.6 Program / Programming A program is an algorithm translated into a language understandable by the computer so that it can execute it. Programming plays the role of translating this algorithm into a programming language. 2.7 Programming language A programming language is a computer language that allows a human to write a program that will be analyzed and executed by a computer. Among the programming languages, we can mention: Pascal, C, C++, Java, Python, Visual Basic, etc. 2.8 Data structure A data structure is a way of organizing data to make it efficient for storage, retrieval, and modification. Common data structures include arrays, records, files, lists, stacks, queues, and more. These data structures play a crucial role in computer science and programming for managing and manipulating data effectively. 3 Problem Solving in Computer Science Several steps are required to solve a problem in computer science (figure 1.2) : Fig. 1.2 Steps for Problem Solving 3.1 Analysis This step involves finding a way to go from data to results by answering the following 3 questions: What are the inputs (data)? What are the processing operations? What are the outputs (results)? 5 Dr. Samir FENANIR Chapter 1 : Algorithmic Concepts The result of this step is an algorithm composed of a set of instructions written in pseudocode, describing the method for solving the problem. Example: The figure 1.3 presents an analysis for solving a second-degree equation: 2 Ax + Bx +C = 0. Fig. 1.3 Analysis of the second-degree equation problem 3.2 Programming It involves translating the algorithm into a specific programming language. Since the pro- gramming language is intended for the computer, it must adhere to strict syntax rules. The outcome of the programming phase is a program; it is the set of instructions that will be executed by the computer. 3.3 Execution It allows the user to see the results after entering the necessary data for the computer. If the obtained results are not as expected, we would say that there are runtime errors. In this case, it is necessary to review whether the algorithm has been translated correctly or if there was a proper analysis. 4 General Structure of an Algorithm An algorithm is composed of three main parts (Figure 1.4) : 6 Dr. Samir FENANIR Chapter 1 : Algorithmic Concepts Fig. 1.4 General Structure of an Algorithm Head: Serves to give a name to the algorithm, it is preceded by the word Algorithm. Declaration: Is used to declare variables and constants.. Body of the algorithm: Comprises the algorithm’s instructions and is delimited by the words: Begin et End. 4.1 Variables and Constants During the execution of a program, the data as well as the calculation results are stored in boxes of the central memory (CM) which correspond to variables or constants. variable is defined by its name (identifier), its value and its type. Where its value can be changed during program execution. constant is defined by its name (identifier) and its value. Where its value cannot be modified during program execution. 4.1.1 Declaration of variables To be able to use a variable or constant in an algorithm, you must first declare it. Each declaration of a variable must include the name (identifier) and type. 7 Dr. Samir FENANIR Chapter 1 : Algorithmic Concepts Syntax : Variable identifier: type or Variables identifier1, identifier2,... : type (if they have the same type) Examples : Variable average : real Variable age : integer Variables A, B, C : real 4.1.2 Declaration of constants Each declaration of a constant must include the name (identifier) and the value. Syntax : Constant identifier = value Example : Constant pi = 3.14 4.1.3 Identifier It is the name of a constant or variable that allows them to be uniquely identified, and it must meet the following conditions: It must be composed by a sequence of letters: (a..z, A..Z) and numbers: (0..9), in addition to the special character ‘_’. It must always start with a letter. It must be different from the words reserved by the algorithmic language, for example: (Begin, End, If, integer,...). It is best if it is chosen based on the content of the object. Example : Are the following identifiers correct? 8 Dr. Samir FENANIR Chapter 1 : Algorithmic Concepts 4.1.4 Types of variables The type is the set of values that a variable can take, the basic types are: Integer: its value is an integer belonging to the set: {..., −2, −1, 0, 1, 2,...} Real: its value is a fractional number belonging to the set R, Mathematically: R =] − ∞, +∞[ Character: its value is an alphabetical character (A..Z, a..z), numeric (0..9), or special (+, −, $,... ), Examples : ‘9’ , ‘B’ String: its value is a sequence of characters, examples: "Ahmed", "0792/00", "R19" Boolean: its value is logical (true, false). Exercise: Give an identifier and its type for each of the following information about a student: Registration number, First and last name, Date of birth, Group, Section, Notes for the 3 modules: Computer Science (Coef = 4), Math (Coef = 4) and Physics (Coef = 2), their coefficients, The average and "is redoubling". Solution: Constants Comp_Coef =4, Math_Coef=4, Phys_Coef=2 Variables Num, Names, birth_Date: string Group: integer Section: character 9