Algorytm gąsienicy – zadanie Bierki
Omówienie zadania Bierki które wymaga algorytmu gąsienicy:
https://youtu.be/MJCkuBDezSE?t=976
Zadanie Bierki pochodzi z II etapu poprzednika Olimpiady Informatycznej Juniorów:
https://youtu.be/MJCkuBDezSE?t=895
Algorytm gąsienicy omówiony na podstawie zadania Bierki:
https://youtu.be/MJCkuBDezSE?t=2345
Złożoność algorytmu gąsienicy:
https://youtu.be/MJCkuBDezSE?t=3188
Strona z rozwiązaniem zadania Bierki – kod C++ który otrzymuje 100%:
Link do zadania Bierki:
https://szkopul.edu.pl/problemset/problem/KiEvCpZBaUNRCp6oTZx2oAQ4/site/
Link do wszystkich zadań II etapu OIG z którego pochodzi zadanie Bierki:
https://szkopul.edu.pl/portal/problemset/oig/1
————–
Grafy
Co to jest graf? Po co nam grafy?
https://youtu.be/UOei4vez6LM?t=118
Grafy – co to jest?
https://youtu.be/OA8BeVFvaNU?t=1006
Czy Europa i Wielka Brytania są spójne?
https://youtu.be/OA8BeVFvaNU?t=1260
oraz
https://youtu.be/OA8BeVFvaNU?t=1386
Co to jest cykl? Czy drzewo ma cykl?
https://youtu.be/OA8BeVFvaNU?t=1329
–
Graf w C++ – jak trzymamy graf w komputerze:
https://youtu.be/UOei4vez6LM?t=4090
–
Do trzymania grafu wykorzystujemy wektor:
https://youtu.be/UOei4vez6LM?t=6053
a tak naprawdę tablicę wektorów:
https://youtu.be/UOei4vez6LM?t=6100
–
Jak trzymamy graf w pamięci?
https://youtu.be/OA8BeVFvaNU?t=2479
–
Kiedy zaczęła się nauka o grafach? (Quiz)
Od analizy problemów w Królewcu przez Eulera
https://youtu.be/iDPLi4XQN2w?t=376
Co to jest graf?
https://youtu.be/iDPLi4XQN2w?t=738
Przykład osób w klasie połączonych relacją czy ktoś kogoś lubi czy nie?
Po co nam grafy?
https://youtu.be/iDPLi4XQN2w?t=830
– kto mnie może poznać z inną osobą?
– komu powiedzieć informacje by szybko się rozniosła?
– jak szybko się rozniesie?
– ile osób zna się w danej społeczności – na przykład zainteresowanej kupnem samochodu
– ile osób dzieli dwie inne by przekazać wiadomość
– na świecie jest 7 miliardów ludzi, różne preferencje -> grafy są gigantyczne
– a google w ciągu 1/10 sekundy musi nam pokazać strony spośród miliardów stron – zanalizował gigantyczny graf
– podobnie facebook – pokazuje nam strony – analizuje graf
– gwiazdka – podpowiedzi prezentów biorą się z analizy grafu!
Grafy to jest dziedzina która potrzebuje nowych pomysłów – nas!
https://youtu.be/iDPLi4XQN2w?t=1197
– to my wymyślimy lepsze algorytmu które lepiej pokażą strony, podpowiedzi prezentów, …
– wszystko można przedstawić jako graf
– jeśli umiemy posługiwać się grafami – jesteśmy pożądani, magikami
– zamiast miliona lat, program wykona się w sekundę
– każda sekunda poświęcona na grafy, to najlepiej spędzony czas
– mamy moc by te rozwiązać najtrudniejsze problemy!
– fascynują przygoda przed nami
Przykład, że grafem można zobrazować wszystko.
Budowa domu – harmonogram działań
https://youtu.be/iDPLi4XQN2w?t=1346
Dom jest prosty, ale bez gafu nie zrobimy:
– kompleks fabryk, osiedle, rakieta kosmiczna, rozkład zadań w fabryce
Samochód – produkcja – harmonogram zadań
https://youtu.be/iDPLi4XQN2w?t=1426
– fabryka dostaje plan na następny tydzień bo tydzień czasu jest graf analizowany
– znając grafy, możemy to poprawić, zwiększyć zyski fabryki
Klasyczne problemy grafu:
https://youtu.be/iDPLi4XQN2w?t=1522
– najkrótsza droga
– problem chińskiego listonosza – obejść wszystkie domy i wrócić do bazy
Przykład z ciężarówkami – redukujemy koszty o 10% – skracając drogę ciężarówek – gigantyczny zysk dla nas i dla firmy!
https://youtu.be/iDPLi4XQN2w?t=1546
Jesteśmy w stanie pomóc jeśli znamy algorytmikę!
https://youtu.be/iDPLi4XQN2w?t=1772
– jeśli umiemy przedstawić problem jako graf to przyspieszymy jego rozwiązanie!
– i wielki FUN!
===============
DFS – Depth First Search
Algorytm który chodzi po grafie “W głąb”
–
Chodzimy po grafie – Co to jest DFS?
https://youtu.be/UOei4vez6LM?t=884
Jak chodzić po grafie / drzewie:
https://youtu.be/OA8BeVFvaNU?t=3933
Algorytm DFS:
https://youtu.be/OA8BeVFvaNU?t=4025
DFS – implementacja i wyjaśnienie:
https://youtu.be/UOei4vez6LM?t=5326
Implementacja DFS:
https://youtu.be/OA8BeVFvaNU?t=5623
PreOrder i PostOrder:
https://youtu.be/-6XSy1IUlgg?t=1998
===============
C++ – pierwszy program
Jak wypisujemy tekst w języku C++?
Czym kończy się każde polecenie w C++?
https://youtu.be/zN3CApegsSY?t=2388
ZADANIE SERCE – pierwszy program wypisujący piękne serce na ekranie
Początek omówienia zadania Serce:
https://youtu.be/zN3CApegsSY?t=1682
Omówienie, kod link do zadania Serce:
https://oki.org.pl/serce/
Piszemy pierwszy program w języku C++
Rysowanie choinki z kodów ASCII
https://youtu.be/xF5wlR-xX8g?t=2072
Link do kodu, omówienia zadania:
https://oki.org.pl/choinka/
Zadanie czekoladki dało nam nową wiedzę w C++
Wczytywanie danych w C++:
https://youtu.be/CMasYTVhIjQ?t=1393
–
Zmienne w programowaniu / C++ czyli szufladki w których komputer przechowuje nam wartości
https://youtu.be/CMasYTVhIjQ?t=1422
W naszym kodzie były to liczby całkowite typu int o wielkości -2 147 483 648 do 2 147 483 647
–
Komentarz w C++ czyli coś co C++ zupełnie nie interesuje:
https://youtu.be/CMasYTVhIjQ?t=1608
–
Wczytywanie z klawiatury i przechowywanie w zmiennych:
https://youtu.be/CMasYTVhIjQ?t=1796
–
Jak nazywać zmienne?
Piszmy kod, byśmy zawsze wiedzieli co on robi:
https://youtu.be/CMasYTVhIjQ?t=2212
–
Wykonujemy działania arytmetyczne w C++:
https://youtu.be/CMasYTVhIjQ?t=2271
–
Wszystkie zmienne deklarujemy w C++:
https://youtu.be/CMasYTVhIjQ?t=2397
–
Deklarujmy zmienne na początku:
https://youtu.be/CMasYTVhIjQ?t=2488
===============
Tworzymy CV na podstawie rozwiązanego zadania
Tworzymy CV na podstawie rozwiązanego zadania USACO – Amerykańska Olimpiada Informatyczna.
W przyszłości (staż, projekt, uczelnia) pokazujemy moc, pracowitość, pomysłowość!!!
Nawet na imprezie!
https://youtu.be/UOei4vez6LM?t=7251
CV pomaga nam w zdobyciu dobrej szkoły, stażu – tak jak pan Krzysztof Maziarz z Microsoft który był naszym gościem:
https://youtu.be/yYn4AOQU4S4?t=8114
=================
Złożoność
=================
Przygoda / Olimpiada
Nad każdym zadaniem pomyśl! https://youtu.be/2RV8_naxzHE?t=9257
Olimpijskie Koło Informatyczne #2 zaczęliśmy od nietypowej karety:
https://youtu.be/CMasYTVhIjQ?t=154
Dlaczego? Przyszłość jest nasza! Świat nas potrzebuje!!!
Potrzeba bardzo dużo programistów, osób które wymyślają
Jest mnóstwo problemów które trzeba rozwiązać – świat czeka na nas!
Czy Olimpiada Informatyczna Juniorów jest dla początkujących
czy zaawansowanych?
I dla takich i dla takich!
https://youtu.be/CMasYTVhIjQ?t=4800
O co chodzi w Olimpiadzie?
https://youtu.be/CMasYTVhIjQ?t=4885
* Żeby się poznawać algorytmy, programować
* Pretekst do rozwijania się
* Żebyśmy pod koniec roku byli dużo mocniejsi
https://youtu.be/zN3CApegsSY?t=1205OKI1 – przygotowanie OD ZERA do Olimpiady i do pięknej przyszłości!
By mieć ciekawe życie, fun, godne życie.
Przygotowuj się do Olimpiady.
Rozwiązuj zadania.
Po pół roku zobaczy moc – to jest obietnica.
Przykład ucznia który zrobił algorytm do pakowania paczek.
Przykład ucznia który otrzymał duże pieniądze za optymalizację ryzyka.
Będziemy pożądanymi ludźmi na rynku.
Programujemy, rozwiązujemy problemy.
Dziś motywuje nas Olimpiada. W przyszłości znajdziemy lek na raka, przyjazny plastik, sygnał dalekiej cywilizacji
https://youtu.be/zN3CApegsSY?t=32
Olimpiada motywuje nas do nauki programowania i algorytmiki.
By w przyszłości pisać programy i znaleźć lek na raka:
https://youtu.be/zN3CApegsSY?t=32
Olimpiada prowadzi nas do pięknej przygody by zmieniać, negować, wymyślać.
Jesteśmy odkrywcami, tymi którzy negują, tymi którzy w przyszłości mają wymyślać w Google’u, start-upach, na uczelniach:
https://youtu.be/2RV8_naxzHE
Przez programowanie, Olimpiadę do pięknej przygody!
https://youtu.be/xF5wlR-xX8g?t=953
Dlaczego Olimpiada?
Chodzi o rozwiązanie problemów świata
Oki #1 2019/2020
https://youtu.be/xF5wlR-xX8g?t=953
Ilość operacji. Szczegółowe wyjaśnienie:
https://youtu.be/LryJ-4lrXts?t=8663
Komputer kwantowy nie rozwiąże problemów.
Problemy są o złożoności 2^n
Musimy czekać miliony lat na rozwiązanie tych problemów.
Dlatego świat potrzebuje Ciebie – Twoich pomysłów, by komputer zdążył policzyć.
Świat czeka być dużo nauczył się w Olimpiadzie!!!
https://youtu.be/MJCkuBDezSE?t=120
Sztuczna inteligencja jest potrzebna bo komputery są wolne – startup który zarobił 2.1 mld.
Dlatego startujemy w Olimpiadzie – negujemy, wymyślamy.
https://youtu.be/Je9Bfy6lu3Y?t=237
=================
Quizy, samodzielne poszukiwania nas rozwijają
Był tez quiz który dał wielka radość
Quiz z rysowanie znaków ASCII:
https://youtu.be/CMasYTVhIjQ?t=4050
Ale też eksperymentowaliśmy!
https://youtu.be/CMasYTVhIjQ?t=2867
I zmusiliśmy komputer do błędu:
https://youtu.be/CMasYTVhIjQ?t=3328
2147483647 + 1 dało liczbę ujemną!
A dlaczego?
Bo każde pudełko kiedyś pęka!
Jeśli czegoś nie rozumiemy – to normalne!
Zawsze można wrócić do treści!
Ale trochę czasu – i będziemy śmigać
https://youtu.be/CMasYTVhIjQ?t=4658
Zadanie przed zajęciami są jawne.
Myśląc nad zadaniem więcej korzystamy z zajęć!
https://youtu.be/OC_xrHSMYlA?t=4190
Robiąc research jesteśmy naukowcami, poszukiwaczami, odkrywcami nowych lądów!
https://youtu.be/eCSjwO9wu0I?t=10111
Być odkrywcą! Wszystko się zaczyna od pytania dlaczego? Jest wiele do odkrycia!
https://youtu.be/Q3j6LNU_LRM?t=937
Zawsze zadajemy pytanie dlaczego, kiedy? Wówczas jesteśmy odkrywcami, tymi którzy wymyślą nową rzecz, założą start-up. Historia DD
https://youtu.be/Q3j6LNU_LRM?t=415
Nie ma znaczenia czy umiem programować, czy nie – czy znam algorytmikę czy nie – wystarczy poświęcić się pasji, wystarczy trud, wystarczy liczyć zadania – historia Mikołaja:
https://youtu.be/SUnVGr8lWw4?t=1111
Dlaczego zadania są znane przed zajęciami? Bo nasze pomysły przed zajęciami są najważniejsze:
https://youtu.be/2RV8_naxzHE?t=4530
Nasze pomysły są najważniejsze! Żebyśmy myśleli inaczej niż wszyscy!
https://youtu.be/2RV8_naxzHE?t=5872
Nasza droga która czymś więcej niż programowanie – to wymyślanie!
https://youtu.be/OC_xrHSMYlA?t=254
=================
Programowanie, algorytmika
Po co nam to programowanie?
https://youtu.be/zN3CApegsSY?t=952
By komputer robił nudne, powtarzające się czynności.
By ułatwiał życie – przykłady problemów:
https://youtu.be/zN3CApegsSY?t=1372
Na czym polega programowanie?
Pokazaliśmy to na przykładzie oddzielania grochu od maku
https://youtu.be/zN3CApegsSY?t=1006
zobaczyliśmy, że programowanie to powtarzanie (pętla) i decyzja (warunek)
https://youtu.be/zN3CApegsSY?t=1079
Może ciut więcej
Wielu z nas myśli – ale ja nic nie umiem…
Spokojnie – będzie moc!
https://youtu.be/zN3CApegsSY?t=1092
Nie tylko będziesz pisał programy ale rozwiązywał problemy!
Algorytmika – piękna część informatyki
Dlaczego nikt nie znalazł leku na raku?
Bo komputer jest wolny.
Potrzebujemy algorytmiki – by programy się szybko kończyły
https://youtu.be/zN3CApegsSY?t=1190
Przykłady problemów algorytmicznych:
https://youtu.be/zN3CApegsSY?t=1382
Zapraszam na zajęcia z algorytmiki.
Problem źle rozwiązany komputer liczy długo, problem dobrze rozwiązany – komputer liczy ułamek sekundy,
https://youtu.be/zN3CApegsSY?t=1311
Czym jest język programowania a czym algorytmika?
https://youtu.be/iDPLi4XQN2w?t=6944
Dlaczego warto umieć programować – quiz:
https://youtu.be/zN3CApegsSY?t=609
Mogę pomóc, automatyzuję, jestem lepszy w grach – MAM FUN!
Co to jest programowanie – quiz:
https://youtu.be/zN3CApegsSY?t=450
Jaki musi być program komputerowy?
https://youtu.be/zN3CApegsSY?t=812
Poprawny – a czasem też z szybki!
=====================
OKI – na czym polegają nasze zajęcia?
Na czym polegają zajęcia OKI?
https://youtu.be/zN3CApegsSY?t=1484
* Spotkania – problemy znamy wcześniej by samodzielnie pomyśleć
Nasze pomysły są bardzo ważne
* Quizy
* Challenge
Co jest najważniejsze z tej trójki?
https://youtu.be/zN3CApegsSY?t=1580
Challenge – nasze własne rozwiązania zadań!
To one pchają nas do przodu
Myślimy 4h sami – nawet jak nie zrobimy – najlepiej spędzony czas
Potem szukamy pomocy – Pitagoras nie doszedł tego momentu
Pamiętajmy co jest kluczem do sukcesu
3-6 zadań tygodniowo:
https://youtu.be/zN3CApegsSY?t=1602
Jak wrzucać/dodawać własne rozwiązanie do challenge / pracy domowej?
https://youtu.be/zN3CApegsSY?t=3972
Lista zadań w Challenge’u:
https://oki.org.pl/lista-zadan.php
Ranking:
https://oki.org.pl/ranking-z-ostatniego-tygodnia.php
Zachęcam do samodzielnego rozwiązywania zadań – wtedy się rozwijasz!
https://youtu.be/zN3CApegsSY?t=4210
Jak najwięcej samemu!
====================
Lista algorytmów i osób które wymyśliły te algorytmy:
https://www.ics.uci.edu/~eppstein/161/people.html
Lista pionierów w “ComputerScience”:
https://en.wikipedia.org/wiki/List_of_pioneers_in_computer_science
Zastosowanie grafów:
https://www.sunjackson.com/post/7060/
—-
Jak uzyskac specjalizację w danej grupie programistycznej?
https://roadmap.sh/