Algorytmika od podstaw

Najważniejsze algorytmy maturalne 

Programowanie od lat zyskuje na popularności. Nie ma co się dziwić – w obecnych czasach praktycznie każda firma jest skomputeryzowana. Z tego powodu programista, w szczególności dobry programista cieszy się ogromnym zainteresowaniem headhunterów. Jak jednak odróżnić przeciętnego programistę od dobrego? Jednym z kryteriów jest znajomość algorytmów. Taka umiejętność pozwala napisać dużo szybszy i bardziej wydajny program – często różnica jest znacząca (np. obliczenia trwają kilka sekund, nie kilka godzin). Celem warsztatu jest wprowadzenie uczestników w świat pisania szybkich programów.

Do kogo kierowany jest ten warsztat?

Warsztat jest skierowany do licealistów chcących szlifować swoje umiejętności programistyczne pod kątem algorytmiki. Umiejętność pisania szybkich programów to podstawa pracy kodera. Jedno to stworzyć i wymyślić rozwiązanie dające poprawne wyniki, a drugie to nie spędzić wieków (a i takie rozwiązania można napisać) czekając na zakończenie obliczeń.

Do uczestnictwa w warsztatach wymagana jest znajomość programowania strukturalnego (pętle, ify, typy zmiennych, tablice itp.). Preferowana znajomość języków rodziny C, ale nie jest to konieczne (będzie wprowadzanie do składni C++). W celu sprawdzenia gotowości do udziału w warsztacie, załączamy w linku test (oraz odpowiedzi), który sprawdzi wymagane umiejętności. 

Test

Liczby

Niezbędny sprzęt i oprogramowanie

Do uczestnictwa w warsztatach wymagany jest własny laptop o minimalnych parametrach:

• System Windows 11, 10, 8, 7 (SP1, 64 bitowy), Linux (64 bitowy) lub MacOS
• 4 GB RAM
• 10 GB wolnego miejsca na dysku (na środowisko programistyczne)
• Uprawnienia administratora (do instalowania wymaganych na zajęciach pakietów)

Wymagany program (wszystkie są darmowe oraz dostępne na prawie każdy system operacyjny):

Środowisko programistyczne wspierające język C++, do wyboru:

• Visual Studio Community: https://visualstudio.microsoft.com/pl/vs/community/  
• Code::Blocks: https://www.codeblocks.org/  

Do Code::Blocks przyda się MinGW: https://www.mingw-w64.org/  

Dlaczego warto wziąć udział w tym warsztacie?

Uczestnicy warsztatu:

• poznają składnię języka C++,
• nauczą się pojęć oraz idei związanych z algorytmiką,
• poznają popularne na rynku narzędzia do pracy z C++,
• napiszą własną strukturę danych,
• nauczą się obliczać złożoności programów,
• rozwiną umiejętność rozwiązywania problemów.

Program warsztatu

Dzień pierwszy

Składnia C++, złożoność, struktury danych vs kontenery, lista 

Pierwszy dzień warsztatów zaczniemy wprowadzeniem do składni C++. Następnie dowiemy się co to jest złożoność programu (O-notacja, Ω-notacja, Θ-notacja). Poznamy również różnicę między strukturą danych oraz kontenerem. Na koniec zajmiemy się listami – podstawową, ale istotną w programowaniu strukturą danych. Dowiemy się, jakie zalety, a jakie wady mają listy uporządkowane, nieuporządkowane oraz czym różni się lista jednokierunkowa od dwukierunkowej. Zastosujemy nową wiedzę w praktyce implementując naszą własną listę. 

Dzień drugi

Stos, kolejka, kopiec, sortowanie elementarne i nieelementarne

Drugi dzień rozpoczniemy od poznania dwóch istotnych kontenerów – stosu oraz kolejki. Rozszerzymy kolejkę o priorytet tworząc kolejkę priorytetową. Zaimplementujemy ją poznawszy najpierw pierwszą drzewiastą strukturę danych – kopiec. Zapoznamy się również z problemem sortowania – omówimy najważniejsze algorytmy elementarne oraz nieelementarne. Dowiemy się, co to znaczy, że sortowanie jest stabilne, niestabilne, antystabilne oraz in situ i ex situ.

Dzień trzeci

Algorytmy numeryczne 

Na matematyce często rozwiązuje się różne równania. Nierzadko nie jest to łatwe zadanie. Trzeci dzień rozpoczniemy od algorytmów znajdowania przybliżonego miejsca zerowego funkcji – rozwiążemy (z pewną dokładnością) naszą szkolną udrękę. Następnie zajmiemy się szacowaniem wartości całek oznaczonych, przecinaniem się prostych oraz schematem Hornera (obliczanie wartości wielomianu).

Dzień czwarty

Programowanie zachłanne i dynamiczne

Czasami jak rozwiązujemy jakiś problem algorytmiczny to wydaje nam się, że najprostsze rozwiązanie będzie najlepsze. Podejście takie nazywa się zachłannym. Niestety, często nie mamy racji. Czwartego dnia warsztatów poznamy najważniejsze różnice między podejściem zachłannym, dziel i rządź, dynamicznym oraz heurystycznym. Omówimy najważniejsze problemy rozwiązywane zachłannie, które posiadają dużo wydajniejsze rozwiązania dynamiczne.

Dzień piąty

Systemy pozycyjne, zadania przekrojowe

Ostatni dzień warsztatów rozpoczniemy krótkim wstępem do systemów pozycyjnych – dowiemy się jak konwertować liczby zapisane w różnych systemach. Następnie zdobytą przez cały warsztat wiedzę wykorzystamy rozwiązując przekrojowe zadania programistyczne z zakresu algorytmiki.