Algoritmi

The video introduces the concept of algorithms as basic tools in computer science, which we have already used implicitly. It plans to discuss the representation of information, how computers work, operating systems, and computer networks. The goal is to understand algorithms more formally and apply this knowledge to app development.

Not all problems can be solved by machines; only those with specific characteristics can. The video explains that problems solvable by machines are those that can be tackled with specific means. It differentiates between a problem and its resolution process, highlighting that an algorithm provides a standard procedure to solve a problem. The resolution process combines an algorithm with an 'executor' who carries it out.

The concept of problem parameterization is introduced, relating it to variables, which have already been encountered in app development. Examples like adding or multiplying numbers are used to illustrate algorithms. The video mentions early machines that encoded algorithms within their structure, like Pascal's calculator, and questions how to choose the 'best' algorithm when multiple solutions exist for a problem.

A farmer's problem (selling grapes, buying fabric, calculating remaining money) is presented to explain problem-solving. This common math problem illustrates that a specific sequence of operations is necessary to arrive at the correct solution. Some operations can be swapped, but the final step (calculating the remaining sum) must come after the initial calculations, demonstrating the ordered nature of a procedure.

The discussion distinguishes between the creative act of devising a problem-solving procedure and the mechanical execution of that procedure. It emphasizes that solving problems often involves recognizing existing solution schemas (algorithms) and then applying them. This leads to the definition of an algorithm as a sequence of orders to be executed by someone (an executor), similar to a recipe being followed by a cook.

The video explains how to generalize problem solutions using variables (parameters), making an algorithm applicable to a wider range of similar problems. An example demonstrates how replacing specific numbers with variables like X, Y, Z, and K creates a more generic algorithm that can solve various farmer-like problems by simply plugging in different values. This allows numerous people to use the same algorithm for their similar problems.

The speaker provides everyday examples of algorithms, like a recipe requiring clear and understandable instructions for the executor, or a fixed menu in a restaurant that dictates the order of dishes. It questions whether a shopping list is an algorithm, concluding it is not because the order of execution is not mandatory, emphasizing that for something to be an algorithm, the sequence of instructions must be ordered and explicit.

The video presents two algorithms for adding two numbers: the 'abacus' method (counting up and down by one) and the 'normal' or standard columnar addition method. It details the step-by-step process of the counting method, showing how one number is decremented while the other is incremented until the decremented number reaches zero. This method is linked to concepts already seen in app development, such as updating variables (a=a+1) and conditional statements (if B equals 0).

The standard columnar addition algorithm is explained, emphasizing the importance of aligning numbers by place value (units under units, tens under tens). It details the process of summing digits from right to left, handling carries, and iteratively moving to the next column. This method is presented as a more advanced algorithm taught after the basic counting method, highlighting that different algorithms exist for the same problem.

Similar to addition, two algorithms for multiplication are discussed: repeated addition (summing a number 'B' times) and the traditional columnar multiplication method. The repeated addition algorithm is demonstrated by adding 'A' to a running total 'C' while decrementing 'B' until it reaches zero. The columnar method is then outlined, involving multiplying digits and summing partial products.

The video reiterates that a single problem can have multiple algorithms. It highlights that algorithms existed long before computers, citing examples like log tables used by Napoleon and Babbage's difference engine. The discussion notes that many innovations, like GPS (for restaurant finding), stem from military necessities, and emphasizes the importance of choosing an efficient algorithm.

An algorithm is formally defined as a finite sequence of instructions that solves a given parametric problem. A process is introduced as an execution of this algorithm by an executor. The crucial distinction is drawn that while an algorithm must be finite (to be written down), the process resulting from its execution can potentially be infinite if no external event stops it, like a computer operating system. An algorithm being finite is essential for its creation and implementation.

The discussion returns to the two addition algorithms, questioning why the seemingly more complex 'normal' method is taught over the simpler 'abacus' method. The evaluation focuses on two criteria: the algorithm's structure (comprehensibility, number of instructions) and the process it generates (number of steps/time taken to solve a particular problem). While the abacus method has fewer, simpler instructions, its execution (number of steps) for larger numbers is significantly longer compared to the normal method.

The speaker reveals a trick in the previous comparison: the 'steps' in each algorithm were implicitly different. The 'abacus' method's step is a simple +1/-1 operation, while the 'normal' method's step involves summing two digits with a carry, which itself comprises multiple elementary +1/-1 operations. By standardizing the 'basic capability' (e.g., counting by one), it's shown that even considering this, the normal algorithm remains more efficient for larger numbers due to fewer overall complex steps. This leads to the conclusion that efficiency (less time/fewer operations) is the primary driver for choosing an algorithm.

The video introduces flowcharts as a standard graphical language for describing algorithms. It explains the canonical symbols for affirmations (rectangles), conditions (rhombuses with two exits), and jumps (arrows). An example of the abacus addition algorithm is translated into a flowchart, demonstrating how these symbols represent the sequence of operations, conditional checks, and loops. A critical point is made about the distinction between assignment (= for setting a value) and equality testing (= for comparison) within algorithms.

The 'abacus' addition algorithm's flowchart is analyzed for robustness. A specific case (A=5, B=0) reveals a flaw: the algorithm enters an infinite loop because it attempts to decrement B, making it negative, never reaching the B=0 condition. This demonstrates the importance of considering edge cases and proper algorithm design. A corrected flowchart is proposed where the B=0 condition is checked *before* any operations on B, preventing the infinite loop and ensuring correctness for all inputs.

The video contrasts two main paradigms for expressing problem-solving logic: procedural and declarative. Procedural focuses on defining a step-by-step sequence of actions (like the algorithms discussed). Declarative focuses on defining a set of rules or conditions that, when met, yield the solution, without specifying the exact order of steps. An analogy with university credit rules is used to illustrate declarative logic, where achieving a degree is based on fulfilling credit requirements rather than following a strict sequence of exams. The lecture concludes by relating these concepts to app development, where event-driven programming combines both.

The video summarizes the key concepts covered: the existence of solvable problems, algorithms as recipes for solutions, parametric algorithms, the role of executors, and the importance of choosing efficient algorithms (complexity study). It re-emphasizes that efficiency, not just simplicity, is why the 'normal' addition algorithm is favored. The session ends by highlighting the use of flowcharts as a standard language for expressing algorithms and reinforcing the newfound understanding of algorithm choice.